基於問題結構特性的混合差分進化調度理論與方法研究

《基於問題結構特性的混合差分進化調度理論與方法研究》是依託昆明理工大學，由錢斌擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：基於問題結構特性的混合差分進化調度理論與方法研究
• 項目類別：青年科學基金項目
• 項目負責人：錢斌
• 依託單位：昆明理工大學

項目摘要

生產調度問題通常具有NP（Nondeterministic Polynomial, NP）難、大規模、多目標、不確定、強約束等複雜性，智慧型最佳化調度理論和高效算法的研究一直是學術界和工業界的熱點課題。從複雜生產調度問題的研究現狀來看，將問題結構的特有性質和智慧型最佳化算法有機結合是設計高效算法的關鍵。本項目將研究基於複雜生產調度問題結構特性的混合差分進化（Differential Evolution,DE）調度理論與方法：① 研究調度問題結構特性的相關理論；② 研究混合DE的統一框架、收斂性理論和高性能算法策略；③ 給出基於問題結構特性的複雜流水線系列調度問題、複雜作業車間系列調度問題、不確定調度問題和半導體生產調度問題的高性能混合DE算法。研究成果將豐富和深化已有的最佳化調度理論，還可對指導實際生產提供有益的幫助。

結題摘要

本項目取得了預定研究成果。項目的主要工作歸納如下：1、通過分析不同指標下帶序相關設定時間和釋放時間的零等待流水線調度問題的結構特性，提出了結合差分進化（Differential Evolution, DE）機制和問題解結構性質的一系列HDE算法，並探討了不同操作和參數對算法性能的影響。基於算例的大量仿真結果和算法比較，驗證了所提算法的高效性。2、針對加工時間不確定的有限緩衝區置換流水線調度問題，通過在DE算法中融合最優計算量分配（Optimal Computing Budget Allocation, OCBA）技術以及假設檢驗（Hypothesis Test, HT）策略，提出了一種魯棒的混合DE算法，記作OHTDE算法，並基於Markov鏈理論分析了該算法的收斂性；針對工件動態到達設定時間序相關的零等待流水線調度問題，提出了滾動視窗策略和混合DE算法相結合的有效處理方法，並在理論上分析了所提策略的全局性能。3、在所提HDE算法基礎上，有機融合針對具體問題的特性而設計的有效局部搜尋操作，提出了解決m台機器可重入置換流水線調度問題的混合種群增量學習算法，以及解決帶不同工件重入次數的可重入置換流水線調度問題的混合DE算法。基於算例的大量仿真結果和算法比較，驗證了所提算法的有效性和魯棒性。4、通過分析可重入多目標作業車間調度問題的解空間特點，結合拓展的活動化解碼策略和變鄰域搜尋策略，設計了一種多目標混合DE算法。基於算例的仿真結果和算法比較，驗證了所提算法的有效性。5、針對聚丙烯生產過程批調度問題，參與了實地調研和問題建模，將實際問題建模為一種複雜的多階段柔性流水線調度問題；針對流水線調度問題，參與提出了一種機率混合進化算法。基於算例的大量仿真結果和算法比較，驗證了所提模型和算法的有效性。以上的研究成果可豐富和深化已有的最佳化調度理論，還可對實際工程提供幫助。