One-dimensional cutting stock problem with a given number of setups: A hybrid approach of metaheuristics and linear programming

One-dimensional cutting stock problem with a given number of setups: A hybrid approach of metaheuristics and linear programming

0.00 Avg rating0 Votes
Article ID: iaor20062684
Country: Netherlands
Volume: 5
Issue: 1
Start Page Number: 43
End Page Number: 64
Publication Date: Apr 2006
Journal: Journal of Mathematical Modelling and Algorithms
Authors: , ,
Keywords: heuristics, programming: linear
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.

Reviews

Required fields are marked *. Your email address will not be published.