在線A形裝箱問題

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

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

【在線A形裝箱問題】相關(guān)文章：

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

遠(yuǎn)程培訓(xùn)在線教學(xué)支持的問題及對策研究04-28

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

氨氮在線自動監(jiān)測儀的現(xiàn)狀與問題04-26

氨氮在線自動監(jiān)測儀的現(xiàn)狀與問題04-26

火電廠煙氣在線監(jiān)測系統(tǒng)存在的主要問題及進(jìn)一步加強在線監(jiān)測工作的建議04-26

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

在線詞典大全05-04

在線上課簡報12-23

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