经典一维装箱问题近似算法的研究进展

doi:10.15960/j.cnki.issn.1007-6093.2022.01.005

摘要/Abstract

摘要：

自20世纪70年代开始，随着计算复杂性理论的建立，近似算法逐渐成为组合优化的重要研究方向。作为第一批研究对象，装箱问题引起了组合优化领域学者的极大关注。装箱问题模型简单、拓展性强，广泛出现在各种带容量约束的资源分配问题中。除了在物流装载和材料切割等方面愈来愈重要的应用外，装箱算法的任何理论突破都关乎到整个组合优化领域的发展。直到今天，对装箱问题近似算法的研究仍如火如荼。本文主要针对一维模型，简述若干经典Fit算法的发展历程，分析基于线性规划松弛的近似方案的主要思路，总结当前的研究现状并对未来的研究提供一些参考建议。

关键词: 装箱问题, 近似算法, 线性规划松弛

Abstract:

With the emergence of computational complexity theory, the study of approximation algorithms has gradually become an important field in combinatorial optimization since the 1970s. As one of the classic combinatorial optimization problems, bin packing has attracted great attention. It can be widely found in various resource allocation problems with capacity constraints. Its more and more important applications including logistics loading and material cutting aside, any theoretical breakthrough of bin packing algorithms is related to the development of the whole combinatorial optimization. At present, the research on approximation algorithms of bin packing is still popular. This paper briefly introduces the process of some classic Fit algorithms, analyzes the main ideas of approximation schemes based on linear programming relaxation, reviews the state of the art, and provides some suggestions for future research.

Key words: bin packing, approximation algorithms, linear programming relaxation

中图分类号:

O221.7

陈婳, 张国川. 经典一维装箱问题近似算法的研究进展[J]. 运筹学学报, 2022, 26(1): 69-84.

Hua CHEN, Guochuan ZHANG. A survey on approximation algorithms for one dimensional bin packing[J]. Operations Research Transactions, 2022, 26(1): 69-84.

参考文献 49

1	Yue M Y . A simple proof of the inequality FFD (L) ≤ 11/9OPT (L) +1, ∀L for the FFD bin-packing algorithm[J]. Acta Mathematicae Applicatae Sinica, 1991, 7 (4): 321- 331. doi: 10.1007/BF02009683
2	Eisemann K . The trim problem[J]. Management Science, 1957, 3 (3): 279- 284. doi: 10.1287/mnsc.3.3.279
3	Ullman J D. The performance of a memory allocation algorithm[R]. Princeton: Princeton University, 1971.
4	Johnson D S. Near-optimal bin packing algorithms[D]. Cambridge: Massachusetts Institute of Technology, 1973.
5	Garey M R, Johnson D S. Approximation algorithms for bin packing problems: A survey[M]//Analysis and Design of Algorithms in Combinatorial Optimization, New York: Springer, 1981: 147-172.
6	Coffman E G, Garey M R, Johnson D S. Approximation algorithms for bin-packing-an updated survey[M]//Algorithm Design for Computer System Design, New York: Springer, 1984: 49-106.
7	Coffman E G , Garey M R , Johnson D S . Approximation algorithms for bin packing: A survey[J]. Approximation Algorithms for NP-hard Problems, 1996, 46- 93.
8	Coffman E G, Csirik J, Galambos G, et al. Bin packing approximation algorithms: Survey and classification[M]. Handbook of Combinatorial Optimization, 2013: 455-531.
9	Johnson D S . Fast algorithms for bin packing[J]. Journal of Computer and System Sciences, 1974, 8 (3): 272- 314. doi: 10.1016/S0022-0000(74)80026-7
10	Johnson D S , Demers A , Ullman J D , et al. Worst-case performance bounds for simple onedimensional packing algorithms[J]. SIAM Journal on Computing, 1974, 3 (4): 299- 325. doi: 10.1137/0203025
11	Garey M R , Graham R L , Johnson D S , et al. Resource constrained scheduling as generalized bin packing[J]. Journal of Combinatorial Theory, Series A, 1976, 21 (3): 257- 298. doi: 10.1016/0097-3165(76)90001-7
12	Dósa G, Sgall J. First fit bin packing: A tight analysis[C]//Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS), 2013: 538-549.
13	Dósa G, Sgall J. Optimal analysis of best fit bin packing[C]//Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), 2014: 429-441.
14	Csirik J , Imreh B . On the worst-case performance of the NkF bin-packing heuristic[J]. Acta Cybernetica, 1989, 9 (2): 89- 105.
15	Mao W . Tight worst-case performance bounds for next-k-fit bin packing[J]. SIAM Journal on Computing, 1993, 22 (1): 46- 56. doi: 10.1137/0222004
16	Mao W . Besk-k-Fit bin packing[J]. Computing, 1993, 50 (3): 265- 270. doi: 10.1007/BF02243816
17	Zhang G , Yue M . Tight performance bound of AFBk bin packing[J]. Acta Mathematicae Applicatae Sinica, 1997, 13 (4): 443- 446. doi: 10.1007/BF02009554
18	Csirik J , Johnson D S . Bounded space on-line bin packing: Best is better than first[J]. Algo rithmica, 2001, 31 (2): 115- 138.
19	Lee C C , Lee D T . A simple on-line bin-packing algorithm[J]. Journal of the ACM, 1985, 32 (3): 562- 572. doi: 10.1145/3828.3833
20	Galambos G . Parametric lower bound for on-line bin-packing[J]. SIAM Journal on Algebraic Discrete Methods, 1986, 7 (3): 362- 367. doi: 10.1137/0607041
21	Balogh J , Békési J , Dósa G , et al. A new lower bound for classic online bin packing[J]. Algorithmica, 2021, 83 (7): 2047- 2062. doi: 10.1007/s00453-021-00818-7
22	Balogh J, Békési J, Dósa G, et al. A new and improved algorithm for online bin packing[C]//Proceedings of the 26th European Symposium on Algorithms (ESA), 2018: 1-5: 14.
23	Baker B S , Coffman E G . A tight asymptotic bound for next-fit-decreasing bin-packing[J]. SIAM Journal on Algebraic Discrete Methods, 1981, 2 (2): 147- 152. doi: 10.1137/0602019
24	Garey M R, Graham R L, Ullman J D. Worst-case analysis of memory allocation algorithms[C]//Proceedings of the 4th Annual ACM Symposium on Theory of Computing (STOC), 1972: 143-150.
25	Baker B S . A new proof for the first-fit decreasing bin-packing algorithm[J]. Journal of Algo rithms, 1985, 6 (1): 49- 70. doi: 10.1016/0196-6774(85)90018-5
26	Li R , Yue M Y . The proof of FFD (L) 611=9OPT (L) +7=9[J]. Chinese Science Bulletin, 1997, 42 (15): 1262- 1265. doi: 10.1007/BF02882754
27	Dósa G. The tight bound of first fit decreasing bin-packing algorithm is FFD (I)611=9OPT (I)+6=9[C]//International Symposium on Combinatorics, Algorithms, Probabilistic and Experimen tal Methodologies, 2007: 1-11.
28	Garey M R , Johnson D S . Computers and Intractability: A Guide to the Theory of NP Completeness[M]. New York: WH Freeman and Company, 1979.
29	Zhang G , Cai X , Wong C K . Linear time-approximation algorithms for bin packing[J]. Oper ations Research Letters, 2000, 26 (5): 217- 222. doi: 10.1016/S0167-6377(99)00077-2
30	Fernandez de la Vega W , Lueker G S . Bin packing can be solved within 1+ "ε" in linear time[J]. Combinatorica, 1981, 1 (4): 349- 355. doi: 10.1007/BF02579456
31	Williamson D P , Shmoys D B . The Design of Approximation Algorithms[M]. Cambridge: Cam bridge University press, 2011.
32	Grötschel M , Lovász L , Schrijver A . The ellipsoid method and its consequences in combinatorial optimization[J]. Combinatorica, 1981, 1 (2): 169- 197. doi: 10.1007/BF02579273
33	Karmarkar N, Karp R M. An efficient approximation scheme for the one-dimensional bin packing problem[C]//Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (FOCS), 1982: 312-320.
34	Eisenbrand F, Pálvölgyi D, Rothvoss T. Bin packing via discrepancy of permutations[C]//Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011: 476-481.
35	Newman A, Neiman O, Nikolov A. Beck's three permutations conjecture: A counterexample and some consequences[C]//Proceedings of the 53rd Annual Symposium on Foundations of Computer Science (FOCS), 2012: 253-262.
36	Eisenbrand F , Pálvölgyi D , Rothvoss T . Bin packing via discrepancy of permutations[J]. ACM Transactions on Algorithms, 2013, 9 (3): 1- 15.
37	Rothvoss T. Approximating bin packing within O$ (\log \text{OPT}* \log \log \text{OPT}) $ bins[C]//Proceedings of the 54th Annual Symposium on Foundations of Computer Science (FOCS), 2013: 20-29
38	Hoberg R, Rothvoss T. A logarithmic additive integrality gap for bin packing[C]//Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2017: 2616-2625.
39	Lovett S , Meka R . Constructive discrepancy minimization by walking on the edges[J]. SIAM Journal on Computing, 2015, 44 (5): 1573- 1582. doi: 10.1137/130929400
40	Jansen K, Solis-Oba R. An OPT +1 algorithm for the cutting stock problem with constant number of object lengths[C]//Proceedings of the 14th International Conference on Integer Programming and Combinatorial Optimization (IPCO), 2010: 438-449.
41	Goemans M X, Rothvoss T. Polynomiality for bin packing with a constant number of item types[C]//Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014: 830-839.
42	Friesen D K , Langston M A . A storage-size selection problem[J]. Information Processing Letters, 1984, 18 (5): 295- 296. doi: 10.1016/0020-0190(84)90010-3
43	Friesen D K , Langston M A . Variable sized bin packing[J]. SIAM Journal on Computing, 1986, 15 (1): 222- 230. doi: 10.1137/0215016
44	Epstein L , Levin A . An APTAS for generalized cost variable-sized bin packing[J]. SIAM Journal on Computing, 2008, 38 (1): 411- 428. doi: 10.1137/060670328
45	Jansen K , Öhring S . Approximation algorithms for time constrained scheduling[J]. Information and Computation, 1997, 132 (2): 85- 108. doi: 10.1006/inco.1996.2616
46	Jansen K . An approximation scheme for bin packing with conflicts[J]. Journal of Combinatorial Optimization, 1999, 3 (4): 363- 377. doi: 10.1023/A:1009871302966
47	Epstein L , Levin A . On bin packing with conflicts[J]. SIAM Journal on Optimization, 2008, 19 (3): 1270- 1298. doi: 10.1137/060666329
48	Koutsoupias E, Papadimitriou C. Worst-case equilibria[C]//Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS), 1999: 404-413.
49	Zhang C, Zhang G. Cost-sharing mechanisms for selfish bin packing[C]//Proceedings of the 11th International Conference on Combinatorial Optimization and Applications (COCOA), 2017: 355-368.

[1]	李建平, 蔡力健, 李陈筠然, 潘鹏翔. 限制性多源点偏心距增广问题[J]. 运筹学学报, 2022, 26(1): 60-68.
[2]	刘文杰, 张冬梅, 张鹏, 邹娟. 带惩罚µ-相似Bregman散度k-均值问题的初始化算法[J]. 运筹学学报, 2022, 26(1): 99-112.
[3]	剧嘉琛, 刘茜, 张昭, 周洋. 带惩罚的相同容量k-均值问题的局部搜索算法[J]. 运筹学学报, 2022, 26(1): 113-124.
[4]	李小玮, 成夏炎, 李荣珩. 带有线性惩罚的鲁棒k-种产品设施选址问题的近似算法[J]. 运筹学学报, 2021, 25(4): 31-44.
[5]	包晓光, 路超, 黄冬梅, 余炜. 混合图上最小-最大圈覆盖问题的近似算法[J]. 运筹学学报, 2021, 25(1): 107-113.
[6]	任建峰, 田晓云. 带有异常点的平方度量设施选址问题[J]. 运筹学学报, 2021, 25(1): 114-122.
[7]	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130.
[8]	刘晓霞, 余山杉, 罗文昌. 工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法[J]. 运筹学学报, 2020, 24(1): 131-139.
[9]	王翼展, 张安, 陈永, 陈光亭. 堆取料机调度问题的一个近似算法[J]. 运筹学学报, 2020, 24(1): 147-154.
[10]	张国川, 陈林. 负载均衡问题[J]. 运筹学学报, 2019, 23(3): 1-14.
[11]	姜燕君, 徐大川, 张冬梅. 平方度量动态设施选址问题的近似算法[J]. 运筹学学报, 2018, 22(3): 49-58.
[12]	余善恩, 徐文洋, 刘光宇. 圆形区域分散布局问题研究[J]. 运筹学学报, 2018, 22(3): 132-138.
[13]	王一水, 徐大川, 吴晨晨. 关联聚类问题的半定规划舍入算法[J]. 运筹学学报, 2018, 22(1): 67-76.
[14]	陈光亭, 陈蕾, 张安, 陈永. 可转包两台流水作业机排序的近似算法[J]. 运筹学学报, 2016, 20(4): 109-114.
[15]	仲维亚, 马晓茹. 带有运输且加工具有灵活性的无等待流水作业排序问题[J]. 运筹学学报, 2016, 20(4): 93-101.