Abstract
We consider the two-dimensional cutting stock problem that arises in many applications in industries. In recent industrial applications, it is argued that the setup cost for changing patterns becomes more dominant and it is impractical to use many different cutting patterns. Therefore, we consider the pattern restricted two-dimensional cutting stock problem, in which the total number of applications of cutting patterns is minimized while the number of different cutting patterns is given as a parameter n. For this problem, we develop local search algorithms. As the neighborhood size plays a crucial role in determining the efficiency of local search, we propose to use linear programming techniques for the purpose of restricting the number of solutions in the neighborhood. In this process, to generate a cutting pattern, it is required to place all the given products (rectangles) into the stock sheet (two-dimensional area) without mutual overlap. For this purpose, we develop a heuristic algorithm using an existing rectangle packing algorithm with the sequence pair coding scheme. Finally, we generate random test instances of this problem and conduct computational experiments, to evaluate the effectiveness of the proposed algorithms.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
F. Chauny and R. Loulou, “LP-based method for the multi-sheet cutting stock problem,” INFOR, Vol. 32, 1994, pp. 253–264.
V.D. Cung, M. Hifi and B. Le Cun, “Constrained two-dimensional cutting stock problems a best-first branch-and-bound algorithm,” International Transactions in Operational Research, Vol. 7, 2000, pp. 185–210.
A.A. Farley, “Practical adaptations of the Gilmore-Gomory approach to cutting stock problems,” OR Spectrum, Vol. 10, 1998, pp. 113–123.
H. Foerster and G. Wäscher, “Pattern reduction in one-dimensional cutting stock problems,” International Journal of Production Research, Vol. 38, 2000, pp. 1657–1676.
M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, 1979).
P.C. Gilmore and R.E. Gomory, “A linear programming approach to the cutting-stock problem,” Operations Research, Vol. 9, 1961, pp. 849–859.
P.C. Gilmore and R.E. Gomory, “A linear programming approach to the cutting-stock problem-Part II,” Operations Research, Vol. 11, 1963, pp. 863–888.
P.C. Gilmore and R.E. Gomory, “Multistage cutting stock problems of two and more dimensions,” Operations Research, Vol. 13, 1965, pp. 94–120.
R.E. Haessler, “Controlling cutting pattern changes in one-dimensional trim problems,” Operations Research, Vol. 23, 1975, pp. 483–493.
S. Imahori, M. Yagiura and T. Ibaraki, “Local search algorithms for the rectangle packing problem with general spatial costs,” Mathe-matical Programming, Vol. 97, 2003, pp. 543–569.
S. Imahori, M. Yagiura and T. Ibaraki, “Improved local search algorithms for the rectangle packing problem with general spatial costs,” European Journal of Operational Research (to appear).
A. Lodi, S. Martello and D. Vigo, “Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems,” INFORMS Journal on Computing, Vol. 11, 1999, pp. 347–357.
O. Marcotte, “The cutting stock problem and integer rounding,” Mathematical Programming, Vol. 33, 1985, pp. 82–92.
S. Martello and D. Vigo, “Exact solution of the two-dimensional finite bin packing problem,” Management Science, Vol. 44, 1998, pp. 388–399.
H. Murata, K. Fujiyoshi, S. Nakatake and Y. Kajitani, “VLSI module placement based on rectangle-packing by the sequence-pair,” IEEE Transactions on Computer Aided Design, Vol. 15, 1996, pp. 1518–1524.
J. Riehme, G. Scheithauer and J. Terno, “The solution of two-stage guillotine cutting stock problems having extremely varying order demands,” European Journal of Operational Research, Vol. 91, 1996, pp. 543–552.
S. Umetani, M. Yagiura and T. Ibaraki, “An LP-based local search to the one dimensional cutting stock problem using a given number of cutting patterns,” IEICE Transactions on Fundamentals, Vol. E86-A, 2003, pp. 1093–1102.
R. Alvarez-Valdés, A. Parajón and J.M. Tamarit, “A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems,” Computers & Operations Research, Vol. 29, 2002, pp. 925–947.
R. Alvarez-Valdés, A. Parajón and J.M. Tamarit, “A computational study of LP-based heuristic algorithms for two-dimensional guillotine cutting stock problems,” OR Spectrum, Vol. 24, 2002, pp. 179–192.
F. Vanderbeck, “Computational study of a column generation algorithm for bin packing and cutting stock problems,” Mathematical Programming, Vol. 86, 1999, pp. 565–594.
F. Vanderbeck, “A nested decomposition approach to a three-stage, two-dimensional cutting-stock problem,” Management Science, Vol. 47, 2001, pp. 864–879.
S. Zionts, “The criss-cross method for solving linear programming problems,” Management Science, Vol. 15, 1969, pp. 426–445.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer Science+Business Media, Inc.
About this chapter
Cite this chapter
Imahori, S., Yagiura, M., Umetani, S., Adachi, S., Ibaraki, T. (2005). Local Search Algorithms for the Two-Dimensional Cutting Stock Problem with a Given Number of Different Patterns. In: Ibaraki, T., Nonobe, K., Yagiura, M. (eds) Metaheuristics: Progress as Real Problem Solvers. Operations Research/Computer Science Interfaces Series, vol 32. Springer, Boston, MA. https://doi.org/10.1007/0-387-25383-1_8
Download citation
DOI: https://doi.org/10.1007/0-387-25383-1_8
Publisher Name: Springer, Boston, MA
Print ISBN: 978-0-387-25382-4
Online ISBN: 978-0-387-25383-1
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)