Computer Science ›› 2017, Vol. 44 ›› Issue (5): 290-293, 303.doi: 10.11896/j.issn.1002-137X.2017.05.053

Previous Articles     Next Articles

u-Block Optimization Algorithm for 2-D Strip Packing Problem

HUANG Hai and LI Song-bin   

  • Online:2018-11-13 Published:2018-11-13

Abstract: The 2-D strip packing problem is the problem of loading a subset of a given set of rectangular boxes with profits into a rectangular container so that the stowed profits is maximized.The paper presented u-Block optimization algorithm to find more efficient parameter of block for any value.A new data structure was introduced for different classes of rectangles.At last,u-points of the X axis of the different kinds of rectangular boxes were filled to the maximum profits of the items.Two algorithms were developed,one is an effective block parameter u,another is block selection algorithm based on a simplified data structure.In particular,we presented polynomial time approximation for any value. In the case of polynomial time complexity and ε,we can reduce the required box width from 1+ε to 1,while the beight remains the same.

Key words: u-Block,2-D packing problem,Approximation scheme,NP-hard,Heuristics

[1] HAR-PELED S,KAPLAN H,SHARIR M.Approximating the k-level in three-dimensional plane arrangements[C]∥Acm-siam Symposium on Discrete Algorithms.2016:1193-1212.
[2] NADIRADZE G,WIESE A.On approximating strip packing wi-th a better ratio than 3/2[C]∥Acm-siam Symposium on Discrete Algorithms.2016:1491-1510.
[3] FERNAU H,LPEZ-ORTIZ A.Using Parametric,Transforma-tions Toward Polynomial Kernels for Packing Problems Allowing Overlaps[J].ACM Transactions on Computation Theory,2015,7(3):1-29.
[4] LPEZ-CAMACHO E,TERASHIMA-MARIN H.A unifiedhyper-heuristic framework for solving bin packing problems[J].Expert Systems with Applications,2014,41(15):6876-6889.
[5] ASTA S,OZCAN E.A Tensor Analysis Improved Genetic Algorithm for Online Bin Packing[C]∥ Genetic & Evolutionary Computation Conference.New York:ACM Press,2015:799-806.
[6] ZHANG D F,PENG Y,ZHANG L L.A Multi-Layer Heuristic Search Algorithm for Three Dimensional Container Loading Problem[J].Chinese Journal of Computers,2012,35(12):2553-2561.(in Chinese) 张德富,彭煜,张丽丽.求解三维装箱问题的多层启发式搜索算法[J].计算机学报.2012,5(12):2553-2561.
[7] LIU S,ZHU F H,LV Y S,et al.A Heuristic Orthogonal Binary Tree Search Algorithm for Three Dimensional Container Loa-ding Problem[J].Chinese Journal of Computers,2015,38(8):1530-1543.(in Chinese) 刘胜,朱凤华,吕宜生,等.求解三维装箱问题的启发式正交二叉树搜索算法[J].计算机学报,2015,38(8):1530-1543.
[8] SOSA-ASCENCIO A,TERASHIMA H.Conant-Pablos Gram-mar-based Selection Hyper-heuristics for Solving Irregular Bin Packing Problems[C]∥Genetic and Evolutionary Computation Conference.New York:ACM Press,2016:111-112.
[9] JANSEN K,ZHANG G.Maximizing the number of packed rectangles[M]∥Scandinavian Workshop on Algorithm Theory(SWAT).2004:362-371.
[10] HARREN R.Approximating the orthogonal knapsack problemfor hypercubes[C]∥International Colloquium on Automata,Languages and Programming(ICALP).2006:238-249.
[11] FISHKIN A V,GERBER O,JANSEN K,et al.Packing weighted rectangles into a square[C]∥Symposium on Mathematical Foundation of Computer Science(MFCS).2005:352-363.
[12] LAWLER E.Fast approximation algorithms for knapsack problems[J].Mathematics of Operations Research,1977,4(4):339-356.
[13] FISHKIN A V,GERBER O,JANSEN K.On weighted rectangle packing with large resources[C]∥Theoretical Computer Science Conference(TCS).2004:237-250.
[14] COFFMAN E G.Performance bounds for level-oriented two-dimensional packing algorithms[J].SIAM Journal on Computing,1980,9(4):808-826.
[15] HOPPER E,TRUTON B C H.An empirical investigation ofmeta-heuristic and heuristic algorithms for a 2D packing problem[J].European Journal of Operational Research,2001,8(1):34-57.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] 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, 116 .