基于仿真集成的遺傳算法在單元制造系統(tǒng)中的人機調(diào)度問題優(yōu)化

康雯軒

（燕山大學(xué) 經(jīng)濟管理學(xué)院，河北 秦皇島 066000）

0 引言

單元生產(chǎn)是基于成組技術(shù)發(fā)展出來的，也是精益生產(chǎn)的一部分。單元生產(chǎn)的優(yōu)點有：生產(chǎn)中產(chǎn)生的在制品庫存少，物料搬運成本少，單元內(nèi)設(shè)備利用率較高等[1]。

Seru生產(chǎn)方式是指以Seru為基本單位的生產(chǎn)線組織，由流水線生產(chǎn)方式分割、轉(zhuǎn)化為多個Seru的生產(chǎn)組織形式[2]。本文研究的背景是把Seru生產(chǎn)運用到單元制造中，單元中不再單一的考慮機器，而是在單元里把機器因素與人共同考慮，本文采用仿真集成的遺傳算法來求解seru生產(chǎn)下的單元制造車間調(diào)度多目標(biāo)優(yōu)化問題。

1 模型建立

1.1 問題描述

假設(shè)n個零件按照固定的工序依次通過不同的單元，每個單元內(nèi)包含一定數(shù)量的機器和多能工，零件的工序可以在不同的單元內(nèi)完成，但是零件在單元內(nèi)的移動是有時間的消耗。

1.2 參數(shù)符號

n：零件的數(shù)量；

m：機器的數(shù)量；

o：工人的數(shù)量；

oij：第j零件的第次的操作，

pijk：操作oij在機器上的處理時間；

ptijw：工人w處理操作oij時間；

stij：生產(chǎn)oij所需要的準備時間；

CTij：oij的加工完成時間；

tuu'：部件從單元u移動到單元u'時的單元間移動時間，當(dāng)u=u'時tuu'=0；

c：單元的數(shù)量；

dj：j零件的最長生產(chǎn)時間；

Dj：零件j的最晚交貨時間；

Fij：Oij作業(yè)的完成時間；

Sij：Oij作業(yè)的開始時間

決策變量：

1.3 建立模型

約束（1）確保每個操作只能分配給其中一個機器。約束（2）確保每個操作只能分配給其中一個工人。式（3）確保工人只能被分配給一個單元，約束（4）表示從這個工序的開始時間到下個工序的完成時間是由機器與工人的處理時間和部件的移動時間構(gòu)成的。約束（5）表示如果指定操作機器和零件處在不同的單元中，單元間移動時間將發(fā)生。約束（6）是零件到期日約束。約束（7）表示操作的加工完成時間表示。約束（8）限制了一個單元內(nèi)的工人數(shù)；約束（9）確保訂單只能分配到可行的單元。

2 仿真集成的混合遺傳算法

仿真集成混合遺傳算法（SHGA）是將離散事件仿真（DES）和遺傳算法（GA）集成在一起的改進遺傳算法，在SHGA種群中的每個個體都使用離散事件仿真來評估。

2.1 編碼

本文采用三層編碼方式對每個零件的每個操作數(shù)所對應(yīng)的機器和單元進行編碼，其中第一層中的值表示零件j的索引，其出現(xiàn)的次數(shù)表示操作i的索引，第二層表示操作所在的機器，第三層代表操作所在的機器所在的單元。

2.2 適應(yīng)度函數(shù)

本文求解的是最小化目標(biāo)函數(shù)，因此通過上面初始個體的染色體編碼數(shù)據(jù)計算適應(yīng)度，通過保留較小目標(biāo)函數(shù)值的個體，即適應(yīng)度大的個體，構(gòu)成下一代。

2.3 選擇運算

本文使用輪盤賭的方法選擇優(yōu)秀的個體，其主要思想是選擇路徑的概率與適應(yīng)度成正比，適應(yīng)度越大，選擇概率越大。

2.4 交叉運算

本小節(jié)提出了一種擴展的偏序交叉算子，用于從一對父染色體（父染色體1和2）中生成子染色體（子染色體1和2）。首先我們把所有部分隨機分成兩組，即S和S0。我們將那些部分包含在集合S中的基因從父代1復(fù)制到子代1的相同位置。我們用來自父代2的那些基因填充子代1的剩余空白位置，這些基因具有屬于集合S0的部分，而不改變它們的序列。子2的生成方式類似。

2.5 變異運算

應(yīng)用隨機插入變異算子。突變操作通過從親本染色體中隨機選擇兩個基因i和j，并將位置j的三層基因插入位置i之前，進行突變。

2.6 算法框架

通過上述分析，本文提出的仿真集成混合遺傳算法流程圖如圖1所示。

圖1 仿真集成混合遺傳算法流程圖

3 數(shù)值實驗

本實例問題包括6個零件、10臺機器和2個單元。每個零件的工序次數(shù)都是6，其中工件加工計劃如表2所示。在遺傳算法中，使用這些參數(shù)的不同組合進行仿真，以對它們進行微調(diào)，其參數(shù)設(shè)置結(jié)果如表1、表2所示，人工數(shù)量為10人。本文的算例所使用的仿真集成混合遺傳算法（SHGA）使用MATLAB編程。

表1 仿真集成混合遺傳算法參數(shù)

表2 工件加工計劃表

通過仿真得到最佳函數(shù)值從最初72min下降到最小值48min，從計算的最優(yōu)的結(jié)果來看，人工成本達到了最小，由此可見本模型可以共同考慮機器與工人合作生產(chǎn)。為了對比算法有效性，本文使用蟻群算法進行對比，對比結(jié)果如表3所示。通過實例可以看出，離散事件仿真集成的遺傳算法在計算實例過程中表現(xiàn)良好，得到了良好的結(jié)果。見圖3。

表3 SHGA 與ACO 對比

圖3 使用SHGA 算法求解的甘特圖

4 結(jié)語

本文提出了一種用于單元制造系統(tǒng)與seru單元結(jié)合的工序調(diào)度的仿真集成遺傳算法，以最小化最大完成時間為目標(biāo)。仿真集成遺傳算法提供了一種解決方案，可以共同考慮機器與工人合作生產(chǎn)。從計算結(jié)果表明，仿真集成遺傳算法在合理的時間內(nèi)表現(xiàn)良好，在求解目標(biāo)問題上得到了良好的結(jié)果。