求解車間作業(yè)調(diào)度問題的啟發(fā)式算法.pdf

1、車間作業(yè)調(diào)度問題就是用一組機(jī)器加工一組工件,每個工件有若干個工序,把這些工序按照一定次序加工,在加工的過程中要滿足問題特定的約束條件,并使加工完所有的工序后形成的最終調(diào)度的時間跨度盡可能短.該問題是一個典型的NP完全問題.求解車間作業(yè)調(diào)度問題實際上就是給待加工的工序確定一個調(diào)度順序并達(dá)到優(yōu)化目的.為了確定工序的調(diào)度順序,可以用優(yōu)先指派規(guī)則.算法MP是一個基于優(yōu)先指派規(guī)則的啟發(fā)式算法,該算法會給被考察的工序子集中的每個工序都賦予一個優(yōu)先級

2、,優(yōu)先調(diào)度優(yōu)先級最高的工序.算法MP通過貪心法一次確定了工序的開工時間,因而速度很快,但搜索范圍有限.而結(jié)合了算法MP和枚舉策略的枚舉算法MPE則可以通過枚舉來增加算法的搜索范圍.求解車間作業(yè)調(diào)度問題的局部搜索算法LS是按照局部搜索的一般步驟,結(jié)合了具體問題構(gòu)造出來的.由于算法LS中提出的初始解方案、鄰域構(gòu)造方案以及搜索策略的方案都是針對本問題的,因而,算法LS能夠比較好的求出問題實例的近似解.實際測試結(jié)果表明,這三個啟發(fā)式算法對于求解