基于物品移動的局內(nèi)裝箱算法的改進(jìn)
2008-01-01 00:00:00楊鼎強(qiáng)王晨
計算技術(shù)與自動化 2008年2期
摘要：局內(nèi)裝箱問題在多處理器調(diào)度、資源分配和日常生活中的計劃、包裝、調(diào)度等優(yōu)化問題中有著極為重要的應(yīng)用。提出一個新的局內(nèi)線性算法MAMOV，算法中采用“物品移動模型”，當(dāng)新物品到達(dá)時，允許首次入箱后的固定數(shù)目的物品再次移動；證明MAMOV算法的最壞情況漸近性能比1.25，該算法最壞情況漸近性能比低于同類算法最壞情況漸近性能比的下界值。
關(guān)鍵詞：裝箱問題；局內(nèi)算法；近似算法；復(fù)雜性
中圖分類號：TP301.5 文獻(xiàn)標(biāo)識碼：A
