Name
Title | ||
|---|---|---|
One-dimensional cutting stock problem with a given number of setups: a hybrid approach of metaheuristics and linear programming |
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. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1007/s10852-005-9031-0 | Journal of Mathematical Modelling and Algorithms |
Keywords | Field | DocType |
cutting stock problem,linear program | Mathematical optimization,Cutting stock problem,Linear programming,Mathematics,Metaheuristic | Conference |
Volume | Issue | ISSN |
5 | 1 | 1572-9214 |
Citations | PageRank | References |
6 | 0.57 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shunji Umetani | 1 | 56 | 5.41 |
| Mutsunori Yagiura | 2 | 614 | 46.59 |
| Toshihide Ibaraki | 3 | 2593 | 385.64 |