帶換裝次數(shù)限制的車間作業(yè)調(diào)度.pdf

1、自從1954年Johnson發(fā)表第一篇關(guān)于車間作業(yè)調(diào)度的文章以來，車間作業(yè)調(diào)度，因其在生產(chǎn)制造業(yè)中的廣泛應(yīng)用而得到了很多學(xué)者的重視。但是，由于問題本身的復(fù)雜性，如兩臺機器的作業(yè)調(diào)度問題已經(jīng)被證明是NP-困難的，經(jīng)典的算法設(shè)計技巧很難用來解決現(xiàn)實的車間作業(yè)調(diào)度問題。計算智能理論的興起，為復(fù)雜車間作業(yè)調(diào)度問題的研究提供了一種全新的方法。例如模擬退火、遺傳算法、人工神經(jīng)網(wǎng)絡(luò)等，由于其良好的性能，在車間作業(yè)調(diào)度問題的研究中發(fā)揮了重要作用。

2、>　　 車間作業(yè)調(diào)度問題的經(jīng)典描述為:給定n個工件(job)，每個工件有特定的加工工序;給定m臺機器(machine)，每臺機器負(fù)責(zé)特定工序的加工。作業(yè)調(diào)度的目標(biāo)是:求解n個工件在m臺機器上的加工順序，使得最后完工時間最小。盡管人們對很多類型的車間作業(yè)調(diào)度問題已經(jīng)做了廣泛的研究，但是對于帶換裝次數(shù)限制的車間作業(yè)調(diào)度問題，至今還沒有相關(guān)的成果（有些機器更換某個部件之后，可以加工不同類型的工件，我們稱機器更換部件的過程為“換裝”。但是頻繁

3、的換裝，會影響機器的使用壽命，并且換裝一般由人工完成，從而導(dǎo)致單位時間內(nèi)的換裝次數(shù)限制）。然而，該類型的車間作業(yè)調(diào)度問題在實際的車間生產(chǎn)過程中廣泛存在，例如輪胎制造、服裝加工等行業(yè)，都涉及到機器的換裝操作。另外，在實際生產(chǎn)中，有些機器是批量生產(chǎn)部件，一次性生產(chǎn)的部件除了滿足當(dāng)前需求之外，還會有剩余。這些剩余的部件被存儲在倉庫中，作為庫存供以后使用。很多部件都存在有效期，過了有效期之后，部件便要銷毀，這就造成了部件的浪費。如何提高庫存的利

4、用率，減少庫存浪費，也是很多企業(yè)亟待解決的問題之一。本文以帶換裝次數(shù)限制的車間作業(yè)調(diào)度問題為研究對象，并且在考慮最小化完工時間的同時，使得庫存浪費盡可能減少。
　　 針對帶換裝次數(shù)限制的車間作業(yè)調(diào)度問題，首先就不考慮庫存的情況設(shè)計了遺傳算法、模擬退火算法、蟻群算法、模擬退火+遺傳算法、蟻群算法+遺傳算法等五個智能算法。就考慮庫存的情況，我們把目標(biāo)函數(shù)設(shè)為最后完工時間和庫存浪費的加權(quán)之和，然后對以上五個算法進(jìn)行修改并成功應(yīng)用于該種

5、情況的求解。最后，設(shè)計了10個不同規(guī)模的調(diào)度實例，分別就有無庫存的情況，對算法進(jìn)行了實驗，并進(jìn)行了詳細(xì)的分析。實驗結(jié)果表明，就只考慮完工時間而言，模擬退火+遺傳算法得到的結(jié)果最好，其次是模擬退火算法，遺傳算法比蟻群算法+遺傳算法表現(xiàn)稍好，而蟻群算法表現(xiàn)最差。就同時考慮完工時間和庫存而言，模擬退火+遺傳算法得到的結(jié)果最好，其次是模擬退火算法，其它三個算法表現(xiàn)不相上下，但是，蟻群算法+遺傳算、蟻群算法的庫存利用率多數(shù)情況下較其它算法高，其它