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

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

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

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