基于最小松弛量的启发式一维装箱算法

doi:10.11896/j.issn.1002-137X.2019.09.048

计算机科学 ›› 2019, Vol. 46 ›› Issue (9): 315-320.doi: 10.11896/j.issn.1002-137X.2019.09.048

基于最小松弛量的启发式一维装箱算法

罗飞, 任强, 丁炜超, 卢海峰

(华东理工大学信息科学与工程学院上海200237)

收稿日期:2018-08-16 出版日期:2019-09-15 发布日期:2019-09-02
通讯作者: 任强(1993-),男,硕士生,主要研究方向为云计算,E-mail:renqiqiang@outlook.com
作者简介:罗飞(1978-),男,博士,副教授,主要研究方向为分布式计算,E-mail:luof@ecust.edu.cn;丁炜超(1989－),男,博士,讲师,主要研究方向为云资源调度、分布式计算、多目标优化等;卢海峰(1993－),男,博士生,主要研究方向为边缘计算和强化学习。
基金资助:
国家自然科学基金(61472139),华东理工大学2017年教育教学规律与方法研究项目(ZH1726107)

Heuristic One-dimensional Bin Packing Algorithm Based on Minimum Slack

LUO Fei, REN Qiang, DING Wei-chao, LU Hai-feng

(Department of Computer Science and Engineering,East China University of Science and Technology,Shanghai 200237,China)

Received:2018-08-16 Online:2019-09-15 Published:2019-09-02

摘要/Abstract

摘要： 一维装箱问题是组合优化中的NP难问题,在有限的时间内获得问题的精确解非常困难。启发式算法和遗传算法是解决装箱问题的两类主要方法,但是,采用经典启发式装箱算法得到的结果在极端情况下非常差,而遗传算法在解决装箱问题的过程中容易出现无效解,致使需要处理的数据量十分巨大。为了获得装箱问题的近似最优解,文中针对目前的装箱问题算法展开分析,提出了一种新型的启发式装箱算法。提出的IAMBS算法允许装箱有一定的松弛量,使用随机思想搜索局部最优,进而获得装箱问题的全局最优解。随机松弛量使该算法不易陷入局部最优,具有较强的发现全局最优解的能力。采用来自两个数据集的1410个基准测试实例进行实验。最终,IAMBS算法获得了1152个实例的最优解。实验数据表明,IAMBS算法可以有效地获得近似最优解,比经典装箱算法更有优势。

关键词: 蒙特卡洛, 启发式算法, 随机算法, 装箱问题

Abstract: The one-dimensional bin packing problem is a NP-hard problem in the combinatorial optimization,and it is extremely difficult to obtain an accurate solution of the problem in a limited time.Heuristic algorithms and genetic algorithms are the two main methods to solve the bin packing problem.However,the results obtained by the classical heuristic packing algorithm are very poor in extreme cases.The genetic algorithm is prone to generate invalid solutions in the process of solving the packing problem,thus resulting in large amount of data to be processed.In order to obtain the approximate optimal solution of the packing problem,this paper analyzed the current packing problem algorithm and proposed a new heuristic packing algorithm.The proposed IAMBS algorithm uses the idea of random to search for local optimum by allowing a certain amount of slack in the bin-packing,and then obtains the global optimal solution of the packing problem.The allowable slack can prevent this algorithm from falling into local optimum,and has strong ability to discover global optimal solutions.1410 benchmark test instances from two sources were utilized for the experiment,and the optimal solution of 1152 instances were implemented by the IAMBS algorithm.Experimental data demonstrate that the IAMBS algorithm can effectively obtain the approximate optimal solution,and it is more advantageous than the traditional classical packing algorithm.

Key words: Bin packing problem, Heuristic algorithm, Monte Carlo, Random algorithm

中图分类号:

TP301.6

罗飞, 任强, 丁炜超, 卢海峰. 基于最小松弛量的启发式一维装箱算法[J]. 计算机科学, 2019, 46(9): 315-320. https://doi.org/10.11896/j.issn.1002-137X.2019.09.048

LUO Fei, REN Qiang, DING Wei-chao, LU Hai-feng. Heuristic One-dimensional Bin Packing Algorithm Based on Minimum Slack[J]. Computer Science, 2019, 46(9): 315-320. https://doi.org/10.11896/j.issn.1002-137X.2019.09.048

参考文献

[1]DELORMEM,IORIM,MARTELLO S.Bin packing and cutting stock problems:Mathematical models and exact algorithms[J].European Journal of Operational Research,2016,255(1):1-20.
[2]JOHNSON D S.Near-Optimal Bin Packing Algorithms[D].Cambridge,MA,USA:Massachusetts Institute of Technology,1973.
[3]HEYDRICH S,STEE R V.Beating the Harmonic lower bound for online bin packing[J].arXiv:1511.00876.
[4]SEIDEN S S.On the online bin packing problem[J].Journal of the Acm,2002,49(5):640-671.
[5]BALOGH J,BÉKÉSI J,GALAMBOS G.New Lower Bounds for Certain Classes of Bin Packing Algorithms[J].Theoretical Computer Science,2012,440-441(8):1-13.
[6]COFFMAN E G J,GAREY M R,JOHNSON D S.Approximation algorithms for bin packing:a survey[C]//Approximation algorithms for NP-hard problems.PWS Publishing Co.,1997:46-93.
[7]GUPTA J D,HO J.A new heuristic algorithm for the one-dimensional bin-packing problem[J].Production Planning & Control,1999,10(6):598-603.
[8]FLESZARK,KHALIL S.New heuristics for one-dimensionalbin-packing[J].Computers & Operations Research,2002,29(7):821-839.
[9]MARTELLO S,TOTH P.Knapsack problems:algorithms and computer implementations[J].Journal of the Operational Research Society,1991,42(6):513-513.
[10]SCHOLL A,KLEIN R,JÜRGENS C.Bison:A fast hybrid procedure for exactly solving the one-dimensional bin packing problem[J].Publications of Darmstadt Technical University Institute for Business Studies,1997,24(7):627-645.
[11]CARVALHO J M V D.Exact solution of cutting stock problems using column generation and branch-and-Bound 1[J].Annals of Operations Research,1999,86(1):629-659.
[12]FALKENAUER E.A hybrid grouping genetic algorithm for bin packing[J].Journal of Heuristics,1996,2(1):5-30.
[13]BHATIA A K,BASU S K.Packing Bins Using Multi-chromosomal Genetic Representation and Better-Fit Heuristic[C]//Neural Information Processing,International Conference,ICONIP 2004.Calcutta,India,2004:181-186.
[14]TANSEL D,AHMET C.Optimization of one-dimensional BinPacking Problem with island parallel grouping genetic algorithms[J].Computers & Industrial Engineering,2014,75:176-186.
[15]玄光男,程润伟.遗传算法与工程优化[M].北京:清华大学出版社,2004:26-27.
[16]JOHNSON D S.Fast algorithms for bin packing [J].Journal of Computer & System Sciences,1974,8(3):272-314.
[17]HOCHBAUM D.Approximation algorithms for NP-hard problems[J].ACM Sigact News,1997,28(2):40-52.
[18]HOFFMANN T R.Assembly line balancing with a precedence matrix[J].Management Science,1963,9(4):551-562.
[19]KROESE D P,BRERETON T,TAIMRE T,et al.Why theMonte Carlo method is so important today[J].Wires Computational Statistics,2014,6(6):386-392.
[20]BRATTKA V,GHERARDI G,HÖLZL R.Las Vegas computability and algorithmic randomness[J].International Symposium on Theoretical Aspects of Computer Science,2015,30:130-142.
[21] ROBERT P C.Monte Carlo statistical methods [M].WorldBook Publishing Company,2009.
[22]SLEATOR D D,TARJAN R E.Amortized efficiency of list update and paging rules[J].Communications of the Acm,1985,28(2):202-208.
[23]SCHWERIN P,WÄESCHER G.The Bin-Packing Problem:A Problem Generator and Some Numerical Experiments with FFD Packing and MTP[J].International Transactions in Operational Research,1997,4(5／6):377-389.

相关文章 15

[1]	罗俊仁, 张万鹏, 陆丽娜, 陈璟. 即时策略博弈在线对抗规划方法综述 Survey on Online Adversarial Planning for Real-time Strategy Game 计算机科学, 2022, 49(6): 287-296. https://doi.org/10.11896/jsjkx.210600168
[2]	傅思清, 黎铁军, 张建民. 面向粒子输运程序加速的体系结构设计 Architecture Design for Particle Transport Code Acceleration 计算机科学, 2022, 49(6): 81-88. https://doi.org/10.11896/jsjkx.210600179
[3]	耿海军, 王威, 尹霞. 基于混合软件定义网络的单节点故障保护方法 Single Node Failure Routing Protection Algorithm Based on Hybrid Software Defined Networks 计算机科学, 2022, 49(2): 329-335. https://doi.org/10.11896/jsjkx.210100051
[4]	敖天宇, 刘全. 一种快速收敛的最大置信上界探索方法 Upper Confidence Bound Exploration with Fast Convergence 计算机科学, 2022, 49(1): 298-305. https://doi.org/10.11896/jsjkx.201100194
[5]	刘忠慧, 赵琦, 邹璐, 闵帆. 三元概念的启发式构建及其在社会化推荐中的应用 Heuristic Construction of Triadic Concept and Its Application in Social Recommendation 计算机科学, 2021, 48(6): 234-240. https://doi.org/10.11896/jsjkx.200500136
[6]	高吉吉, 岳雪蓉, 陈智斌. 针对经典排序问题的一种新算法的近似比分析 Approximate Ratios Analysis of New Algorithm for Classical Parallel Scheduling 计算机科学, 2021, 48(4): 37-42. https://doi.org/10.11896/jsjkx.200600064
[7]	郭启程, 杜晓玉, 张延宇, 周毅. 基于改进鲸鱼算法的无人机三维路径规划 Three-dimensional Path Planning of UAV Based on Improved Whale Optimization Algorithm 计算机科学, 2021, 48(12): 304-311. https://doi.org/10.11896/jsjkx.201000021
[8]	郭飞雁, 唐兵. 基于用户延迟感知的移动边缘服务器放置方法 Mobile Edge Server Placement Method Based on User Latency-aware 计算机科学, 2021, 48(1): 103-110. https://doi.org/10.11896/jsjkx.200900146
[9]	张旭, 王莉莉, 杨博韬. 带有一刀切约束的二维非规则装箱算法 Heuristic Algorithms for Two-dimensional Irregular Bin Packing Problem with GuillotineConstraints 计算机科学, 2020, 47(5): 212-216. https://doi.org/10.11896/jsjkx.190400078
[10]	王栋, 商红慧, 张云泉, 李琨, 贺新福, 贾丽霞. 原子动力学蒙特卡洛程序MISA-KMC在反应堆压力容器钢辐照损伤研究中的应用 Application of Atomic Dynamics Monte Carlo Program MISA-KMC in Study of Irradiation Damage of Reactor Pressure Vessel Steel 计算机科学, 2020, 47(4): 30-35. https://doi.org/10.11896/jsjkx.191100045
[11]	杨婷, 罗飞, 丁炜超, 卢海峰. 一种自适应优化松弛量的装箱算法 Bin Packing Algorithm Based on Adaptive Optimization of Slack 计算机科学, 2020, 47(4): 211-216. https://doi.org/10.11896/jsjkx.190500132
[12]	李远锋, 李章维, 秦子豪, 胡俊, 张贵军. 基于蒙特卡洛相似度遗传算法的运输问题研究 Study on Transportation Problem Using Monte Carlo Similarity Based Genetic Algorithm 计算机科学, 2020, 47(10): 215-221. https://doi.org/10.11896/jsjkx.190600101
[13]	张澍裕, 宫达, 谢兵, 刘开贵. 基于实时GPS的公交短时动态调度算法 Bus Short-term Dynamic Dispatch Algorithm Based on Real-time GPS 计算机科学, 2019, 46(6A): 497-501.
[14]	史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法 Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading 计算机科学, 2018, 45(4): 94-99. https://doi.org/10.11896/j.issn.1002-137X.2018.04.014
[15]	童晓红,唐超. 基于次优区间卡尔曼滤波的机器鱼跟踪方法 Robotic Fish Tracking Method Based on Suboptimal Interval Kalman Filter 计算机科学, 2018, 45(2): 114-120. https://doi.org/10.11896/j.issn.1002-137X.2018.02.020

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于最小松弛量的启发式一维装箱算法

Heuristic One-dimensional Bin Packing Algorithm Based on Minimum Slack

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0