Job Shop系統(tǒng)任務(wù)分配與能力規(guī)劃耦合優(yōu)化問題—應(yīng)用并行遺傳算法.pdf

1、生產(chǎn)系統(tǒng)的任務(wù)分配問題和能力規(guī)劃問題作為兩個(gè)單獨(dú)的子問題，已經(jīng)得到廣泛的研究。其中，任務(wù)分配問題是指在零件加工路線已知的基礎(chǔ)上對系統(tǒng)中各個(gè)加工中心的生產(chǎn)任務(wù)進(jìn)行合理分配，使得加工中心之間滿足負(fù)荷平衡要求；能力規(guī)劃問題是指合理安排加工中心機(jī)器數(shù)量以滿足生產(chǎn)成本要求。目前為止，這兩個(gè)問題都是作為相互獨(dú)立的子問題展開研究。也就是說，解決任務(wù)分配問題時(shí)，通常假設(shè)能力規(guī)劃的結(jié)果已知；同樣的，能力規(guī)劃問題的研究也是建立在任務(wù)分配的結(jié)果已知的基礎(chǔ)上的

2、。然而，實(shí)際情況中，生產(chǎn)系統(tǒng)任務(wù)分配問題和能力規(guī)劃問題之間相互耦合。在給加工中心分配生產(chǎn)任務(wù)的同時(shí)，需要調(diào)節(jié)加工中心生產(chǎn)設(shè)備數(shù)量，以便順利完成該加工任務(wù)；同樣，在決定加工中心的生產(chǎn)設(shè)備數(shù)量時(shí)，需要根據(jù)生產(chǎn)成本約束來調(diào)節(jié)加工中心的生產(chǎn)任務(wù)。 不同于已有的工作，本文在排隊(duì)網(wǎng)絡(luò)的基礎(chǔ)上，對相互耦合的散件加工型制造系統(tǒng)（Job Shop）任務(wù)分配問題和能力規(guī)劃問題展開并行研究。分別以開環(huán)散件加工型制造系統(tǒng)（Open Job Shop，O

3、JS）和閉環(huán)散件加工型制造系統(tǒng)（Closed Job Shop， CJS）為例展開分析，建立上述兩類系統(tǒng)的數(shù)學(xué)模型。其中任務(wù)分配問題的優(yōu)化目標(biāo)是使得各個(gè)加工中心負(fù)荷平衡；能力規(guī)劃問題的優(yōu)化目標(biāo)是使得在生產(chǎn)率滿足一定要求的前提下生產(chǎn)成本最小。本文應(yīng)用排隊(duì)網(wǎng)絡(luò)理論計(jì)算兩個(gè)優(yōu)化問題的性能指標(biāo)，提出一種并行遺傳算法（Concurrent Genetic Algorithm，CGA）來解決上述耦合優(yōu)化問題，并且通過數(shù)值實(shí)驗(yàn)驗(yàn)證了此算法的有效性。

4、 本文的主要研究成果如下： 1．建立了開環(huán)和閉環(huán)Job Shop型制造系統(tǒng)任務(wù)分配問題和能力規(guī)劃問題的耦合優(yōu)化模型。 利用排隊(duì)理論分析法，建立了開環(huán)和閉環(huán)Job Shop系統(tǒng)任務(wù)分配問題和能力規(guī)劃問題的數(shù)學(xué)模型。這里，一個(gè)問題（任務(wù)分配問題或能力規(guī)劃問題）的決策變量都是另一個(gè)問題目標(biāo)函數(shù)或約束條件中的參數(shù)，從而形成耦合。由于這兩個(gè)優(yōu)化目標(biāo)的相互沖突，二者難以同時(shí)達(dá)到最優(yōu)，為此以獲得二者的滿意性能為目標(biāo)，建立弱化的耦

5、合優(yōu)化模型。 2．并行遺傳算法的提出。該方法簡單易實(shí)現(xiàn)，簡化了多個(gè)優(yōu)化目標(biāo)的并行優(yōu)化過程。 在遺傳算法的基礎(chǔ)上，利用可以將不同優(yōu)化問題的決策變量編碼到同一條染色體的編碼思想，讓一條染色體的一個(gè)完整進(jìn)化過程包含多個(gè)子遺傳算法。每個(gè)優(yōu)化目標(biāo)對應(yīng)一個(gè)子遺傳算法，它們并行運(yùn)行。通過適應(yīng)度函數(shù)的構(gòu)造來控制優(yōu)化方向，其中考慮了每個(gè)優(yōu)化問題的決策變量對多個(gè)目標(biāo)函數(shù)的影響。 3．進(jìn)行了數(shù)值試驗(yàn)，驗(yàn)證了這一并行遺傳算法的有效性。