約束流水調(diào)度問(wèn)題的混合禁忌搜索算法.pdf

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

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

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