×

An iterative sequential heuristic procedure to a real-life 1.5-dimensional cutting stock problem. (English) Zbl 1136.90533

Summary: This paper addresses a real-life 1.5D cutting stock problem, which arises in a make-to-order plastic company. The problem is to choose a subset from the set of stock rectangles to be used for cutting into a number of smaller rectangular pieces so as to minimize total production cost and meet orders. The total production cost includes not only material wastage, as in traditional cutting stock problems, but also production time. A variety of factors are taken into account, like cutter knife changes, machine restrictions, due dates and other work in progress limitations. These restrictions make the combinatorial structure of the problem more complex. As a result, existing algorithms and mathematical models are no longer appropriate. Thus we developed a new 1.5D cutting stock model with multiple objectives and multi-constraints and solve this problem in an incomplete enumerative way. The computational results show that the solution procedure is easy to implement and works very well.

MSC:

90C59 Approximation methods and heuristics in mathematical programming
90C27 Combinatorial optimization
90B30 Production models
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Antonio, J.; Chauvet, F.; Chu, C.; Proth, J. M., The cutting stock problem with mixed objectives: Two heuristics based on dynamic programming, European Journal of Operational Research, 114, 395-402 (1999) · Zbl 0935.90029
[2] Belov, G., Scheithauer, G., 2003. Setup and open stacks minimization in one-dimensional stock cutting. Available from: <http://www.math.tu-dresden.de/ belov/publ.html; Belov, G., Scheithauer, G., 2003. Setup and open stacks minimization in one-dimensional stock cutting. Available from: <http://www.math.tu-dresden.de/ belov/publ.html · Zbl 1241.90070
[3] Coverdale, I.; Wharton, F., An improved heuristic procedure for a nonlinear cutting stock problem, Management Science, 23, 78-86 (1976)
[4] Chu, C. B.; Antonio, J., Approximation algorithms to solve real-life multicriteria cutting stock problems, Operations Research, 47, 4, 495-508 (1999) · Zbl 1041.90536
[5] de Carvalho, J. M.V. V.; Rodrigues, A. J.G., An LP-based approach to a two-stage cutting stock problem, European Journal of Operational Research, 84, 580-589 (1995) · Zbl 0912.90241
[6] Diegel, A.; Montocchio, E.; Schalkwyk, S., Setup minimizing conditions in the trim loss problem, European Journal of Operational Research, 95, 631-640 (1996) · Zbl 0926.90080
[7] Dowsland, K., Some experiments with simulated annealing techniques for packing problems, European Journal of Operational Research, 68, 389-399 (1993) · Zbl 0800.90729
[8] Dowsland, K. A.; Dowsland, W. B., Packing problems, European Journal of Operational Research, 56, 2-14 (1992) · Zbl 0825.90355
[9] Dyckhoff, H., A new linear programming approach to the cutting stock problem, Operations Research, 29, 1092-1104 (1981) · Zbl 0474.90059
[10] Dyckhoff, H., A typology of cutting and packing problems, European Journal of Operational Research, 44, 145-159 (1990) · Zbl 0684.90076
[11] Faero, O.; Pisinger, D.; Zachariasen, M., Guided local search for the three-dimensional bin packing problem, INFORMS Journal on Computing, 15, 267-283 (2003) · Zbl 1238.90112
[12] Gilmore, P. C.; Gomory, R. E., A linear programming approach to the cutting-stock problem, Operations Research, 9, 849-859 (1961) · Zbl 0096.35501
[13] 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
[14] Gilmore, P. C.; Gomory, R. E., Multistage cutting stock problems of two and more dimensions, Operations Research, 13, 94-120 (1965) · Zbl 0128.39601
[15] Gilmore, P. C.; Gomory, R. E., The theory and computation of knapsack functions, Operations Research, 14, 1045-1074 (1966) · Zbl 0173.21502
[16] Goulimis, C., Optimal solutions for the cutting stock problem, European Journal of Operational Research, 44, 2, 197-208 (1990) · Zbl 0684.90082
[17] Gradišar, M.; Kljajić, M.; Resinovič, G.; Jesenko, J., A sequential heuristic procedure for one-dimensional cutting, European Journal of Operational Research, 114, 557-568 (1999) · Zbl 0938.90058
[18] Haessler, R. W., A heuristic solution to a nonlinear cutting stock problem, Management Science, 17, B793-B803 (1971) · Zbl 0219.90021
[19] Haessler, R. W., Controlling cutting pattern changes in one-dimensional trim problems, Operations Research, 23, 483-493 (1975) · Zbl 0301.90030
[20] Haessler, R. W., A note on some computational modifications to the Gilmore-Gomory cutting stock algorithm, Operations Research, 28, 1001-1005 (1980) · Zbl 0441.90066
[21] Haessler, R. W.; Sweeney, P. E., Cutting stock problems and solution procedures, European Journal of Operational Research, 54, 141-150 (1991) · Zbl 0736.90062
[22] Hendry, L. C.; Fok, K. K.; Shek, K. W., Cutting stock and scheduling problem in the copper industry, Journal of the Operational Research Society, 47, 38-47 (1996) · Zbl 0843.90053
[23] Jakobs, S., On genetic algorithm for the packing of polygons, European Journal of Operational Research, 88, 165-181 (1996) · Zbl 0913.90229
[24] Johnson, G. M.R., Computers and Interactability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman and Company: W.H. Freeman and Company San Francisco
[25] Lodi, A.; Martello, S.; Vigo, D., Neighborhood search algorithm for the guillotine non-oriented two-dimensional bin packing problem, (Voss, S.; Martello, S.; Osman, I. H.; Roucairol, C., Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization (1998), Kluwer Academic Publishers: Kluwer Academic Publishers Boston), 125-139 · Zbl 0970.90079
[26] Lodi, A.; Martello, S.; Vigo, D., Approximation algorithms for the oriented two-dimensional bin packing problem, European Journal of Operational Research, 112, 158-166 (1999) · Zbl 0937.90121
[27] Lodi, A.; Martello, S.; Vigo, D., Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems, INFORMS Journal on Computing, 11, 345-357 (1999) · Zbl 1034.90500
[28] Lodi, A.; Martello, S.; Monaci, M., Two-dimensional packing problems: A survey, European Journal of Operational Research, 141, 2, 241-252 (2002) · Zbl 1081.90576
[29] McDiarmid, C., Pattern minimisation in cutting stock problems, Discrete Applied Mathematics, 98, 1-2, 121-130 (1999) · Zbl 0987.90085
[30] Nonas, S. L.; Thorstenson, A., A combined cutting-stock and lot-sizing problem, European Journal of Operational Research, 120, 2, 327-342 (2000) · Zbl 0946.91021
[31] Richard, V., Random search in the one-dimensional cutting stock problem, European Journal of Operational Research, 95, 1, 191-200 (1996) · Zbl 0953.90529
[32] Sinuany-Stern, Z.; Weiner, I., The one dimensional cutting stock problem using two objectives, Journal of the Operational Research Society, 45, 2, 231-236 (1994) · Zbl 0789.90062
[33] Sweeney, P. E.; Haessler, R. W., One-dimensional cutting stock decisions for rolls with multiple quality grades, European Journal of Operational Research, 44, 2, 224-231 (1990) · Zbl 0684.90077
[34] Washer, G., An LP-based approach to cutting stock problems with multiple objectives, European Journal of Operational Research, 44, 175-184 (1990)
[35] Zak, E. J., Row and column generation technique for a multistage cutting stock problem, Computers & Operations Research, 29, 9, 1143-1156 (2002) · Zbl 0994.90111
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.