Please wait a minute...
浙江大学学报（理学版）
浙江大学学报（理学版）
数学与计算机科学     
底为正方形的三维装箱问题
浙江大学玉泉校区应用数学系 , 浙江 杭州 310027
A Three Dimensional Packing Method f or Square Bottom Instances.
department of Applied Mathematics, Zhejiang University , Hangzhou 31002 7, China )
 全文: PDF(239 KB)   HTML ( ) 
摘要： 本文讨论如何将一堆底部为正方形 ,长、宽、高均不超过 1的盒子装入一底为 1× 1,高为正无穷的柱形箱子 ,使装箱高度 Z为最小的问题 .该问题已知为 N P难的问题 . Li和 Cheng在 1990年提出了多项式近似算法 C1,其渐近性能比 r( C1) = 2. 687 5(见参考文献 [1 ]) . 本文根据算法 C1的思想 ,进一步利用盒 子底部为正方形的特点 ,尽可能不浪费高度空间 ,提出了所谓“单元装箱法” D,使新算法的渐近性能比得到改进: r (D ) ≤ 2*251/78 4= 2. 3 201 5.
关键词： NP难问题;  多项式近似算法;  渐近性能比    
Abstract: This paper discusses how to pack a set of boxes with square bottom s into a box B with a fix edsize square bott m and unbounded height such that the height of the pack in g is minimized . It is requiredth at all boxes be packed in to Borthogonally and oriented in a ll three dimension s. The problem is k no w nto b e N P-h a rd. Li a nd C h eng d ev elop ed an ap pr ox im a tio n a lg o rith m C1in 19 90 , of which the worst caseper form an ceratio is r (C1 ) = 2. 6 875 ( reference [ 1 ] ) . Based on th e id ea of algorith m C1 and the characteristics of squares, a new packing method D is developed , of which the worst-case performanceratio is r ( D ) ≤ 2*251/7 84= 2. 3 20 15.
Key words: N P-ha rd    approximation algorithm    asymptotic performance bound
收稿日期: 1998-03-26 出版日期: 2017-05-15
:  O223  
基金资助: 国家自然科学基金资助项目 ( 19701028)
作者简介: 沈灏 ( 1958- ) ,女 ,浙江大学在职博士生 ,杭州电子工业学院讲师 ,从事组合数学方面有关装箱和排序的研究 .
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
沈灏

引用本文:

沈灏. 底为正方形的三维装箱问题[J]. 浙江大学学报（理学版）, .

SHEN Hao . A Three Dimensional Packing Method f or Square Bottom Instances. . Journal of ZheJIang University(Science Edition), .

链接本文:

http://www.zjujournals.com/sci/CN/    或    http://www.zjujournals.com/sci/CN/Y1999/V26/I3/44

[1] 刘卫锋, 常娟, 杜迎雪. 连续拟有序加权几何算子及其群决策应用[J]. 浙江大学学报（理学版）, 2018, 45(2): 180-187,195.
[2] 荣建华. 具有服务等级的可拒绝平行机排序问题[J]. 浙江大学学报（理学版）, 2016, 43(6): 685-688.
[3] 荣建华, 侯丽英. 带有到达时间和拒绝费用工件的同类机排序问题[J]. 浙江大学学报（理学版）, 2016, 43(5): 545-549.
[4] 何勇. 带有工件调整时间的排序复杂性[J]. 浙江大学学报（理学版）, 1999, 26(3): 39-43.