研究主要針對(duì)所有裝入物品大小上限為1/2時(shí)的一維裝箱問題模型展開,根據(jù)物品尺寸大小劃分的思想,提出一種新的一維在線裝箱算法.本模型中,物品在線到來,對(duì)即將到來的物品信息及物品數(shù)量未知,算法執(zhí)行過程中,首先根據(jù)物品尺寸大小將物品劃分成7大類,再根據(jù)欲先設(shè)定的packing規(guī)則,將對(duì)應(yīng)類物品放入對(duì)應(yīng)類型箱子中,任何時(shí)刻,算法最多打開7個(gè)箱子.算法設(shè)計(jì)過程中,不再需要額外的空間存儲(chǔ)物品,物品一旦裝入箱子不允許取出重裝,箱子關(guān)閉后不允許再打開裝其他物品.最后,通過詳細(xì)的分析計(jì)算,驗(yàn)證出本算法能獲得1.4236的漸近競爭比.同時(shí)通過實(shí)例構(gòu)建得出問題新的下界為1.4231,將上下界之間的縫隙縮小至0.0005. 

【文章來源】：系統(tǒng)科學(xué)與數(shù)學(xué). 2017,37(03)北大核心CSCD

【文章頁數(shù)】：11 頁

【部分圖文】：

圖１?ＮＦＢ算法執(zhí)行實(shí)例??（Ｆｉｇｕｒｅ?１?Ｅｘａｍｐｌｅ?ｏｆ?ＮＦＢ）??


本文編號(hào)：3143062