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