允許數(shù)據(jù)項移動和受位置約束的局內(nèi)裝箱算法的研究.pdf

1、在計算機科學和工業(yè)領(lǐng)域中，裝箱問題有著廣泛的應(yīng)用背景，包括多處理器任務(wù)調(diào)度、資源分配、剪裁和現(xiàn)實生活中包裝、整理物件等。在計算機科學中，文件分配、內(nèi)存管理等低層操作均是裝箱問題的實際應(yīng)用，而裝箱問題的各種算法如首次適應(yīng)、最佳適應(yīng)等策略在這些領(lǐng)域已經(jīng)得到廣泛的應(yīng)用。 在至今的局內(nèi)裝箱問題研究當中，除Giorgio在2000年提出一種數(shù)據(jù)項可移動的局內(nèi)裝箱算法之外，所有的局內(nèi)裝箱算法中的數(shù)據(jù)項均是不能移動的，即輸入序列中的數(shù)據(jù)項一旦

2、入箱，就不能再移動，并且在所有數(shù)據(jù)項處理完后，均不能釋放部分曾經(jīng)被裝過數(shù)據(jù)項的箱子。 論文為了進一步提高局內(nèi)裝箱近似算法的最壞情況漸進性能比，改進Giorgio提出的數(shù)據(jù)項移動模型，提出MAREL局內(nèi)算法，算法中數(shù)據(jù)項所屬區(qū)間(0，1]劃分為8個并不均等且不相交的子區(qū)間：I0，I1，I2，I3，I4，I5I6，I7。I7-數(shù)據(jù)項當作能被聚集的“小”數(shù)據(jù)項，且能整體(組)移動，插入I1-箱，I2-箱，I3-箱，I4-箱和I5-箱當

3、中。MAREL算法的空間復(fù)雜度是O(n)，時間復(fù)雜度是O(nlogn)，最壞情況漸近性能比為1.25。該算法的最壞情況漸進性能比低于同類算法的最壞情況漸進性能比，并且低于局內(nèi)裝箱算法漸近性能比理論上的下確界1.536…，同時低于目前所有的局內(nèi)裝箱近似算法的最壞情況漸進性能比。 此外，本文還首先提出受位置約束的有色裝箱問題。它在有色裝箱問題的基礎(chǔ)上加上一個約束：在有色裝箱的過程中要滿足重(長)的物品置于輕(短)的物品下方的原則，同