پیوندهای مفید
آمار
| تعداد نشریات | 32 |
| تعداد شمارهها | 860 |
| تعداد مقالات | 8,355 |
| تعداد مشاهده مقاله | 52,928,238 |
| تعداد دریافت فایل اصل مقاله | 9,316,508 |
A polynomial mixed-integer linear programming model for two-dimensional guillotine strip packing problem | ||
| Journal of Mathematical Modeling | ||
| مقاله 11، دوره 13، شماره 2، مرداد 2025، صفحه 415-428 اصل مقاله (242.09 K) | ||
| نوع مقاله: Research Article | ||
| شناسه دیجیتال (DOI): 10.22124/jmm.2024.26164.2320 | ||
| نویسنده | ||
| Ashkan Fakhri* | ||
| Department of Mathematics, University of Science and Technology of Mazandaran, P.O. Box 4851878195, Behshahr, Iran | ||
| چکیده | ||
| A two-dimensional strip packing problem is the process of packing a set of rectangular items of given dimensions into a strip of bounded width and infinite height so that the used height of the strip is minimized. In the case that only guillotine packing is permitted, the problem is called the guillotine strip packing problem (GSPP). Guillotine packing commonly arises in different industries such as glass, steel, paper and wood. Nevertheless, there is a lack of explicit mathematical models for GSPP that can globally solve the problem. In this paper, a new mixed-integer programming model inspired by a so-called sequence sub-tour elimination technique for the traveling salesman problem (TSP) is presented as a relaxation of (non-staged) GSPP with orthogonal rotation. The proposed model is able to find good solutions (good upper bounds) for the optimal objective value and more importantly, it is a polynomial model of order $O(n^2)$, i.e. the number of decision variables (and constraints, as well) is a polynomial of order $O(n^2)$ in the number of the rectangular items ($n$). Numerical results show that the solutions obtained from the proposed model are superior to several existing heuristic algorithms in the literature. | ||
| کلیدواژهها | ||
| Packing؛ cutting؛ guillotine cut؛ polynomial model؛ mixed-integer programming | ||
| مراجع | ||
|
[1] R. Alvarez-Valdes, F. Parreno, J. M. Tamarit, A tabu search algorithm for a two-dimensional non- guillotine cutting problem, Eur. J. Oper. Res. 183 (2007) 1167–1182. [2] B.S. Baker, E.G. Coffman Jr, R.L. Rivest, Orthogonal packing in two dimensions, SIAM J. Comput. 9 (1980) 846–855. [3] M.A. Boschetti, A. Mingozzi, The two-dimensional finite bin packing problem. Part I: New lower bounds for the oriented case, 4OR 1 (2003) 27–42. [4] M.A. Boschetti, A. Mingozzi, The two-dimensional finite bin packing problem. Part II: New lower and upper bounds, 4OR 1 (2003) 135–147. [5] E.K. Burke, G. Kendall, G. Whitwell, A new placement heuristic for the orthogonal stock-cutting problem, Oper. Res. 52 (2004) 655–671. [6] P.M. Castro, I.E. Grossmann, From time representation in scheduling to the solution of strip packing problems, Comput. Chem. Eng. 44 (2012) 45–57. [7] P.M. Castro, J.F. Oliveira, Scheduling inspired models for two-dimensional packing problems, Eur. J. Oper. Res. 215 (2011) 45–56. [8] C.S. Chen, S. Sarin, R. Balasubramanian, A mixed-integer programming model for a class of as- sortment problems, Eur. J. Oper. Res. 65 (1993) 362–367. [9] H.I. Christensen, A. Khan, S. Pokutta, Approximation and online algorithms for multidimensional bin packing: A survey, Comput. Sci. Rev. 24 (2017) 63–79. [10] F. Furini, E. Malaguti, Models for the two-dimensional two-stage cutting stock problem with multi- ple stock size, Comput. Oper. Res. 40 (2013) 1953–1962. [11] F. Furini, E. Malaguti, R. M. Duran, A column generation heuristic for the two-dimensional two- staged guillotine cutting stock problem with multiple stock size, Eur. J. Oper. Res. 218 (2012) 251– 260. [12] F. Furini, E. Malaguti, D. Thomopulos, Modeling two-dimensional guillotine cutting problems via integer programming, INFORMS J. Comput. 28 (2016) 736–751. [13] Y.H. Huang, H.C. Lu, Y.C. Wang, Y.F. Chang, C.K. Gao, A global method for a two-dimensional cutting stock problem in the manufacturing industry, in Application of Decision Science in Business and Management, IntechOpen, 2020. [14] M. Iori, V.L. de Lima, S. Martello, F.K. Miyazawa, M. Monaci, Exact solution techniques for two- dimensional cutting and packing, Eur. J. Oper. Res. 289 (2021) 399–415. [15] M. Iori, S. Martello, M. Monaci, Metaheuristic Algorithms for the Strip Packing Problem, US: Springer, 2003. [16] T.W. Leung, C.K. Chan, M.D. Troutt, Application of a mixed simulated annealing-genetic algo- rithm for a 2D packing problem, Eur. J. Oper. Res. 145 (2003) 530–542. [17] H.L. Li, C.T. Chang, An approximately global optimization method for assortment problems, Eur. J. Oper. Res. 105 (1998) 604–612. [18] A. Lodi, S. Martello, D. Vigo, Models and bounds for two-dimensional level packing problems, J. Comb. Optim. 8 (2004) 363–379. [19] A. Lodi, M. Monaci, Integer linear programming models for 2-staged two-dimensional knapsack problems, Math. Program. 94 (2003) 257–278. [20] R. Macedo, C. Alves, J.M. Valerio de Carvalho, Arc-flow model for the two-dimensional guillotine cutting stock problem, Comput. Oper. Res. 37 (2010) 991–1001. [21] S. Martello, M. Monaci, D. Vigo, An exact approach to the strip-packing problem, INFORMS J. Comput. 15 (2003) 310–319. [22] M. Martin, R. Morabito, P. Munari, A bottom-up packing approach for modeling the constrained two-dimensional guillotine placement problem, Comput. Oper. Res. 115 (2020) 104851. [23] S.B. Messaoud, C. Chu, M.L. Espinouse, Characterization and modelling of guillotine constraints, Eur. J. Oper. Res. 191 (2008) 112–126. [24] C. Miller, A. Tucker, R. Zemlin, Integer programming formulations and travelling salesman prob- lems, J. ACM 7 (1960) 326–329. [25] M. Monaci, P. Toth, A set-covering-based heuristic approach for bin-packing problems, INFORMS J. Comput. 18 (2006) 71–85. [26] M. Mrad, An arc flow-based optimization approach for the two-stage guillotine strip cutting prob- lem, J. Oper. Res. Soc. 66 (2015) 1850–1859. [27] N. Ntene, J. van Vuuren, A survey and comparison of guillotine heuristics for the 2D oriented offline strip packing problem, Discrete Optim. 6 (2009) 174–188. [28] F. Parreno, R. Alvarez-Valdes, J.F. Oliveira, J.M. Tamarit, A hybrid GRASP/VND algorithm for two- and three-dimensional bin packing, Ann. Oper. Res. 179 (2010) 203–220. [29] J. Puchinger, G.R. Raidl, Models and algorithms for three-stage two-dimensional bin packing, Eur. J. Oper. Res. 183 (2007) 1304–1327. [30] C.D. Rodrigues, A.C. Cherri, S.A. de Araujo, Strip based compact formulation for two-dimensional guillotine cutting problems, Comput. Oper. Res. 149 (2023) 106044. [31] S.M. Shperling, Y.A. Kochetov, A knapsack problem for rectangles under center-of-gravity con- straints, J. Appl. Ind. Math. 16 (2022) 563–571. [32] E. Silva, F. Alvelos, J.M. Valerio de Carvalho, An integer programming model for two- and three- stage two-dimensional cutting stock problems, Eur. J. Oper. Res. 205 (2010) 699–708. [33] L. Wei, H. Qin, B. Cheang, X. Xu, An efficient intelligent search algorithm for the two-dimensional rectangular strip packing problem, Int. Trans. Oper. Res. 23 (2016) 65–92. | ||
|
آمار تعداد مشاهده مقاله: 263 تعداد دریافت فایل اصل مقاله: 351 |
||