《四維時空高效利用的裝箱調度問題》是依託華中科技大學，由何琨擔任項目負責人的面上項目。
基本介紹
- 中文名：四維時空高效利用的裝箱調度問題
- 項目類別：面上項目
- 項目負責人：何琨
- 依託單位：華中科技大學
中文摘要,結題摘要,
中文摘要
研究如下關於時空充分利用的三維空間中的長方體裝箱調度問題。已知一個形狀大小任意給定的長方體形的箱子和有限個形狀大小各自任意給定的長方體形的剛性物體，又知每個物體須在箱中連續烘烤的時間長度，考慮應如何安排每個物體的入箱時刻，以及至出箱前這段時間內它在每個時刻上的位置和方向，才能使得整個箱子的被使用時間最少。與經典裝箱問題的不同之處在於，各物體在箱子內可以改變其位置和方向。正因為如此，按本數學模型，四維時空才可以得到更真實、更充分的利用。本項研究為新鮮課題，具有高的理論和實用價值。研究的哲學途徑為擬人，即挖掘幾千年以來全人類的有關實踐經驗，利用西方近現代的數學語言，將它們說確切、說透徹、說完整，並加以有針對性的發展和提高，最後形式化為確切的求解算法。據我們所知，類似研究在國際上尚未起步，我們將作前瞻性的工作，取得創新性的成果。
結題摘要
Packing問題和調度問題有著重要的理論研究意義和廣泛的實際套用價值。 本項目對我們提出的三維空間與一維時間所構成的四維時空中長方體裝箱工作的最佳化調度問題(簡稱：四維裝箱調度問題)的模型和算法進行了研究。項目研究工作進展順利，達到了預期研究目標，推廣和發展了傳統意義上的Packing 工作，為今後更高水平的研究工作奠定了基礎。 所取得的主要成果包括：(1) 問題的建模、實參數下的弱可計算性分析、計算複雜度分析; (2) 其核心子問題二維/三維矩形Packing問題的較低複雜度的完備算法的設計，以及基於“動作空間”和“穴度”提出的一系列擬人高效算法；(3) 其三維退化問題即二維空間與一維時間所構成的三維時空中的矩形布局的最佳化調度問題（簡稱：三維裝箱調度問題）的擬人求解算法研究，與將時間簡單類比為空間的相應算法的對比研究，以及多樣性算例的自動生成算法的設計； (4)對四維裝箱調度問題的擬人求解算法研究，將時間簡單類比為空間的相應算法的對比研究，以及多樣性算例的自動生成算法的設計。 在本項目支持下，在國內外權威期刊和重要學術會議上發表和錄用了論文27篇，其中在SCI影響因子排名前20%的運籌學或計算機科學權威期刊以及理論計算機科學的權威期刊《Theoretical Computer Science》上共發表了8篇，在國內三大權威期刊《中國科學》、《計算機學報》、《軟體學報》上共發表了9篇。學術論文被SCI收錄9篇次、EI收錄18篇次、ISTP收錄2篇次。相關工作得到國內外同行的較多引用，從2011年至今僅項目負責人參與發表的論文的SCI他引為28次、Google引用為202次。 在人才培養方面，共培養博士畢業生5名，碩士畢業生9名；正在培養的博士研究生6名，正在培養的碩士研究生7名；培養了二十餘名本科生的科研興趣，指導本科生在ICDM等會議和期刊上發表了學術論文3篇。在本項目的資助下，積極參與國內外學術交流，分別與法國Picardie Jules Verne 大學、美國的史丹福大學和康奈爾大學進行了交流與合作。
