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

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

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

【部分圖文】：

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


本文編號：3143062