拉格朗日鬆弛的改進及其在動態HFS調度中的套用研究

拉格朗日鬆弛的改進及其在動態HFS調度中的套用研究

《拉格朗日鬆弛的改進及其在動態HFS調度中的套用研究》是依託鄭州大學,由軒華擔任項目負責人的青年科學基金項目。

基本介紹

  • 中文名:拉格朗日鬆弛的改進及其在動態HFS調度中的套用研究
  • 項目類別:青年科學基金項目
  • 項目負責人:軒華
  • 依託單位:鄭州大學
項目摘要,結題摘要,

項目摘要

許多實際生產與物流管理問題,如生產調度問題,都可歸結為組合最最佳化問題。由於理論上多數生產調度問題都屬於NP-hard問題,而實際生產調度問題因為包含更為複雜的約束和目標函式從而多數也是強NP-hard,拉格朗日鬆弛(LR)算法作為一種典型的基於最最佳化的近似算法,因其疊代的方向性和算法的自我評價性,使它已成功用於求解多類組合最最佳化問題。本課題對改進LR算法進行基礎研究,並以從鋼鐵生產中提煉出的動態HFS調度為對象進行套用研究。首先,從LR的結構和影響算法性能的要素出發,提出LR算法的改進算法;其次,從鋼鐵生產實際提煉出帶不同生產特徵的動態HFS調度問題,建立數學規劃模型;然後,研究改進LR的具體實現方式;最後,以鋼鐵生產為背景對所提出的理論方法進行驗證。本課題的研究不但擴展了現有的LR算法理論,而且其套用對實際生產具有重要的理論價值,在工業中的套用將有助於降低能耗和成本,提高產品生產率。

結題摘要

拉格朗日鬆弛算法作為基於最最佳化的近似算法,因其疊代的方向性和算法的自我評價性,使其已成功用於求解多類組合最最佳化問題。本課題對拉格朗日鬆弛算法的分解策略、對偶問題求解以及子問題求解策略進行研究,並探討了它們在動態混合流水車間調度的套用。提出了結合階段分解策略的改進拉格朗日鬆弛算法,將拉格朗日鬆弛問題分解為多個同構平行機總加權完成時間問題,子問題數即為加工階段數,以帶有限運輸機的動態混合流水車間調度為研究對象對該算法進行了套用研究。提出了結合批分解策略的改進混合流水車間算法,將拉格朗日鬆弛問題分解為多個批級子問題,每個子問題包含多個有優先權要求的工序,子問題數即為批數,以初始階段為批處理機的動態混合流水車間調度問題為研究對象對該算法進行了套用研究。提出了結合代理次梯度法的改進拉格朗日鬆弛算法,它要求近似求解鬆弛問題從而獲得乘子更新方向,以帶有限等待時間的動態混合流水車間調度問題為研究對象進行了套用研究。上述算法均通過仿真驗證了有效性。針對鬆弛問題或子問題含工件或工序優先權要求的工件問題,提出了基於混合前後向動態規劃的改進拉格朗日鬆弛算法,使其能處理工件(工序)有多個緊前和緊後工件(工序)的情況,分別對帶工件或工序優先權要求的單機調度和多階段混合流水車間調度進行了套用研究。圍繞上述研究,發表和錄用論文23篇,其中SCI收錄源刊上發表論文1篇,EI收錄8篇,國家自然科學基金委員會管理科學部A類重要期刊3篇,B類重要期刊2篇,中文核心期刊17篇。
check!

熱門詞條

聯絡我們