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

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