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

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

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

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

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

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