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

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

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

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