One-Dimensional Cutting Stock Problem with a Given Number of Setups: A Hybrid Approach of Metaheuristics and Linear Programming |
| |
Authors: | Shunji Umetani Mutsunoti Yagiura Toshihide Ibaraki |
| |
Institution: | (1) Department of Systems Engineering, Faculty of Electro-Communications, The University of Electro-Communications, Tokyo, Japan;(2) Department of Computer Sciences and Mathematical Informatics, Graduate School of Information Science, Nagoya University, Nagoya, Japan;(3) Department of Informatics, School of Science and Technology, Kwansei Gakuin University, Hyogo, Japan |
| |
Abstract: | One-dimensional cutting stock problem (1D-CSP) is one of the representative combinatorial optimization problems, which arises
in many industrial applications. Since the setup costs for switching different cutting patterns become more dominant in recent
cutting industry, we consider a variant of 1D-CSP, called the pattern restricted problem (PRP), to minimize the number of
stock rolls while constraining the number of different cutting patterns within a bound given by users. For this problem, we
propose a local search algorithm that alternately uses two types of local search processes with the 1-add neighborhood and
the shift neighborhood, respectively. To improve the performance of local search, we incorporate it with linear programming
(LP) techniques, to reduce the number of solutions in each neighborhood. A sensitivity analysis technique is introduced to
solve a large number of associated LP problems quickly. Through computational experiments, we observe that the new algorithm
obtains solutions of better quality than those obtained by other existing approaches. |
| |
Keywords: | 90C90 90C27 90C10 |
本文献已被 SpringerLink 等数据库收录! |
|