一個特殊資源約束項目調(diào)度問題模型及其優(yōu)化算法研究.pdf

1、項目調(diào)度問題在企業(yè)生產(chǎn)中有著很重要的作用，與生產(chǎn)效率、成本密切相關(guān)。由于企業(yè)生產(chǎn)過程的多樣性，經(jīng)典資源約束項目調(diào)度問題(RCPSP)在實際生產(chǎn)中并不適用，所以，本文基于某企業(yè)的實際需求，在RCPSP基礎(chǔ)上加入了工位、工件等新的概念，增加了工位對可更新資源、工件加工的約束，設定最小化總流程時間和最小化總偏差時間為求解目標，提出了一個新的項目調(diào)度問題模型—特殊資源約束項目調(diào)度問題(SRCPSP)，用以解決實際調(diào)度問題。
　　由于RCP

2、SP是NP-hard問題，而SRCPSP約束更為復雜，所以，只能使用啟發(fā)式算法進行求解。本文首先使用基于串行進度生成機制和優(yōu)先規(guī)則的啟發(fā)式算法對SRCPSP進行求解，提出了三大類規(guī)則分別用于選擇工位、選擇資源和選擇工序，實驗表明該算法可以快速生成一個初始可行解。然后，在此基礎(chǔ)上，對初始解進行優(yōu)化算法研究。首先，本文實驗了使用迭代局部搜索的方法，研究了使用迭代局部搜索時解的表示方式、鄰域結(jié)構(gòu)、擾動策略等，然而研究表明，由于工件在工位間移動

3、的巨大時間代價，迭代局部搜索并不適用于帶工位約束的項目調(diào)度問題。之后，考慮到工序的調(diào)度主要是合適的工位和資源，所以本文實驗了為工序隨機選擇工位和資源，結(jié)果表明，隨機選擇工位可以產(chǎn)生更好的結(jié)果。根據(jù)此結(jié)果，本文將蟻群優(yōu)化算法—最大最小螞蟻系統(tǒng)(MMAS)—應用到工位選擇上，并用實驗確定了蟻群算法中各項參數(shù)。實驗表明，使用最大最小螞蟻系統(tǒng)優(yōu)化工位選擇過程的方法是切實有效的，并且在生成相同數(shù)量解的情況下，相較于隨機選擇是穩(wěn)定較優(yōu)的。