Computer Science ›› 2020, Vol. 47 ›› Issue (4): 211-216.doi: 10.11896/jsjkx.190500132

• Artificial Intelligence • Previous Articles     Next Articles

Bin Packing Algorithm Based on Adaptive Optimization of Slack

YANG Ting, LUO Fei, DING Wei-chao, LU Hai-feng   

  1. Department of Computer Science and Engineering,East China University of Science and Technology,Shanghai 200237,China
  • Received:2019-05-22 Online:2020-04-15 Published:2020-04-15
  • Contact: LUO Fei,born in 1978,Ph.D,associate professor,postgraduate supervisor,is a member of China Computer Federation.His main research interests include cloud computing,and distributed computing.
  • About author:YANG Ting,born in 1996,postgra-duate.Her main research interests include cloud computing and bin packing problems.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China(61472139),and Research Project of Education and Teaching Law and Method of East China University of Science and Technology in 2017 (ZH1726107)

Abstract: The bin packing problem is a classical and important mathematical optimization problem in logistics system and production system.A series of items are put into bins with fixed capacity in a certain order,and the number of bins used is minimized to obtain the approximate optimal solution of the bin packing problem to the greatest extent.However,the existing bin packing algorithms have obvious defects.Genetic algorithm has too much computation,and even can’t find the required solution.Heuristic algorithm can’t deal with the extreme value problem.And the existing improved algorithm will easily fall into the local minimum even if the slack is introduced.The proposed Adaptive-MBS algorithm uses adaptive weights to improve the original method.Specifically,the method is allowed to have a certain amount of slack,and has the intuition of capturing the change of object sample space with time,so as to use a better slack strategy to pack.The Adaptive-MBS algorithm first uses the current bin as the center and uses the Adaptive_Search algorithm to iteratively find a subset of all objects in the set suitable for the bin capacity.In the Adaptive_Search algorithm,the bin is not required to be completely filled,but is allowed to have a certain amount of slack.In the training process,the slack is automatically adjusted according to the change of the current state,and after finding the subset that is completely filled,the subset is iterated to the next round of search until the traversal is completed.This method is not easy to fall into local optimum and has strong ability to find global optimum.In this paper,the BINDATA and SCH_WAE data sets in the packing problem are used for experiments.The results show that 991 cases in the data set can be optimized by Adaptive-MBS algorithm.In the case where the optimal solution is not found,the proposed algorithm has the lowest relative offset percentage in all comparison algorithms.Numerical experiments show that compared with other classic bin packing algorithms,Adaptive-MBS algorithm has better effect and its convergence speed is significantly better than other algorithms.

Key words: Adaptive weight, Bin packing problem, Global optimal solution, Heuristic algorithm, Slack

CLC Number: 

  • TP301.6
[1]DE ALMEIDA R,STEINER M T A.Resolution of 1-D Bin Packing Problem using Augmented Neural Networks and Minimum Bin Slack[C]//Latin America Congress on Computational Intelligence (LA-CCI).IEEE,2015:1-6.
[2]KAAOUACHE M A,BOUAMAMA S.Solving bin packingproblem with a hybrid genetic algorithm for VM placement in cloud[J].Procedia Computer Science,2015,60(1):1061-1069.
[3]RODRIGO N P,DAUNDASEKERA W B,PERERA A I.One-dimensional bin-packing problems with branch and bound algorithm[J].International Journal of Discrete Mathematics,2018,3(2):36.
[4]HU H,ZHANG X,YAN X,et al.Solving a new 3d bin packing problem with deep reinforcement learning method[J].arXiv:1708.05930,2017.
[5]DUAN L,HU H,QIAN Y,et al.A Multi-task Selected Learning Approach for Solving 3D Flexible Bin Packing Problem[J].arXiv:1804.06896,2018.
[6]KORF R E.A new algorithm for optimal bin packing[C]//Proceedings of the EighteenthNational Conference on Articial Intelligence.AAAI Press,2002:731-736.
[7]VAZIRANI V V.Approximation algorithms[M].Springer Science & Business Media,2013:10-19.
[8]GUPTA J N D,HO J C.A new heuristic algorithm for the one-dimensional bin-packing problem[J].Production Planning & Control,1999,10(6):598-603.
[9]HARTMANIS J.Computers and intractability:a guide to thetheory of NP-completeness (michael r.garey and david s.johnson)[J].Siam Review,1982,24(1):90.
[10]COFFMAN J,GAREY M,JOHNSON D S.Approximation algorithms for NP-hard problems.[M].Boston:PWS Publishing,1997:46-93.
[11]DOSA G.Encyclopedia of Algorithms [M].New York:Springer,2014:10-19.
[12]NGUYEN-DUC T,QUANG-HUNG N,THOAI N.BFD-NN:best fit decreasing-neural network for online energy-aware virtual machine allocation problems[C]//Proceedings of the Se-venth Symposium on Information and Communication Technology.ACM,2016:243-250.
[13]JOHNSON D S.Near-optimal bin packing algorithms[D].Cambridge:Massachusetts Institute of Technology,1973.
[14]FLESZAR K,HINDI K S.New heuristics for one-dimensionalbin-packing[J].Computers & operations research,2002,29(7):821-839.
[15]MARTELLO S,TOTH P.Lower bounds and reduction procedures for the bin packing problem[J].Discrete applied mathematics,1990,28(1):59-70.
[16]ZHANG J J.Conbinatorial packing probleming:Models and Algorithms[D].Shanghai:Shanghai Jiao Tong University,2012.
[17]SRIDHAR R,CHANDRASEKARAN M,SRIRAMYA C,et al.Optimization of heterogeneous Bin packing using adaptivegene-tic algorithm[C]//IOP Conference Series:Materials Science and Engineering.IOP Publishing,2017.
[18]QUIROZ-CASTELLANOS M,CRUZ-REYES L,TORRESJIMENEZ J,et al.A grouping genetic algorithm with controlled gene transmission for the bin packing problem[J].Computers & Operations Research,2015,55:52-64.
[19]DOKEROGLU T,COSAR A.Optimization of one-dimensionalbin packing problem with island parallel grouping genetic algorithms[J].Computers & Industrial Engineering,2014,75:176-186.
[20]LOH K H,GOLDEN B,WASIL E.Solving the one-dimensional bin packing problem with a weight annealing heuristic[J].Computers & Operations Research,2008,35(7):2283-2291.
[21]HIFI M,NEGRE S,WU L.Hybrid greedy heuristics based onlinear programming for the three-dimensional single bin-size bin packing problem[J].International Transactions in Operational Research,2014,21(1):59-79.
[22]BALOGH J,BÉKÉSI J,DÒSA G,et al.The optimal absolute ratio for online bin packing[C]//Proceedings of the twenty-sixth Annual ACM-SIAM Symposium on Discrete Algorithms.Philadelphia:Society for Industrial and Applied Mathematics,2014:1425-1438.
[23]KHANAFER A,CLAUTIAUX F,TALBI E G.New lowerbounds for bin packing problems with conflicts[J].European Journal of Operational Research,2010,206(2):281-288.
[24]CLAUTIAUX F,DELL’AMICO M,IORI M,et al.Lower and upper bounds for the Bin Packing Problem with Fragile Objects[J].Discrete Applied Mathematics,2014,163:73-86.
[25]BALOGH J,BÉKÉSI J,GALAMBOS G,et al.Lower bound for 3-batched bin packing[J].Discrete Optimization,2016,21:14-24.
[26]BALOGH J,BÉKÉSI J.Semi-on-line bin packing:a short overview and a new lower bound[J].Central European Journal of Operations Research,2013,21(4):685-698.
[27]SCHOLL A,KLEIN R,JÜRGENS C.Bison:A fast hybrid procedure for exactly solving the one-dimensional bin packing problem[J].Computers & Operations Research,1997,24(7):627-645.
[28]SCHWERIN P,WÄSCHER G.The bin-packing problem:Aproblem generator and some numerical experiments with FFD packing and MTP[J].International Transactions in Operational Research,1997,4(5/6):377-389.
[29]LÒPEZ-CAMACHO E,TERASHIMA-MARÍN H,ROSS P.Ahyper-heuristic for solving one and two-dimensional bin packing problems[C]//Proceedings of the 13th Annual Conference Companion on Genetic and Evolutionary Computation.Dublin:ACM,2011:257-258.
[1] ZHAO Liang, ZHANG Jie, CHEN Zhi-kui. Adaptive Multimodal Robust Feature Learning Based on Dual Graph-regularization [J]. Computer Science, 2022, 49(4): 124-133.
[2] 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.
[3] 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.
[4] 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.
[5] CAO Lin, YU Wei-wei. Adaptive Window Binocular Stereo Matching Algorithm Based on Image Segmentation [J]. Computer Science, 2021, 48(11A): 314-318.
[6] GUO Fei-yan, TANG Bing. Mobile Edge Server Placement Method Based on User Latency-aware [J]. Computer Science, 2021, 48(1): 103-110.
[7] CHENG Zhong-Jian, ZHOU Shuang-e and LI Kang. Sparse Representation Target Tracking Algorithm Based on Multi-scale Adaptive Weight [J]. Computer Science, 2020, 47(6A): 181-186.
[8] 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.
[9] HUANG Guang-qiu, LU Qiu-qin. Vertical Structure Community System Optimization Algorithm [J]. Computer Science, 2020, 47(4): 194-203.
[10] YI Yu-gen, LI Shi-cheng, PEI Yang, CHEN Lei, DAI Jiang-yan. Feature Selection Method Combined with Multi-manifold Structures and Self-representation [J]. Computer Science, 2020, 47(11A): 474-478.
[11] 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.
[12] ZHAO Qing-jie, LI Jie, YU Jun-yang, JI Hong-yuan. Bat Optimization Algorithm Based on Dynamically Adaptive Weight and Cauchy Mutation [J]. Computer Science, 2019, 46(6A): 89-92.
[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] SHEN Xian-bao, SONG Yu-qing, LIU Zhe. Adaptive Integrated Method Based on Sorting Selection Metrics [J]. Computer Science, 2019, 46(12): 237-241.
[15] YANG Liu, CHEN Li-min, YI Yu-gen. Face Recognition Method Based on Adaptively Weighted Sub-pattern Discriminant Neighborhood Projection [J]. Computer Science, 2019, 46(10): 307-310.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!