在線A形裝箱問(wèn)題

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

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

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

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

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

具有特殊工件的平行機(jī)在線排序問(wèn)題04-26

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

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

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

分形有限元方法解外域聲散射問(wèn)題04-27

在線詞典大全05-04

在線上課簡(jiǎn)報(bào)12-23

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