计算机科学 ›› 2017, Vol. 44 ›› Issue (5): 290-293.doi: 10.11896/j.issn.1002-137X.2017.05.053

• 人工智能 • 上一篇    下一篇

求解2-D Strip Packing问题的u-分组优化算法

黄海,李松斌   

  1. 莆田学院信息工程学院 莆田351100,中国科学院声学研究所南海研究站 海口570105;中国科学院声学研究所国家网络新媒体工程技术研究中心 北京100190
  • 出版日期:2018-11-13 发布日期:2018-11-13
  • 基金资助:
    本文受国家自然科学基金(61303249),福建省教育厅A类科技项目(JA15443),福建省莆田市科技项目(2014G16)资助

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

HUANG Hai and LI Song-bin   

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

摘要: D strip packing问题指将带有价值的矩形物品装入长宽固定的箱子中,使其装入的物品价值最大。基于装箱的期望目标ε,提出一种新的分组构造函数,结合装箱矩形特点计算出最优分组参数u并对矩形进行分类,同时对不同类别的矩形引入相应的数据结构,最后对不同类别矩形基于箱子X轴的u等分点进行填充,使其装入的物品价值最大。文中的主要贡献在于:提出了一种有效的分组构造函数;计算出了对应的最优分组参数u;简化了不同类别箱体的数据结构以及相应的装箱算法;特别地,在期望目标ε、多项式时间复杂度和 至少装入(1-ε) OPT价值物品的情况下,可将所需箱体宽度从1+ε减小到1,而高度保持不变。

关键词: u-分组,二维装箱,近似算法,NP难度,启发式

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   
No Suggested Reading articles found!