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

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

2、入箱，就不能再移動，并且在所有數(shù)據(jù)項處理完后，均不能釋放部分曾經被裝過數(shù)據(jù)項的箱子。 論文為了進一步提高局內裝箱近似算法的最壞情況漸進性能比，改進Giorgio提出的數(shù)據(jù)項移動模型，提出MAREL局內算法，算法中數(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算法的空間復雜度是O(n)，時間復雜度是O(nlogn)，最壞情況漸近性能比為1.25。該算法的最壞情況漸進性能比低于同類算法的最壞情況漸進性能比，并且低于局內裝箱算法漸近性能比理論上的下確界1.536…，同時低于目前所有的局內裝箱近似算法的最壞情況漸進性能比。 此外，本文還首先提出受位置約束的有色裝箱問題。它在有色裝箱問題的基礎上加上一個約束：在有色裝箱的過程中要滿足重(長)的物品置于輕(短)的物品下方的原則，同