Mathematical models for the two-dimensional variable-sized cutting stock problem in the home textile industry. (English) Zbl 1541.90310
Summary: In this paper, we consider the two-dimensional Variable-Sized Cutting Stock Problem (2D-VSCSP) with guillotine constraint, applied to the home textile industry. This is a challenging class of real-world problems where, given a set of predefined widths of fabric rolls and a set of piece types, the goal is to decide the widths and lengths of the fabric rolls to be produced, and to generate the cutting patterns to cut all demanded pieces. Each piece type considered has a rectangular shape with a specific width and length and a fixed demand to be respected. The main objective function is to minimize the total amount of the textile materials produced/cut to satisfy the demand. According to G. Wäscher et al. [ibid. 183, No. 3, 1109–1130 (2007; Zbl 1278.90347)], the addressed problem is a Cutting Stock Problem (CSP), as the demand for each item is greater than one. However, in the real-world application at stake, the demand for each item type is not very high (below ten for all item types). Therefore, addressing the problem as a Bin-Packing Problem (BPP), in which all items are considered to be different and have a unitary demand, was a possibility. For this reason, two approaches to solve the problems were devised, implemented, and tested: (1) a CSP model, based on the well-known A. Lodi and M. Monaci [Math. Program. 94, No. 2–3 (B), 257–278 (2003; Zbl 1030.90064)] model (3 variants), and (2) an original BPP-based model. Our research shows that, for this level of demand, the new BPP model is more competitive than CSP models. We analyzed these different models and described their characteristics, namely the size and the quality of the linear programming relaxation bound for solving the basic mono-objective variant of the problem. We also propose an \(\epsilon\)-constraint approach to deal with a bi-objective extension of the problem, in which the number of cutting patterns used must also be minimized. The quality of the models was evaluated through computational experiments on randomly generated instances, yielding promising results.
MSC:
| 90C27 | Combinatorial optimization |
| 90C10 | Integer programming |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
cutting stock problem; variable-sized stock; integer linear programming; bi-objective optimization problem; home textile industrySoftware:
BPPLIBReferences:
| [1] | Aliano Filho, A.; Moretti, A. C.; Pato, M. V., A comparative study of exact methods for the bi-objective integer one-dimensional cutting stock problem, Journal of the Operational Research Society, 1-18 (2017) |
| [2] | Alves, C.; De Carvalho, J. V., A stabilized branch-and-price-and-cut algorithm for the multiple length cutting stock problem, Computers & Operations Research, 35, 4, 1315-1328 (2008) · Zbl 1163.90702 |
| [3] | IOP Publishing |
| [4] | Belov, G.; Scheithauer, G., A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths, European Journal of Operational Research, 141, 2, 274-294 (2002) · Zbl 1081.90590 |
| [5] | Belov, G.; Scheithauer, G., A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting, European Journal of Operational Research, 171, 1, 85-106 (2006) · Zbl 1091.90080 |
| [6] | Bouaine, A.; Lebbar, M.; Ha, M. A., Minimization of the wood wastes for an industry of furnishing: A two dimensional cutting stock problem, Management and Production Engineering Review (2018) |
| [7] | Brooks, L.; Smith, C.; Stone, A., WT Tutte the dissection of rectangles into squares, Duke Mathematical Journal, 7, 312-340 (1940) · Zbl 0024.16501 |
| [8] | Cintra, G. F.; Miyazawa, F. K.; Wakabayashi, Y.; Xavier, E. C., Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation, European Journal of Operational Research, 191, 1, 61-85 (2008) · Zbl 1146.90499 |
| [9] | Côté, J.-F.; Iori, M., The meet-in-the-middle principle for cutting and packing problems, INFORMS Journal on Computing, 30, 4, 646-661 (2018) · Zbl 1528.90211 |
| [10] | Cui, Y., Heuristic and exact algorithms for generating homogenous constrained three-staged cutting patterns, Computers & Operations Research, 35, 1, 212-225 (2008) · Zbl 1149.90428 |
| [11] | Cui, Y.; Liu, Z., C-sets-based sequential heuristic procedure for the one-dimensional cutting stock problem with pattern reduction, Optimization Methods and Software, 26, 1, 155-167 (2011) · Zbl 1226.90087 |
| [12] | Cui, Y.; Yang, L.; Zhao, Z.; Tang, T.; Yin, M., Sequential grouping heuristic for the two-dimensional cutting stock problem with pattern reduction, International Journal of Production Economics, 144, 2, 432-439 (2013) |
| [13] | 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, 6, 677-685 (2008) |
| [14] | Cui, Y.; Zhong, C.; Yao, Y., Pattern-set generation algorithm for the one-dimensional cutting stock problem with setup cost, European Journal of Operational Research, 243, 2, 540-546 (2015) · Zbl 1346.90610 |
| [15] | Delorme, M.; Iori, M.; Martello, S., Bin packing and cutting stock problems: Mathematical models and exact algorithms, European Journal of Operational Research, 255, 1, 1-20 (2016) · Zbl 1346.90700 |
| [16] | Delorme, M.; Iori, M.; Martello, S., Logic based benders’ decomposition for orthogonal stock cutting problems, Computers & Operations Research, 78, 290-298 (2017) · Zbl 1391.90514 |
| [17] | Delorme, M.; Iori, M.; Martello, S., Bpplib: A library for bin packing and cutting stock problems, Optimization Letters, 12, 2, 235-250 (2018) · Zbl 1401.90183 |
| [18] | Dolan, E. D.; Moré, J. J., Benchmarking optimization software with performance profiles, Mathematical Programming, 91, 2, 201-213 (2002) · Zbl 1049.90004 |
| [19] | Dyckhoff, H., A typology of cutting and packing problems, European Journal of Operational Research, 44, 2, 145-159 (1990) · Zbl 0684.90076 |
| [20] | Dyckhoff, H.; Scheithauer, G.; Terno, J., Cutting and packing, Annotated bibliographies in combinatorial optimization, 393-412 (1997) · Zbl 1068.90509 |
| [21] | Ehrgott, M.; Gandibleux, X., Multiobjective combinatorial optimization’ theory, methodology, and applications, Multiple criteria optimization: State of the art annotated bibliographic surveys, 369-444 (2003), Springer · Zbl 1095.90593 |
| [22] | ESICUP (1988). Euro special interest group on cutting and packing https://www.euro-online.org/websites/esicup/. |
| [23] | Faina, L., An application of simulated annealing to the cutting stock problem, European Journal of Operational Research, 114, 3, 542-556 (1999) · Zbl 0938.90057 |
| [24] | Faina, L., A global optimization algorithm for the three-dimensional packing problem, European Journal of Operational Research, 126, 2, 340-354 (2000) · Zbl 0971.90071 |
| [25] | Foerster, H.; Wäscher, G., Pattern reduction in one-dimensional cutting stock problems, International Journal of Production Research, 38, 7, 1657-1676 (2000) · Zbl 0944.90546 |
| [26] | Furini, F.; Malaguti, E., Models for the two-dimensional two-stage cutting stock problem with multiple stock size, Computers & Operations Research, 40, 8, 1953-1962 (2013) · Zbl 1348.90487 |
| [27] | Furini, F.; Malaguti, E.; Durán, R. M.; Persiani, A.; Toth, P., A column generation heuristic for the two-dimensional two-staged guillotine cutting stock problem with multiple stock size, European Journal of Operational Research, 218, 1, 251-260 (2012) · Zbl 1244.90191 |
| [28] | Furini, F.; Malaguti, E.; Thomopulos, D., Modeling two-dimensional guillotine cutting problems via integer programming, INFORMS Journal on Computing, 28, 4, 736-751 (2016) · Zbl 1355.90081 |
| [29] | Garey, M. R.; Johnson, D. S., Computers and intractability: A guide to the theory of NP-completeness, vol. 174 (1979), Freeman San Francisco · Zbl 0411.68039 |
| [30] | Gilmore, P. C.; Gomory, R. E., Multistage cutting stock problems of two and more dimensions, Operations Research, 13, 1, 94-120 (1965) · Zbl 0128.39601 |
| [31] | Goulimis, C.; Olivera, A., KBP: A new pattern reduction heuristic for the cutting stock problem, OR 59: OR Society Annual Conference, 25-43 (2017) |
| [32] | Hadj Salem, K.; Kieffer, Y., New symmetry-less ilp formulation for the classical one dimensional bin-packing problem, International computing and combinatorics conference, 423-434 (2020), Springer · Zbl 07336123 |
| [33] | Hifi, M.; Roucairol, C., Approximate and exact algorithms for constrained (un) weighted two-dimensional two-staged cutting stock problems, Journal of Combinatorial Optimization, 5, 4, 465-494 (2001) · Zbl 1135.90389 |
| [34] | Hwang, C.-L.; Masud, A. S.M., Multiple objective decision making’ methods and applications: A state-of-the-art survey, vol. 164 (2012), Springer Science & Business Media |
| [35] | Iori, M.; de Lima, V. L.; Martello, S.; Miyazawa, F. K.; Monaci, M., Exact solution techniques for two-dimensional cutting and packing, European Journal of Operational Research, 289, 2, 399-415 (2021) · Zbl 1487.90556 |
| [36] | Kantorovich, L. V., Mathematical methods of organizing and planning production, Management Science, 6, 4, 366-422 (1960) · Zbl 0995.90532 |
| [37] | Kokten, E. S.; Sel, Ç., A cutting stock problem in the wood products industry: A two-stage solution approach, International Transactions in Operational Research, 29, 2, 879-907 (2022) · Zbl 07770683 |
| [38] | 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 |
| [39] | Lodi, A.; Monaci, M., Integer linear programming models for 2-staged two-dimensional knapsack problems, Mathematical Programming, 94, 2-3, 257-278 (2003) · Zbl 1030.90064 |
| [40] | Macedo, R.; Alves, C.; De Carvalho, J. V., Arc-flow model for the two-dimensional guillotine cutting stock problem, Computers & Operations Research, 37, 6, 991-1001 (2010) · Zbl 1178.90292 |
| [41] | Malaguti, E.; Durán, R. M.; Toth, P., Approaches to real world two-dimensional cutting problems, Omega, 47, 99-115 (2014) |
| [42] | Martello, S.; Toth, P., Knapsack problems: Algorithms and computer implementations (1990), John Wiley & Sons, Inc. · Zbl 0708.68002 |
| [43] | Martin, M.; Morabito, R.; Munari, P., A top-down cutting approach for modeling the constrained two-and three-dimensional guillotine cutting problems, Journal of the Operational Research Society, 1-15 (2020) |
| [44] | Miettinen, K., Nonlinear multiobjective optimization, vol. 12 (2012), Springer Science & Business Media |
| [45] | Mrad, M.; Meftahi, I.; Haouari, M., A branch-and-price algorithm for the two-stage guillotine cutting stock problem, Journal of the Operational Research Society, 64, 5, 629-637 (2013) |
| [46] | IOP Publishing |
| [47] | Octarina, S.; Juita, D. G.; Eliyati, N.; Bangun, P. B.J., Set covering model in solving multiple cutting stock problem, Science and Technology Indonesia, 5, 4, 121-130 (2020) |
| [48] | Oliveira, J. F.; Ferreira, J. S., A faster variant of the Gilmore and Gomory technique for cutting stock problems, JORBEL, 34, 1, 23-38 (1994) · Zbl 0815.90123 |
| [49] | Parreño, F.; Alvarez-Valdes, R., Mathematical models for a cutting problem in the glass manufacturing industry, Omega, 102432 (2021) |
| [50] | Pisinger, D.; Sigurd, M., Using decomposition techniques and constraint programming for solving the two-dimensional bin-packing problem, INFORMS Journal on Computing, 19, 1, 36-51 (2007) · Zbl 1241.90118 |
| [51] | Poldi, K. C.; Arenales, M. N., Heuristics for the one-dimensional cutting stock problem with limited multiple stock lengths, Computers & Operations Research, 36, 6, 2074-2081 (2009) · Zbl 1179.90292 |
| [52] | Puchinger, J.; Raidl, G. R., Models and algorithms for three-stage two-dimensional bin packing, European Journal of Operational Research, 183, 3, 1304-1327 (2007) · Zbl 1135.90029 |
| [53] | Russo, M.; Boccia, M.; Sforza, A.; Sterle, C., Constrained two-dimensional guillotine cutting problem: Upper-bound review and categorization, International Transactions in Operational Research, 27, 2, 794-834 (2020) · Zbl 07767414 |
| [54] | Scheithauer, G., Introduction to cutting and packing optimization: Problems, modeling approaches, solution methods, vol. 263 (2017), Springer |
| [55] | Silva, E.; Alvelos, F.; De Carvalho, J. V., An integer programming model for two-and three-stage two-dimensional cutting stock problems, European Journal of Operational Research, 205, 3, 699-708 (2010) · Zbl 1188.90181 |
| [56] | Silva, E.; Viães, C.; Oliveira, J. F.; Carravilla, M. A., Integrated cutting and production planning: A case study in a home textile manufacturing company, Operations research and big data, 213-220 (2015), Springer |
| [57] | Sumetthapiwat, S.; Intiyot, B.; Jeenanunta, C., A column generation on two-dimensional cutting stock problem with fixed-size usable leftover and multiple stock sizes, International Journal of Logistics Systems and Management, 35, 2, 273-288 (2020) |
| [58] | Cited By 73 · Zbl 1012.90045 |
| [59] | Cited By 82 · Zbl 1106.90373 |
| [60] | Vanderbeck, F., A nested decomposition approach to a three-stage, two-dimensional cutting-stock problem, Management Science, 47, 6, 864-879 (2001) · Zbl 1232.90326 |
| [61] | Wang, D.; Xiao, F.; Zhou, L.; Liang, Z., Two-dimensional skiving and cutting stock problem with setup cost based on column-and-row generation, European Journal of Operational Research (2020) · Zbl 1443.90304 |
| [62] | Wäscher, G.; Haußner, H.; Schumann, H., An improved typology of cutting and packing problems, European Journal of Operational Research, 183, 3, 1109-1130 (2007) · Zbl 1278.90347 |
| [63] | Wuttke, D. A.; Heese, H. S., Two-dimensional cutting stock problem with sequence dependent setup times, European Journal of Operational Research, 265, 1, 303-315 (2018) · Zbl 1374.90277 |
| [64] | Yanasse, H.; Limeira, M., A hybrid heuristic to reduce the number of different patterns in cutting stock problems, Computers and Operations Research, 33, 9, 2744-2756 (2006) · Zbl 1086.90067 |
| [65] | Yanasse, H. H.; Zinober, A. S.; Harris, R. G., Two-dimensional cutting stock with multiple stock sizes, Journal of the Operational Research Society, 42, 8, 673-683 (1991) · Zbl 0729.90755 |
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.
