The one-dimensional cutting stock problem with usable leftovers – a survey. (English) Zbl 1317.90003
Summary: In this article, we review published studies that consider the solution of the one-dimensional cutting stock problem (1DCSP) with the possibility of using leftovers to meet future demands, if long enough. The one-dimensional cutting stock problem with usable leftovers (1DCSPUL) is a problem frequently encountered in practical settings but often, it is not dealt with in an explicit manner. For each work reviewed, we present the application, the mathematical model if one is proposed and comments on the computational results obtained. The approaches are organized into three classes: heuristics, item-oriented, or cutting pattern-oriented.
MSC:
| 90-02 | Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming |
| 90C27 | Combinatorial optimization |
| 90C10 | Integer programming |
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
References:
| [1] | Abuabara, A.; Morabito, R., Cutting optimization of structural tubes to build agricultural light aircrafts, Annals of Operations Research, 169, 149-165 (2009) · Zbl 1279.90207 |
| [3] | Arbibi, C.; Marinelli, F.; Rossi, F.; Di Iorio, F., Cutting and reuse: An application from automobile component manufacturing, Operations Research, 50, 923-934 (2002) · Zbl 1163.90533 |
| [4] | Arenales, M. N.; Morabito, R.; Yanasse, H., Cutting and packing problems, Pesquisa Operacional, 19, 107-299 (1999) |
| [5] | Bischoff, E.; Wäscher, G., Cutting and packing, European Journal of Operational Research, 84, 3 (1995), (special issue) · Zbl 0904.00026 |
| [6] | Brown, A. R., Optimum packing and depletion: The computer in space and resource usage problem (1971), Macdonald - London and American Elsevier Inc.: Macdonald - London and American Elsevier Inc. New York, 107p · Zbl 0268.90034 |
| [7] | Caprara, A.; Kellerer, H.; Pferschy, U., A PTAS for the multiple subset sum problem with different knapsack capacities, Information Processing Letters, 73, 111-118 (2000) · Zbl 1014.68225 |
| [9] | Cherri, A. C.; Alem, D. J.; Silva, I. N., Inferência Fuzzy para o problema de corte de estoque com sobras aproveitáveis de material, Pesquisa Operacional, 31, 1-22 (2011) |
| [10] | Cherri, A. C.; Arenales, M. N.; Yanasse, H. H., The one dimensional cutting stock problems with usable leftover: A heuristic approach, European Journal of Operational Research, 196, 897-908 (2009) · Zbl 1176.90158 |
| [11] | Cherri, A. C.; Arenales, M. N.; Yanasse, H. H., The usable leftover one-dimensional cutting stock problem-a-priority-in-use heuristic, International Transactions in Operational Research, 20, 189-199 (2013) · Zbl 1263.90071 |
| [13] | Chu, C.; Antonio, J., Approximation algorithms to solve real-life multicriteria cutting stock problems, Operations Research, 47, 495-508 (1999) · Zbl 1041.90536 |
| [14] | Cui, Y.; Yang, Y., A heuristic for the one-dimensional cutting stock problem with usable leftover, European Journal of Operational Research, 204, 245-250 (2010) · Zbl 1192.90163 |
| [15] | Cui, Y.; Zhao, X.; Yang, Y.; Yu, P., A heuristic for the one-dimensional cutting stock problem with pattern reduction, Proceedings of the Institution of Mechanical Engineers, Part B. Journal of Engineering Manufacture, 222, 677-685 (2008) |
| [16] | Dimitriadis, S.; Kehris, E., Cutting stock optimization in custom door and window manufacturing industry, International Journal of Decision Sciences, Risk and Management, 1, 66-80 (2009) |
| [17] | Dowsland, K.; Dowsland, W., Packing problems, European Journal of Operational Research, 56, 2-14 (1992) · Zbl 0825.90355 |
| [18] | Dyckhoff, H., A typology of cutting and packing problems, European Journal Operational Research, 44, 145-159 (1990) · Zbl 0684.90076 |
| [19] | Dyckhoff, H.; Finke, U., Cutting and packing in production and distribution: Typology and bibliography (1992), Springer: Springer Heidelberg |
| [20] | Dyckhoff, H.; Kruse, H. J.; Abel, D.; Gal, T., Trim loss and related problems, The International Journal of Management Science, 13, 59-72 (1985) |
| [21] | Dyckhoff, H.; Scheithauer, G.; Terno, J., Cutting and packing, (Dell’Amico, M.; Maffioli, F.; Martello, S., Annoted bibliographies in combinatorial optimization (1997), John Wiley & Sons: John Wiley & Sons New York), 393-414 · Zbl 1068.90509 |
| [22] | Dyckhoff, H.; Wäscher, G., Special issue: Cutting and packing, European Journal of Operational Research, 44, 2 (1990) |
| [23] | Eilon, S.; Christofides, N., The loading problem, Management Science, 17, 259-268 (1971) · Zbl 0208.45701 |
| [25] | Gilmore, P. C.; Gomory, R. E., A linear programming approach to the cutting stock problem, Operations Research, 9, 848-859 (1961) · Zbl 0096.35501 |
| [26] | Gilmore, P. C.; Gomory, R. E., A linear programming approach to the cutting stock problem - Part II, Operations Research, 11, 863-888 (1963) · Zbl 0124.36307 |
| [27] | Gracia, C.; Andrés, C.; Gracia, L., A hybrid approach based on genetic algorithms to solve the problem of cutting structural beams in a metalwork company, Journal of Heuristics, 19, 253-273 (2013) |
| [28] | Gradisar, M.; Jesenko, J.; Resinovic, C., Optimization of roll cutting in clothing industry, Computers & Operational Research, 10, 945-953 (1997) · Zbl 0893.90144 |
| [29] | Gradisar, M.; Kljajic, M.; Resinovic, C.; Jesenko, J., A sequential heuristic procedure for one-dimensional cutting, European Journal of Operational Research, 114, 557-568 (1999) · Zbl 0938.90058 |
| [30] | Gradisar, M.; Resinovic, C.; Kljajic, M., A hybrid approach for optimization of one-dimensional cutting, European Journal of Operational Research, 119, 719-728 (1999) · Zbl 0945.90049 |
| [31] | Gradisar, M.; Trkman, P., A combined approach to the solution to the general one-dimensional cutting stock problem, Computers & Operations Research, 32, 1793-1807 (2005) · Zbl 1074.90045 |
| [32] | Gupta, J.; Ho, J., A new heuristic algorithm for the one dimensional bin packing problem, Production Planning & Control, 10, 598-603 (1999) |
| [33] | Hifi, M., Special issue: Cutting and packing problems, Studia Informatica Universalis, 2, 1 (2002) |
| [34] | Hinxman, A., The trim-loss and assortment problems: A survey, European Journal of Operational Research, 5, 8-18 (1980) · Zbl 0442.90072 |
| [35] | Koch, S.; König, S.; Wäscher, G., Linear programming for a cutting problem in the wood processing industry - A case study, International Transactions in Operational Research, 16, 715-726 (2009) · Zbl 1179.90235 |
| [36] | Kos, L.; Duhovnik, J., Cutting optimization with variable-sized stock and inventory status data, International Journal of Production Research, 40, 2289-2301 (2002) · Zbl 1044.90026 |
| [38] | Martello, S., Special issue: Knapsack, packing and cutting, Part I: One dimensional knapsack problems, INFOR, 32, 3 (1994) |
| [39] | Martello, S., Special issue: Knapsack, packing and cutting, Part II: Multidimensional knapsack and cutting stock problems, INFOR, 32, 4 (1994) · Zbl 0806.00019 |
| [40] | Morabito, R.; Arenales, M. N.; Yanasse, H. H., Special issue on cutting, packing and related problems, International Transactions in Operations Research, 16, 6 (2009) |
| [41] | Oliveira, J. F.; Wäscher, G., Special issue on cutting and packing, European Journal of Operational Research, 183 (2007) |
| [42] | Poldi, K. C.; Arenales, M. N., Heuristics for the one-dimensional cutting stock problem with limited multiple stock lengths, Computers & Operations Research, 36, 2074-2081 (2009) · Zbl 1179.90292 |
| [44] | Roodman, G. M., Near-optimal solutions to one-dimensional cutting stock problem, Computers & Operations Research, 13, 713-719 (1986) · Zbl 0622.90066 |
| [45] | Scheithauer, G., A note on handling residual length, Optimization, 22, 461-466 (1991) · Zbl 0739.90045 |
| [46] | Sinuany-Stern, Z.; Weiner, I., The one dimensional cutting stock problem using two objectives, Journal of the Operational Research Society, 45, 231-236 (1994) · Zbl 0789.90062 |
| [47] | Sweeney, P.; Parternoster, E., Cutting and packing problems: A categorized, application-oriented research bibliography, Journal of the Operational Research Society, 43, 691-706 (1992) · Zbl 0757.90055 |
| [48] | Terno, J.; Lindemann, R.; Scheithauer, G., Zuschnittprobleme und ihre praktische Lösung (1987), Verlag Harri Deutsch: Verlag Harri Deutsch Thun, Frankfurt/Main · Zbl 0657.65089 |
| [49] | Trkman, P.; Gradisar, M., One-dimensional cutting stock optimization in consecutive time periods, European Journal of Operational Research, 179, 291-301 (2007) · Zbl 1180.90322 |
| [50] | Wang, P. Y.; Wäscher, G., Cutting and packing, European Journal of Operational Research, 141, 239-469 (2002) |
| [51] | Wäscher, G.; Haußner, H.; Schumann, H., An improved typology of cutting and packing problems, European Journal of Operational Research, 183, 1109-1130 (2007) · Zbl 1278.90347 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
