多階段流水生產(chǎn)系統(tǒng)的批量流調(diào)度問題

【摘 要】調(diào)度問題要求在空間和時(shí)間上合理安排任務(wù)和資源，在滿足技術(shù)和資源約束限定下，使預(yù)定目標(biāo)達(dá)到最優(yōu)。

【關(guān)鍵詞】多階段；批量流；調(diào)度

一、引言

調(diào)度問題通?？砂淳途w時(shí)間或加工時(shí)間進(jìn)行劃分。按工序就緒時(shí)間的異同可劃分為動(dòng)態(tài)調(diào)度問題和靜態(tài)調(diào)度問題；按工件加工時(shí)間的性質(zhì)可分為確定型調(diào)度問題和非確定型調(diào)度問題。

二、批量流調(diào)度問題的概念和分類

1.基本概念與分類

批量流就是把一個(gè)被加工的產(chǎn)品批量劃分為若干個(gè)子批量，按子批量分別組織加工和工序間的運(yùn)輸，當(dāng)在一臺(tái)機(jī)器上一個(gè)子批量加工完成以后，這個(gè)子批量無(wú)須等待，就可以直接轉(zhuǎn)運(yùn)到下臺(tái)機(jī)器加工。

2.Lot Streaming調(diào)度問題的一般假設(shè)條件

（1）假設(shè)在零時(shí)刻，所有產(chǎn)品準(zhǔn)備就緒。（2）產(chǎn)品數(shù)、機(jī)器數(shù)、每種產(chǎn)品每個(gè)零件在各臺(tái)機(jī)器上的加工時(shí)間及產(chǎn)品加工的工藝約束—加工路線是已知的。（3）被加工的產(chǎn)品批量劃分為若干個(gè)子批量，按子批量分別組織加工和工序間的運(yùn)輸。（4）當(dāng)在一臺(tái)機(jī)器上一個(gè)子批量加工完成以后，而且相繼機(jī)器空閑，這個(gè)子批量無(wú)須等待其余子批量在此機(jī)器上的加工完成，就可以直接轉(zhuǎn)運(yùn)到下臺(tái)機(jī)器上進(jìn)行加工。（5）子批量的大小是一致的。（6）子批量的加工時(shí)間和它的大小成正比，。（7）獨(dú)立的調(diào)整時(shí)間（或可分離的設(shè)置時(shí)間）：在一臺(tái)機(jī)器上，從加工一種產(chǎn)品轉(zhuǎn)到加工另一種產(chǎn)品要求機(jī)器的調(diào)整。（8）允許產(chǎn)品在工序之間等待，允許機(jī)器在產(chǎn)品未到達(dá)時(shí)閑置。

以上假設(shè)條件允許改變和放松，由此可構(gòu)成不同類型的Lot Streaming調(diào)度問題。

3.多階段、多產(chǎn)品流水車間批量流調(diào)度問題的符號(hào)和變量

以最小化最大完工時(shí)間為目標(biāo)函數(shù)，考慮各產(chǎn)品的子批量可以混排的情況，給出多階段、多產(chǎn)品流水車間調(diào)度問題的數(shù)學(xué)模型。

符號(hào)和變量：

決策變量：

三、混合遺傳算法的設(shè)計(jì)

1.產(chǎn)品的基因編碼

舉例說明，例如：對(duì)于產(chǎn)品，可以表示成：

其中“*”代表的是第個(gè)產(chǎn)品的一個(gè)單位產(chǎn)品，兩個(gè)“1”之間代表這個(gè)產(chǎn)品的一個(gè)子批量所含的單位產(chǎn)品數(shù)。也就是，用位來(lái)表示，第一位是“1”，表示一個(gè)子批量從這里開始，到下一個(gè)“1”之間就是這個(gè)子批量所含的產(chǎn)品零件數(shù)，再?gòu)倪@個(gè)“1”到下一個(gè)“1”是另一個(gè)子批量所含的產(chǎn)品零件數(shù)，直到最后一位“1”。為了存儲(chǔ)方便，基因表示成所有“1”所在的位置，如下：

其中的數(shù)字是表示“1”所占的位置。那么這個(gè)產(chǎn)品的三個(gè)子批量大小是：

計(jì)算公式是：第個(gè)子批量大小=第+1個(gè)位置的數(shù)值-第個(gè)位置的數(shù)值-1。

另外“*”所占據(jù)的位置可以表示成：

2.染色體

舉例說明：

例如：對(duì)于4種產(chǎn)品，每種產(chǎn)品所含零件數(shù)分別是25、30、24、28，子批量數(shù)分別是3、5、3、4，子批量大小如表3.1中所示這樣一個(gè)問題。

表3.1 產(chǎn)品的子批量大小

Sublot1sublot2sublot3sublot4sublot5合計(jì)

產(chǎn)品17612 25

產(chǎn)品251126630

產(chǎn)品3987 24

產(chǎn)品481055 28

3.初始種群

對(duì)于產(chǎn)品來(lái)說，需要滿足，第一個(gè)子批量的大小是隨機(jī)從1到選的一個(gè)整數(shù)；第個(gè)子批量（第二個(gè)到第個(gè)子批量）是從1到中隨機(jī)選取的整數(shù)；第個(gè)子批量=。

4.適值函數(shù)設(shè)計(jì)

最初試驗(yàn)用的適值函數(shù)是：

（9）

其中是這一種群中產(chǎn)生的最大，迭代初期適值函數(shù)值相差很大，選擇壓力大不適于擴(kuò)展空間搜索，迭代后期適值函數(shù)值相差不大，選擇壓力小不適于局部最優(yōu)搜索。

為了改變這種情況，迭代初期適值函數(shù)設(shè)計(jì)成：

（10）

在原適值函數(shù)加上后，迭代初期適值函數(shù)值相差不大，選擇壓力小，適于擴(kuò)展空間搜索。

迭代中期適值函數(shù)設(shè)計(jì)成：

（11）

迭代中期適值函數(shù)趨于平穩(wěn)，相差不是特別大，因而無(wú)需加上。

迭代后期適值函數(shù)設(shè)計(jì)成：

（12）

迭代后期適值函數(shù)值趨于常量，相差不大，因而將原適值函數(shù)平方，加大選擇壓力。試驗(yàn)表明后一個(gè)適值函數(shù)好于前者。

其中的計(jì)算如下：

（13）

（14）

（15）

（16）

（17）

其中是產(chǎn)品在機(jī)器上的加工時(shí)間。

5.選擇

每個(gè)染色體的選擇概率（即生存概率）正比于它的適值：（1）對(duì)各染色體計(jì)算適值；（2）計(jì)算種群中所有染色體的適值之和；（3）對(duì)各染色體，計(jì)算選擇概率；（4）對(duì)各染色體，計(jì)算累積概率。

6.交叉方案

（1）每種產(chǎn)品的交叉方案：采用的是單斷點(diǎn)交叉法。隨機(jī)選取一個(gè)斷點(diǎn)進(jìn)行交叉，交換雙親上斷點(diǎn)的右端，產(chǎn)生新的后代。（2）染色體的交叉方案：采用對(duì)染色體中所有產(chǎn)品都進(jìn)行交叉和部分染色體進(jìn)行交叉兩種交叉方案。

7.修復(fù)方案

由于交叉操作后，產(chǎn)生了不可行的染色體，所以必須進(jìn)行修復(fù)。

若產(chǎn)生編碼如下：

19691821

基因編碼就是不可行的，第二位和第四位都是9，對(duì)這種情況就要進(jìn)行修復(fù)。這里采用的修復(fù)方法是先對(duì)染色體中的數(shù)字進(jìn)行排序，然后對(duì)兩個(gè)位置上數(shù)值相同的基因進(jìn)行修復(fù)，本例中的第三位和第四位數(shù)值相同，隨機(jī)選取其中的一個(gè)9，在零件所占的位置上隨機(jī)選取一個(gè)數(shù)值進(jìn)行替換。

8.變異方案

每種產(chǎn)品的變異方案：

舉例說明：例如對(duì)進(jìn)行變異，隨機(jī)選取一個(gè)除了兩端位置的任何一個(gè)位置，再隨機(jī)從零件所占據(jù)的位置中隨機(jī)選一個(gè)替換。

15812

9.排序

1983年M.nawaz，E.E.Enscore和I.Ham提出NEH算法。據(jù)文獻(xiàn)報(bào)道，該算法是目前已知的求解排列排序Flow shop調(diào)度問題最小加工周期時(shí)性能最好的算法之一。該算法是基于這樣一個(gè)基本假設(shè)：一個(gè)產(chǎn)品的總加工時(shí)間越長(zhǎng)，它具有越高的優(yōu)先權(quán)。

具體步驟如下：（1）將個(gè)產(chǎn)品按各自在機(jī)器上加工的總時(shí)間降序排列；（2）單獨(dú)考慮開始兩個(gè)產(chǎn)品，并以極小化部分加工全長(zhǎng)為目標(biāo)將它們排序；（3）對(duì)轉(zhuǎn)入步驟（4）；（4）將初始排列中的產(chǎn)品插入到前面?zhèn)€可能位置中的一個(gè)位置，而使部分加工全長(zhǎng)最小。

10.混合遺傳算法流程

（1）生成初始種群；（2）交叉、變異修復(fù)；（3）NEH排序；（4）選擇；（5）若未達(dá)終止條件，轉(zhuǎn)2；否則結(jié)束，輸出結(jié)果。

四、計(jì)算實(shí)驗(yàn)

通過實(shí)驗(yàn)發(fā)現(xiàn)非混合遺傳算法比混合遺傳算法效果好，所以下面的實(shí)例均是選中非混合遺傳算法。

Example1.實(shí)驗(yàn)是以10*10（10個(gè)工件和10臺(tái)機(jī)器）為模型的。

設(shè)置：不考慮設(shè)置時(shí)間，可等待；

每個(gè)工件所含的單元數(shù)和必須被分的子批量數(shù)如下：

每個(gè)工件每個(gè)單位在每臺(tái)機(jī)器上的加工時(shí)間：

圖1

不采用批量流的方法時(shí)，用NEH算法進(jìn)行計(jì)算，最小最大完工時(shí)間是2969；采用批量流方法時(shí)參數(shù)選擇：種群大小是100，PC=0.65，PM=0.2，Ps取0.08和0.9，運(yùn)行1000代，分別按混合遺傳和非混合遺傳。目標(biāo)函數(shù)均值走勢(shì)如圖1。

迭代中止條件是迭代2000代時(shí)計(jì)算產(chǎn)生的最小最大完工時(shí)間是1764。

參考文獻(xiàn)：

[1]Saw ik T.A multilevelmachine and vehicle scheduling in a flexible manufacturing system[J].Mathematic and Computer Modelling，1996，23（7）：45-57.

[2]Bilge U.U lusoy G A time window approach to simultaneous scheduling of machines andmaterial handling system in an FMS[J].Operations Research，1995，43（6）：1058-1069.

[3]Logendran R.A sonthinen a tabu search-based approach for scheduling job-shop type flexible manufacturing system s[J].Journal of Operational Research Society，1997，48：244-277.

[4]方劍.席裕庚.基于遺傳算法的Job Shop靜態(tài)調(diào)度算法[J].上海交通大學(xué)學(xué)報(bào)，1997，31（3）：49-52.