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

1、作業(yè)加工調(diào)度問(wèn)題不僅是NP難的,還被認(rèn)為是最難的組合最優(yōu)化問(wèn)題之一.已經(jīng)知道,為解決工業(yè)生產(chǎn)、經(jīng)濟(jì)管理和網(wǎng)絡(luò)通訊等諸多方面的問(wèn)題,都要借助于求解這個(gè)問(wèn)題.優(yōu)質(zhì)、快速地求解作業(yè)加工調(diào)度問(wèn)題,既有重要的理論意義,又能帶來(lái)巨大的經(jīng)濟(jì)效益.轉(zhuǎn)換瓶頸程序(SB)是一個(gè)很有代表性的求解作業(yè)加工調(diào)度問(wèn)題的啟發(fā)式算法.但是它遇到一個(gè)困難,就是它不能夠得到某些實(shí)例的可行解.以此為切入點(diǎn),一個(gè)很有力的定理在此被證明,它部分地解決了SB算法的這一困難.而且,

2、基于這個(gè)定理,一個(gè)新的啟發(fā)式算法——改進(jìn)的轉(zhuǎn)換瓶頸程序(ISB)被提出來(lái).該算法繼承了SB的"轉(zhuǎn)換瓶頸機(jī)"的思想,然而放松了界定瓶頸機(jī)的條件,就是不要求每一臺(tái)機(jī)器的排序是最優(yōu)的.上述定理的推論表明,ISB不會(huì)遇到與SB相同的困難.對(duì)大量實(shí)例的計(jì)算結(jié)果表明,ISB算法在計(jì)算速度和所得到的解的優(yōu)度上幾乎都優(yōu)于SB算法.在所采用的48個(gè)實(shí)例中,ISB有29個(gè)的解優(yōu)于SB,而SB只有2個(gè)的解優(yōu)于ISB.ISBB是ISB的一個(gè)改進(jìn)版本,它是將IS

3、B與回溯算法結(jié)合起來(lái)而得到的,ISBB優(yōu)于SB的第二版本SBII.在這48個(gè)實(shí)例中,ISBB有18個(gè)的解優(yōu)于SBII,而SBII只有在9個(gè)的解優(yōu)于ISBB.雖然與新近的某些算法相比,ISB和ISBB的性能不是足夠高,但是它們可以作為很好的求解作業(yè)加工調(diào)度問(wèn)題的基本算法.在已有的求解作業(yè)加工調(diào)度問(wèn)題的諸多啟發(fā)式算法中,禁止(Tabu)搜索算法以其高效性而倍受人們重視.HLS是結(jié)合ISB算法和Tabu搜索算法所得到的一個(gè)新的混合式鄰域搜索算

4、法.它采用ISB算法來(lái)產(chǎn)生初始解,這使得它的初始解比其它的鄰域搜索算法的優(yōu).HLS還采用新的搜索技術(shù)以改進(jìn)Tabu搜索算法的兩個(gè)很重要的搜索策略——集中搜索策略和分散搜索策略.SHLS是對(duì)HLS進(jìn)行另外一種改進(jìn)的結(jié)果.它將一種隨機(jī)策略引入HLS之中,每次從若干臺(tái)"準(zhǔn)瓶頸機(jī)"中隨機(jī)選取一臺(tái)來(lái)作為當(dāng)前瓶頸機(jī),并對(duì)此機(jī)器所加工工序的次序進(jìn)行重新排列.用這種辦法來(lái)降低對(duì)瓶頸機(jī)的限制條件,以期最終消除瓶頸機(jī)的概念.從大量的模擬計(jì)算來(lái)看,SHLS實(shí)