約束流水調度問題的混合禁忌搜索算法.pdf

1、作業(yè)排序與作業(yè)計劃是服務業(yè)、運輸、科研以及各種企業(yè)生產(chǎn)中普遍遇到的問題。工廠里幾臺機器出了故障，在現(xiàn)有的維修能力下，如何安排這幾臺機器的修理順序，使總體損失最小，這就是一個作業(yè)排序與作業(yè)計劃問題。車間調度是一類作業(yè)排序問題，對于在現(xiàn)有資源條件下提高工作效率和經(jīng)濟效益有重要作用。車間調度問題按工件加工路線的特征不同可以分為單件車間(Job-shop)的排序和流水車間(Flow shop)的排序。 在加工過程中工件不允許等待的流水車

2、間調度問題即為約束流水車間調度問題，也稱為無等待流水車間調度問題(no-wait flow shop)。這種約束對于當今動態(tài)的加工生產(chǎn)環(huán)境和產(chǎn)品的質量來說具有很大的實際性和重要意義，如在金屬加工業(yè)、食品加工工廠里都存在這樣的約束。由于無等待流水車間調度問題具有實際性和廣泛的應用性，所以引起了廣大研究者的注意并且提出了許多算法來解決這類問題。 車間調度是一類典型的NP-hard問題，已被證明在多項式時間內得不到最優(yōu)值。近年來對于車

3、間調度問題的求解方法主要有啟發(fā)式算法和元啟發(fā)式算法，但各有其不足之處：元啟發(fā)式算法的運行時間長，可獲得較好的解，但其解不穩(wěn)定；啟發(fā)式方法可以在較短的時間內得到魯棒性較強的解，但是極少獲得較優(yōu)的解。為了更好解決問題，研究者將一些解決某類問題較好的算法組合起來已成為目前研究的熱點。 針對單一地使用各種啟發(fā)式方法或元啟發(fā)式方法不能有效地獲得較好的解，本文提出了一種將啟發(fā)式方法與禁忌搜索TS(Tabu Search)方法相結合的混合禁忌