在線A形裝箱問題

研究了一類有實際背景的新的裝箱問題--A形裝箱問題(ASBP)的在線情形.在ASBP中物品均為圓柱形,并且在每個箱子中物品均擺放成A字形,即后到達的物品放在先到達的物品之上且上層物品的截面半徑不超過下層物品的截面半徑,優化目標是最小化裝下所有物品所用的箱子數.當所有物品半徑都相同時ASBP退化成經典一維裝箱問題(BP),故BP為ASBP的特殊情形.BP的大多數啟發式算法可以推廣到ASBP中,我們從最壞情形分析的角度討論了兩類ASBP啟發式算法.證明了直接推廣的啟發式算法性能較差,其中一些算法的漸近最壞比甚至可以任意大;如果半徑的種類有限,按半徑分類的啟發式算法的性能較好,并且一些算法的漸近最壞比和它們所基于的BP啟發式算法的漸近最壞比相等.

作 者： 陳鋒 邢文訓   作者單位： 清華大學數學科學系,北京,100084  刊 名： 系統工程理論與實踐  ISTIC EI PKU 英文刊名： SYSTEMS ENGINEERING——THEORY & PRACTICE  年，卷(期)： 2002 22(7)  分類號： O223  關鍵詞： 裝箱問題   算法分析   啟發式算法  

【在線A形裝箱問題】相關文章：

無支架纜索吊裝箱形拱橋施工工藝04-27

遠程培訓在線教學支持的問題及對策研究04-28

具有特殊工件的平行機在線排序問題04-26

氨氮在線自動監測儀的現狀與問題04-26

氨氮在線自動監測儀的現狀與問題04-26

火電廠煙氣在線監測系統存在的主要問題及進一步加強在線監測工作的建議04-26

分形有限元方法解外域聲散射問題04-27

在線詞典大全05-04

在線上課簡報12-23

MODEM·什么是在線連接04-26