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

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

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

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

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