VARIANTS OF THE CUTTING STOCK PROBLEM AND THE SOLUTION METHODS

Abstract

Over the years, column generation based algorithms such as branch and price have been the preferred solution techniques for the classical cutting stock problem (CSP). However, most cutting stock problems encountered in the real world are variants of the classical CSP with many more complexities. The exact algorithms have been found wanting for these variant problems such as cutting stock with knives setup considerations, pattern minimization, ordered cutting stock, order spread minimization, minimization of open stacks, CSP with contiguity, CSP with due dates and service level considerations, CSP with multiple objectives and integration of the cutting stock problem with other production processes. This paper studies the cutting stock variants with an emphasis on the optimality of solutions obtained by the approximate methods.

Keywords

• Cutting Stock Problems, Computational Techniques, Optimization

Kaynakça

1. Araujo, S. A., Constantino, A. A., & Poldi, K. C. (2011). An evolutionary algorithm for the one-dimensional cutting stock problem. International Transactions in Operational Research, 18, 115-127.
2. Becceneri, J., Yanasse, H., & Soma, N. (2004). A method for solving the minimization of the maximum number of open stacks problem within a cutting process. Computers & operations research, 31(14), 2315-2332.
3. Chen, C., Hart, S., & Tham, W. (1996). A simulated annealing heuristic for the one-dimensional cutting stock problem. European journal of operational research, 93(3), 522-535.
4. Chiong, R., & Beng, O. K. (2007). A comparison between Genetic algorithms and Evolutionary Programming based on Cutting Stock Problem. Engineering Letters, 14:1.
5. Falkenauer, E. (1996). A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics, 2(1), 5-30. doi: 10.1007/bf00226291
6. Foerster, H., & Wascher, G. (1998). Simulated annealing for order spread minimization in sequencing cutting patterns. European journal of operational research, 110(2), 272-281.
7. Foerster, H., & Wascher, G. (2000). Pattern reduction in one-dimensional cutting stock problems. International journal of production research, 38(7), 1657- 1676.
8. Gau, T., & Wascher, G. (1995). CUTGEN1: A problem generator for the standard one-dimensional cutting stock problem. European journal of operational research, 84(3), 572-579.

9. Gen M., & Cheng, R. (2000). Combinitorial Optimzation Problems Genetic Algorithms and Engineering Optimization (pp. 53-96). New York: John Wiley & Sons, Inc.
10. Golfeto, R., Moretti, A. , & Neto, L. (2009). A genetic symbiotic algorithm applied to the one-dimensional cutting stock problem. Advanced Modeling and OPtimization, 11(4), 473-501.
11. Haessler, R. W. (1975). Controlling cutting pattern changes in one-dimensional trim problems. OPERATIONS RESEARCH, 23(3), 483-493.
12. Hinterding, R., & Khan, L. (1995). Genetic algorithms for cutting stock problems: With and without contiguity Progress in Evolutionary Computation (pp. 166-186).
13. Liang, K.-H., Yao, X., Newton, C., & Hoffman, D. (2002). A new evolutionary approach to cutting stock problems with and without contiguity. Computers & Operations Research, 29(12), 1641-1659.
14. McDiarmid, C. (1999). Pattern minimisation in cutting stock problems. Discrete applied mathematics, 98(1-2), 121-130.
15. Palisade. (2009). Evolver Extras Guide to Using Evolver: The Genetic Algorithm Solver for Microsoft Excel (pp. 93-97). New York: Palisade Corporation.
16. Peng, J., & Chu, Z. S. (2010). A Hybrid Multi-chromosome Genetic Algorithm for the Cutting Stock Problem. Paper presented at the International Conference on Information Management, Innovation Management and Industrial Engineering (ICIII) 26-28 Nov. 2010.
17. Poldi, K. C., & Arenales, M. N. (2009). Heuristics for the one-dimensional cutting stock problem with limited multiple stock lengths. Computers & operations research, 36(6), 2074.
18. Ragsdale, C., & Zobel, C. (2004). The ordered cutting stock problem. Decision Sciences, 35(1), 83-100.
19. Reeves, C. (1996). Hybrid genetic algorithms for bin-packing and related problems. Annals of Operations Research, 63(3), 371-396.
20. Respicio, A., & Captivo, M. (2005). Bi-Objective Sequencing of Cutting Patterns. In T. Ibaraki, K. Nonobe & M. Yagiura (Eds.), Metaheuristics: Progress as Real Problem Solvers (Vol. 32, pp. 227-241): Springer US.
21. Stawowy, A. (2008). Evolutionary based heuristic for bin packing problem. Computers & Industrial Engineering, 55(2), 465-474.
22. Umetani, S., Yagiura, M., & Ibaraki, T. (2006). One-Dimensional Cutting Stock Problem with a Given Number of Setups: A Hybrid Approach of Metaheuristics and Linear Programming. Journal of Mathematical Modelling and Algorithms, 5(1), 43-64.
23. Wascher, G., & Gau, T. (1996). Heuristics for the integer one-dimensional cutting stock problem: a computational study. OR Spectrum, 18(3), 131.