Computer Science

Computer Science ›› 2019, Vol. 46 ›› Issue (9): 315-320.doi: 10.11896/j.issn.1002-137X.2019.09.048

• Interdiscipline & Frontier • Previous Articles     Next Articles

Heuristic One-dimensional Bin Packing Algorithm Based on Minimum Slack

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

  1. (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

PDF (PC)

1832

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

CLC Number: 

  • TP301.6
[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.
[1] LUO Jun-ren, ZHANG Wan-peng, LU Li-na, CHEN Jing. Survey on Online Adversarial Planning for Real-time Strategy Game [J]. Computer Science, 2022, 49(6): 287-296.
[2] FU Si-qing, LI Tie-jun, ZHANG Jian-min. Architecture Design for Particle Transport Code Acceleration [J]. Computer Science, 2022, 49(6): 81-88.
[3] GENG Hai-jun, WANG Wei, YIN Xia. Single Node Failure Routing Protection Algorithm Based on Hybrid Software Defined Networks [J]. Computer Science, 2022, 49(2): 329-335.
[4] AO Tian-yu, LIU Quan. Upper Confidence Bound Exploration with Fast Convergence [J]. Computer Science, 2022, 49(1): 298-305.
[5] LIU Zhong-hui, ZHAO Qi, ZOU Lu, MIN Fan. Heuristic Construction of Triadic Concept and Its Application in Social Recommendation [J]. Computer Science, 2021, 48(6): 234-240.
[6] GUO Qi-cheng, DU Xiao-yu, ZHANG Yan-yu, ZHOU Yi. Three-dimensional Path Planning of UAV Based on Improved Whale Optimization Algorithm [J]. Computer Science, 2021, 48(12): 304-311.
[7] LIU Tian-xing, LI Wei, XU Zheng, ZHANG Li-hua, QI Xiao-ya, GAN Zhong-xue. Monte Carlo Tree Search for High-dimensional Continuous Control Space [J]. Computer Science, 2021, 48(10): 30-36.
[8] GUO Fei-yan, TANG Bing. Mobile Edge Server Placement Method Based on User Latency-aware [J]. Computer Science, 2021, 48(1): 103-110.
[9] ZHANG Xu, WANG Li-li, YANG Bo-tao. Heuristic Algorithms for Two-dimensional Irregular Bin Packing Problem with GuillotineConstraints [J]. Computer Science, 2020, 47(5): 212-216.
[10] WANG Dong, SHANG Hong-hui, ZHANG Yun-quan, LI Kun, HE Xin-fu, JIA Li-xia. Application of Atomic Dynamics Monte Carlo Program MISA-KMC in Study of Irradiation Damage of Reactor Pressure Vessel Steel [J]. Computer Science, 2020, 47(4): 30-35.
[11] YANG Ting, LUO Fei, DING Wei-chao, LU Hai-feng. Bin Packing Algorithm Based on Adaptive Optimization of Slack [J]. Computer Science, 2020, 47(4): 211-216.
[12] LI Yuan-feng, LI Zhang-wei, QIN Zi-hao, HU Jun, ZHANG Gui-jun. Study on Transportation Problem Using Monte Carlo Similarity Based Genetic Algorithm [J]. Computer Science, 2020, 47(10): 215-221.
[13] ZHANG Shu-yu, DONG Da, XIE Bing, LIU Kai-gui. Bus Short-term Dynamic Dispatch Algorithm Based on Real-time GPS [J]. Computer Science, 2019, 46(6A): 497-501.
[14] LI Zhang-wei, HAO Xiao-hu, ZHANG Gui-jun. Multi-layer Screening Based Evolution Algorithm for De Novo Protein Structure Prediction [J]. Computer Science, 2019, 46(6A): 80-84.
[15] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading [J]. Computer Science, 2018, 45(4): 94-99.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.