《裝箱問題的理論與算法》是依託浙江大學，由張國川擔任項目負責人的面上項目。
基本介紹
- 中文名：裝箱問題的理論與算法
- 依託單位：浙江大學
- 項目負責人：張國川
- 項目類別：面上項目
項目摘要,結題摘要,
項目摘要
裝箱（Bin Packing）是組合最佳化的一個經典問題。以其為基本模型構成的裝箱問題類有強烈的實際背景和深刻的算法理論意義。本項目研究若干具體裝箱問題的算法結構和性質，通過對帶個數限制的線上裝箱、元素有區間約束的裝箱、二維帶狀裝箱、一般費用下的裝箱以及感測器安置等問題的深入探討，刻畫相應問題的內在特性以及可行裝箱的充分條件和必要條件。利用這些條件分析和估計算法的上下界，試圖在算法設計與分析的思想上有所突破。在此基礎上取得重要算法結果。
結題摘要
裝箱問題一直是組合最佳化領域的熱點研究問題。經典的遺留問題不斷需要我們在算法設計與分析上創新，而各種組合最佳化模型大多與裝箱問題相關，如平行機調度、背包以及樹覆蓋等問題。本項目的研究內容可以分成三個層面，一是裝箱問題的各種變形，包括帶容量限制的平行機調度、多帶狀裝箱、線上背包、雙層背包最佳化等；二是調度算法的研究，如多核處理器的調度問題、帶加速資源的調度問題以及兩個代理的流水作業問題；三是由算法設計過渡到機制設計，首次研究了厭惡性選址問題的算法機制。 在模型方面提出了雙層背包最佳化和帶加速資源的調度，前者刻畫了博弈環境下的兩階段背包問題，後者描述了計算機信息處理環境下的資源分配模型，得到了相應的深刻算法結果。在算法理論和方法方面準確分析了帶容量限制平行機調度和帶資源擴展的線上背包問題的最優解結構，分別設計了EPTAS（有效的多項式時間近似方案）和最優的線上算法，豐富了近似方案的設計思想和線上算法的分析手段。在算法機制設計方面我們抓住了厭惡性選址問題誠實機制的核心，利用直徑定位、就近分類的思想，從特殊到一般網路分別給出了相應的有效機制。項目所得到的所有算法成果是相應問題的最好結果。 依託本項目，我們培養了優秀的博士研究生和博士後研究人員，加強和拓展了廣泛的國際學術交流，項目負責人近兩年也先後受邀擔任重要國際學術期刊《Omega-The International Journal of Management Science》和《Journal of Scheduling》的編委。
