刘明明¹, 童小娇², 戴彧虹³

1. 湘潭大学数学与计算科学学院, 湖南湘潭 411105;
2. 湖南第一师范学院数学与计算科学学院, 长沙 410000;
3. 中国科学院数学与系统科学研究院, 北京 100190

收稿日期:2015-11-12出版日期:2016-08-15发布日期:2016-09-08


基金资助:童小娇受国家自然科学基金（批准号11171095和71371065）资助；戴彧虹受国家自然科学基金（批准号11331012和71331001）以及973项目基金（No.2015CB856000）资助.

RECENT DEVELOPMENTS IN ALGORITHMS FOR PACKING PROBLEMS

Liu Mingming¹, Tong Xiaojiao², Dai Yuhong³

1. College of Mathematics and Computational Science, Xiangtan University, Xiangtan 411105, China;
2. College of Mathematics and Computational Science, Hunan First Normal University, Changsha 410000, China;
3. Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China

Received:2015-11-12Online:2016-08-15Published:2016-09-08







摘要
图/表
参考文献
相关文章
编辑推荐
-->Metrics
本文评论

装箱问题在经济社会发展中扮演着重要的角色，该问题研究的是寻找较好的布局方式，尽可能实现利益的最大化.装箱问题具有NP-难性质，其理论和应用研究存在一定的挑战，但因其有广泛的应用背景而受到研究者高度的关注.本文主要总结近几十年来装箱问题的研究成果，特别针对一维、二维和三维单目标装箱问题和算法，以及多目标装箱问题的算法进行概括和总结，并提出装箱问题算法上有待进一步的研究工作.
MR(2010)主题分类:
90C11
97N80

分享此文:

()

[1] Codd E F. Multiprogram scheduling:parts 3 and 4. scheduling algorithm and external constraints[J]. Comm. Acm., 1960, 3(7):413-418. [2] Gilmore P C, Gomory R E. A linear programming approach to the cutting stock problem[J]. Oper. Res., 1961, 9:849-859. [3] Dyckhoff H, Scheithauer G, Terno J. Cutting and packing[M]. Ann. Bibliograph. Comb. Optimi. Wiley, 1997:393-413. [4] Johnson D S. Near-optimal bin packing algorithms[M]. Massch. Inst. Tech., 1973. [5] Krause K L, Shen Y Y, Schwetman H D. Analysis of several task-scheduling algorithms for a model of multiprogramming computer systems[J]. Assoc. Comput. Math., 1975, 22:522-550. [6] Maruyama K, Chang S K, Tang D T. A general packing algorithm for multidimensional resource requirements[J]. Int. J. Comput. Infor. Sci., 1977, 6:131-149. [7] Garey M R, Johnson D S. Approximation algorithms for bin-packing problems-A survey[J]. Comb. Optimi., 1981, 266:147-172. [8] Wee T S, Magazine M J. Assembly line balancing as generalized bin-packing[J]. Oper. Res. Lett., 1982, 1(2):56-58. [9] Bortfeldt A, Wäscher G. Constrains in container loading:a state-of-the-art review[J]. Eur. J. Oper. Res., 2013, 229(1):1-20. [10] Burke E, Kendall G. Applying evolutionary algorithms and the no fit polygon to the nesting problem[J]. Int. Confer. Art. Int., 1999, 1:51-57. [11] Júnior B A, Pinheiro P R. Dealing with nonregular shapes packing[J]. Math. Prob. Eng., 2014, 2014:1-11. [12] Zhang D F, Deng A S. An efective hybrid algorithm for the problem of packing circles into a larger containing circle[J]. Comput. Oper. Res., 2005, 32:1941-1951. [13] Hales T C. The sphere packing problem[J]. J. Comput. Appl. Math., 1992, 44(1):41-76. [14] Liu J F, Yao Y L, Zheng Y, et al. An effective hybrid algorithm for the circles and spheres packing problems[J]. Comput. optimi. Appl., 2009, 5573:135-144. [15] Hifi M, Yousef L. A dichotomous search-based heuristic for the three-dimensional sphere packing problem[J]. Cogent. Eng., 2015, 2:538-549. [16] Conway J H, Goodman S C, Sloane N J A. Recent progress in sphere packing[J]. Current. Deve. Math., 1999, 1:1-39. [17] Wäscher G, Haußner H, Schumann H. An improved typology of cutting and packing problems[J]. Eur. J. Oper. Res., 2007, 183:1109-1130. [18] Garey M R, Johnson D S. Computers and intractibility:a guild to the theory if NPcompleteness[J]. SIAM., 1979. [19] Johnson D S. Fast algorithms for bin packing[J]. J. Comput. Syst. Sci., 1974, 8:272-314. [20] Robson J M. Worst case fragmentation of first-fit and best-fit storage allocation strategies[J]. Comput. J., 1977, 20:242-244. [21] Karmarkar N, Karp R M. An efficient approximation scheme for the one-dimensional bin packing problem[J]. IEEE. Comput. Soc., 1982, 5:312-320. [22] Johnson D S, Demers A, Ullman J D, Garey M R, Graham R L. Worst-case performance bounds for simple one-dimensional packing algorithms[J]. SIAM. J. Comput., 1974, 3(4):299-325. [23] Coffman E G, Garey M R, Johnson D S. Approxiamtion algorithms for bin packing:an updated survey[J]. Int. Cen. Math. Sci., 1984, 284:49-106. [24] Galambos G, Wocgingcr G J. On line bin pacing-a restrieted suvrey[J]. Math. Oper. Res., 1995, 42(1):25-45. [25] Ullman J D. The performance of a memory allocation algorithm[J]. Tech. Rep. Prin. Univer., 1971. [26] Dósa G, Sgall J. First fit bin packing:a tight analysis[J]. Int. Sym. Theore. Aspects. Comput. Sci., 2013, 13:538-549. [27] Coffman E G, Csirik J, Galambos G. Bin packing approximation algorithms:survey and classification. Hand. Comb. Optimi., 2013, 1:455-531. [28] Gilmore P C, Gomory R E. Multistage cutting problems of two-dimensional[J]. Oper. Res., 1965, 13:94-119. [29] Gilmore P C, Gomory R E. A line programming approach to the cutting stock problem[J]. Oper. Res., 1961, 9:849-859. [30] Lodi A, Giovanni M, Martello S. Algorithms for two-dimensional bin packing and assignment problems[M]. Univer. Degli. Studi. Di. Bologna., 2000:1-80. [31] Fowler R J, Paterson M S, Tatimoto S L. Optimal packing and covering in the plane are NPcomplete[J]. Inform. Pro. Lett., 1981, 12:133-137. [32] Hopper E, Turton B. A review of the appplication of meta-heuristic algorithms to 2D strip packing problems[J]. Art. Itell. Rev., 2001, 16:257-300. [33] Lai K K, Chan J W M. Developing a simulated annealing algorithm for the cutting stock problem[J]. Comput. Indust. Eng., 1996, 32(1):115-127. [34] Hage T, Begnum K, Yazidi A. Saving the planet with bin packing-experiences using 2D and 3D bin packing of virtual machines for greener cloud[J]. IEEE, 2014:240-245. [35] Li J W, Lim A. A bidirectional building approach for the 2D constrained guillotine knapsack packing problem[J]. Disc. Optimi., 2015, 242:63-75. [36] Hopper E, Turton B. A genetic algorithm for a 2D industrial packing problem[J]. Comput. Indust. Eng., 1999, 37:375-378. [37] Freund A, Naor J. Approximating the advertisement placement problem[J]. J. Sched., 2004, 7(5):365-374. [38] Lodi A, Martello S, Vigo D. Recent advances on two-dimensional bin packing problems[J]. Disc. Appl. Math., 2002, 123:379-396. [39] Hinxman A I. The trim loss and assortment problems[J]. Eur. J. Oper. Res., 1980, 5:8-18. [40] Coffman E G, Garey M R, Johnson D S. Approximation algorithms for bin packing:an updated survey[J]. Int. Cen. Mech. Sci., 1984, 284:49-106. [41] Polyakovsky S, Hallah R. An agent-based approach to the two-dimensional guillotine bin packing problem[J]. Eur. J. Oper. Res., 2009, 192:767-781. [42] Martello S, Vigo D. Exact solution of the two-dimensional finite bin packing problem[J]. Manage. Sci., 1998, 44(3):388-399. [43] Fekete S P, Schepers J. On more-dimensional packing Ⅲ:Exact algorithms[J]. Ang. Math. Und. Inform. Univer. zu Kyöln., 2000. [44] Fekete S P, Schepers J. On more-dimensional packing I:Modeling[J]. Ang. Math. Und. Inform. Univer. zu Kyöln, 2000. [45] Fekete S P, Schepers J. A new exact algorithm for general orthogonal d-dimensional knapsack problems[J]. Comput. Sci., 1997, 1284:144-156. [46] Fekete S P, Schepers J, Cvander Veen J. An exact algorithm for higher-dimensional orthogonal packing[J]. Oper. Res., 2007, 55(3):569-587. [47] Pisinger D,Sigurd M. Using decomposition techniques and constraint programming for solving the two-dimensional bin packing problem[J]. Inform. J. Comput., 2007, 19(1):36-51. [48] Caprara A, Monaci M. On the 2-dimensional knapsack problem[J]. Oper. Res. Lett., 2004, 32(1):5-14. [49] Martello S, Monaci M, Vigo D. An exact approach to the strip packing problem[J]. Inform. J. Comput., 2003, 3(15):310-319. [50] Alvarez-Valdes R, Parreño F, Tamarit J M. A branch and bound algorithm for the strip packing problem[J]. OR. Spectrum., 2009, 31:431-459. [51] Muritiba F, Iori A E M, Malaguti E, Toth P. Algorithms for the bin packing problem with conflicts[J]. Inform. J. Comput., 2010, 22(3):401-415 [52] Elhedhli S, Li L Z, Gzara M. A branch-and-price algorithm for the bin packing problem with conflicts[J]. Inform. J. Comput., 2011, 23(3):404-415. [53] Han T, Diehr G, Jack S. Multiple-type, two-dimensional bin packing problems:applications and algorithms[J]. Ann. Oper. Res., 1994, 50(1):239-261. [54] Sadykov R, Vanderbeck F. Bin packing with conflicts:a generic branch-and-price algorithm[J]. Inform. J. Comput., 2012, 25(2):244-255. [55] Bekrar A, Kacem I, Chu C B. A comparative study of exact algorithms for the two dimensional strip packing problem[J]. J. Indust. Syst. Eng., 2007, 1(2):151-170 [56] Gary P R. Determinisic scheduling theory[M]. Chapman Hall, 1995. [57] Kou L T, Markowsky G. Multidimensional bin packing algorithms[J]. J. Res. Deve., 1977, 21(5):443-448. [58] Csirik J, Woeginger G. On-line packing and covering problems[J]. Lect. Not. Comput. Sci., 1998, 1442:147-177. [59] Garey M R, Graham R L, Johnson D S. Resource constrained scheduling as generalized bin packing[J]. J. Comb. Th. Set. A., 1976, 21:257-298. [60] Coppersmith D, Raghavan P. Multidimensional on-line bin packing:algorithms and worst case analysis[J]. Oper. Res. Lett., 1989, 8:17-20. [61] Csirik J, Vliet A V. An on-line algorithm for multidimensional bin packing[J]. Oper. Res. Lett., 1993, 13:149-158. [62] Baker B S, Schwartz J S. Shelf algorithms for two-dimensional packing problems[J]. SIAM. J. Comput., 1983, 12:508-525. [63] Berkey J O, Wang P Y. Two dimensional finite bin packing algorithms[J]. J. Oper. Res., 1987, 38:4323-4329. [64] Dósa G, Li R, Han X, Tuza Z. Tight absolute bound for first fit decreasing bin-packing:FFD(L)<11/9 OPT(L)+6/9[J]. Theor. Comput. Sci., 2013, 510:13-61. [65] Lodi A, Martello S, Monaci M. Two-dimensional packing problems:a survey[J]. Eur. J. Oper. Res., 2002, 141:241-252. [66] Lodi A, Martello S, Vigo D. Models and bounds for two-dimensional level packing problems[J]. J. Comb. Optimi., 2004, 8:363-379. [67] Dell,Amio M, Martello S. Optimal scheduling of tasks on identical parallel processors[J]. ORSA. J. Comput., 1995, 7(2):191-200. [68] Chung F R K, Gary M R, Johnson D S. On packing two-dimension bins[J]. SIAM. J. Algcb. Dis. Math., 1982, 3(1):66-76. [69] Fekete S P, Schepers J. New classes of lower bounds for bin packing problems, in:integer programming and combinatorial optimization[J]. Comput. Sci., 1998, 1412:257-270. [70] Lueker G S. Bin packing withitems uniformly distributed over intervals[a, b] [J]. Comput. Sci., 1983, 7-9:289-297. [71] Baker B S, Coffman E G, Rivest R I. Orthogonal packing in two dimensions[J]. SIAM. J. Comput., 1980, 9:846-855. [72] Brown, D J. An improved BL lower bound[J]. Inform Pro. Lett., 1980, 11:37-39. [73] Chazelle B. The bottom-left bin packing heuristic:an efficient implementation[J]. IEEE. Trans.comput., 1983, 32:697-707. [74] Lodi A, Martello S, Vigo D. Heuristics and metaheuristics approach for a class of two-dimensional bin packing problems[J], Inform. J. Comput., 1999, 11:345-357.. [75] Khanafer A, Clautiaux F, Talbi E. Tree decomposition based heuristics for the two-dimensional bin packing problem with conflicts[J]. Comput. Oper. Res., 2012, 39:54-63. [76] Zhang D F, Kang Y, Deng A S. A new heuristic recursive algorithm for the strip rectangular packing problem[J]. Comput. Oper. Res., 2006, 33:2209-2217. [77] Zhang D F, Han S H, Jiang Y. A personification heuristic algorithm for the orthogonal stockcutting problem[J]. Comput. Oper. Res., 2007, 33:911-916. [78] Wu Y L, Huang W Q, Lau S, et al. An effective quasi-human based heuristic for solving the rectangle packing problem[J]. Eur. J. Oper. Res., 2002, 141(2):341-358. [79] Huang W Q, Chen D B, Xu R C. A new heuristic algorithm for rectangle packing[J]. Comput. Oper. Res., 2007, 34:3270-3280. [80] Cui Y D, Yang Y L, Cheng X, Song P H. A recursive branch-and-bound algorithm for the rectangular guillotine strip packing problem[J]. Comput. Oper. Res., 2008, 25:1281-1291. [81] Martello S, Monaci M, Vigo D. An exact approach to the strip packing problem[J]. Inform. J. Comput., 2003, 25(3):310-319.

No related articles found!

--> -->

	阅读次数
	全文
	摘要
	Cited
	Shared

PDF全文下载地址:

http://www.computmath.com/jssx/CN/article/downloadArticleFile.do?attachType=PDF&id=157