基于啟發式遺傳算法的混合流水車間成套訂單問題研究

賈葉玲 董紹華

摘 要：針對并行機帶工藝約束的混合流水車間環境下的成套訂單問題，提出一種基于分批調度策略的啟發式遺傳算法。首先，以最大化加權成套訂單數為目標建立數學模型，對工件分批采用內層遺傳算法生成初始調度;再以外層啟發式規則轉化目標為最大加權成套訂單數，設計一種訂單評價指標用于突破交貨時間瓶頸;最后，內外層算法循環優化，直到不存在瓶頸即得到滿意解。實例驗證結果顯示，啟發式遺傳算法能在20代以內得到每組最優調度，種群規模大于50時得到最優解的概率達到70%。對比實驗結果顯示，當問題規模增加到40個工件時，遺傳算法求解時間顯著增加，在不同問題規模中臨界比最小（SCR）規則優化后的加權成套訂單數均較啟發式遺傳算法更少。啟發式遺傳算法能在實際工程中夠將加權成套訂單數提高到1.5倍以上，使加工時間平均縮短5.1%。結果表明，啟發式遺傳算法能夠改善成套訂單問題在混合流水車間環境下易陷入局部最優的問題，可在大規模復雜混合流水車間的訂貨型企業中實現計劃與生產同步，具有實際意義。

關鍵詞：混合流水車間;成套訂單;遺傳算法;啟發式規則;車間調度

中圖分類號：TP301; TP18

文獻標志碼：A

Research on Whole-set order problem of hybrid flow shop based on heuristic-genetic algorithms

JIA Yeling*， Dong Shaohua

College of Mechanical Engineering， University of Science and Technology Beijing， Beijing 100083， China

Abstract：

A heuristic-genetic algorithm based on batch scheduling strategy was proposed for the whole-set order problem in hybrid flow shop environment with process constrainted parallel machine. Firstly， a mathematical model was established with the objective of maximizing the number of weighted whole-set orders， and initial scheduling was generated by inner genetic algorithm applying to workpieces in batches. Then， the target was transformed to the maximum weighted whole-set order quantity by outer heuristic rules， and an order evaluation index was designed to break the delivery time bottleneck. Finally， the inner and outer algorithms were optimized circularly until there was no bottleneck， which means the satisfactory solution was obtained. Examples show that heuristic-genetic algorithm can obtain the optimal scheduling within 20 generations， and the probability of obtaining the optimal solution is 70% when the population size is larger than 50. The experimental results show that when the scale of the problem increases to 40 workpieces， the solving time of genetic algorithm increases significantly，

and the optimization results of Smallest Critical Ratio （SCR） rules in different scale of the problem are lower than those of heuristic-genetic algorithm.

and the number of whole-set orders optimized by Smallest Critical Ratio （SCR） rule is smaller than the heuristic-genetic algorithm in different problem sizes.

Heuristic-genetic algorithm can increase the quantity of weighted whole-set orders to more than 1.5 times in practical engineering， and shorten the processing time by 5.1% on average. The results show that the heuristic-genetic algorithm can solve the problem that the whole-set order problems are easy to fall into local optimum in the hybrid flow shop environment， and can realize the synchronization of planning and production in the large-scale and complex hybrid flow shop ordering enterprises， which has practical significance.

Key words：

hybrid flow shop; whole-set order; genetic algorithm; heuristic rule; shop scheduling

0 引言

近年來許多現代化企業生產模式由傳統備貨型生產轉變為訂貨型（Make-To-Order，MTO）生產。對于MTO型企業來說，生產活動與決策均以最大限度滿足客戶需求為目標，讓客戶滿意是企業保證市場競爭力和收益的關鍵[1]。MTO生產模式中，訂單內不同工件的交貨期不同是一種較復雜的情況，為了保證企業的訂單履約能力，提高客戶滿意度，企業需在有限生產能力下合理進行生產作業計劃安排與調度，按產品的交貨期要求交貨，一個訂單中任何一個產品誤工都會導致該訂單未按要求履約，類似情況在一些采用定制生產方式的企業比較常見（如汽車制造、船舶制造等）。這類以成套完成訂單數為目標的車間調度問題被稱為成套訂單問題。成套訂單問題的研究對MTO生產模式的企業提高服務水平和市場競爭力具有現實意義。

成套訂單問題在最小化誤工件數問題的基礎上發展而來，與最小化誤工件數相比，成套訂單問題由工件交付的準時性延伸到了訂單交付的完整性，更加能夠實現訂貨型生產的本質目標。周水銀等[2]首次就單臺機器環境下的成套訂單問題進行了研究并建立了0-1整數規劃模型。蘇亞等[3]研究了含調整時間的并行機環境下的成套訂單，采用遺傳算法求解。Yu等[4]提出了采用隨機鍵編碼的螢火蟲算法解決單機環境下的成套訂單問題。與成套訂單相似的問題是具有工件交貨時間要求的提前/拖期問題，肖世昌等[5]提出了基于分布估計算法的混合算法對隨機加工時間的Job Shop問題進行求解。桂玲等[6]提出了加入拖期工件剔除規則的改進的遺傳算法求解了工序不確定的提前/拖期問題。文獻研究表明對于以解決成套訂單問題為目標的研究多集中于理論與智能計算方法研究，方法與實際生產的結合應用有待提高。

與本文研究相關的還有混合流水車間的調度問題（Hybrid Flow Shop Problem， HFSP），HFSP是傳統流水車間與并行機車間調度問題的結合，求解難度更大，兩階段HFSP即為非確定性多項式難題（Non-deterministic Polynomial Hard， NP-Hard）問題[7]。早期對HFSP的研究多集中于相同并行機環境下[8-9]，可接受的計算時間內的求解方法主要為啟發式算法[10]，近幾年求解此類問題的多種智能方法得到了研究[11-14]。帶約束并行機是混合流水車間的一種復雜情況，是指同一工序含有多種類型并行機，在工件工藝約束下，各并行機可適用的工件規格不同。曾有學者以拖后懲罰最小為目標應用并行遺傳算法對其進行了研究[15]。

目前對于成套訂單問題的研究多為單機、單階段以及流水線環境下的研究，對于混合流水車間環境下的成套訂單問題鮮有研究。目前還未見到針對并行機帶工藝約束的混合流水車間的成套訂單問題研究。本文以某船類零件制造企業實際生產車間環境為背景，針對企業生產過程中的訂單履約能力差，客戶滿意度低等問題，設計一種結合了啟發式規則與遺傳算法的雙層算法（以下稱為啟發式遺傳算法），以最大化加權成套訂單數為優化目標，對并行機帶工藝約束混合流水車間環境下的成套訂單問題進行研究。實例驗證表明，啟發式遺傳算法能夠在大規模復雜型調度問題中以較快收斂速度得到滿意解，在實際工程中能夠顯著提高加權成套訂單數，提升企業訂單履約能力和服務水平。

1 問題描述與數學建模

1.1 問題描述

一次生產任務有n個相對獨立的工件需按照一致的方向在s道工序上加工，工件共來自H個訂單，Qh（1≤h≤H）表示訂單h的工件集，即Q1∪Q2∪…∪QH={1，2，…，n};訂單h的權重為ωh，在實際環境中ωh根據訂單h所對應的產品價值、客戶等級、利潤水平、拖期懲罰等確定;車間由M臺機器組成，每道工序至少有一類并行機，每類并行機至少有一臺;并行機具有特殊工藝約束，每個工件在各工序有適用機器集;記工件i屬于訂單h，其交貨期為Dhi，完工時間為Chi，定義工件延誤系數為Uhi（1≤h≤H，1≤i≤n），當Chi≤Dhi時 ，Uhi取0，否則取1。

另外，還有如下假設：

1）工件之間相互獨立，加工不分先后;

2）一臺機器每次只能加工一個工件，每個工件各工序只需在一臺機器上加工一次;

3）工件各工序之間存在優先加工限制，不可同時加工;

4）工件一旦開始加工，必須進行到完工，不得中途終止;

5）不考慮工件在機器之間的轉移時間以及機器準備時間;

6）工件在機器上的加工時間已知，不隨加工順序而改變;

7）所有工件到達時間為0。

根據以上假設和定義，要研究的問題為：確定工件的加工順序以及工件在各工序上的機器分配，使加權成套訂單數最大。

1.2 符號定義

Mj：第j道工序并行機集合。

NMj：第j道工序并行機數量。

MPij：工件i在第j道工序可用的機器集合，MPijMj。

tijk：工件i的第j道工序在機器k上的加工時間。

stijk：工件i的第j道工序在機器k上的開始加工時間。

etijk：工件i的第j道工序在機器k上的結束加工時間。

xijk：當工件i的第j道工序在機器k上加工時xijk=1;否則xijk=0。

rjk：第j道工序在機器k上加工的第r個任務的工件編號。

Ti：工件i的各工序加工時間總和。

1.3 模型構建

根據以上問題描述，建立數學模型如下：

F=max∑Hh=1ωhXh（1）

其中Xh為決策變量，

Xh=1， ?∑i∈QhUhi=0

0，其他

s.t.

∑kxijk≤1; i=1，2，…，n， j=1，2，…，s，k∈MPij（2）

etrjkjk≤st（r+1）jkjk; j=1，2，…，s，k∈Mj，rjk∈{i}ni=1，r=1，2，…，Njk-1（3）

etijk≤sti（j+1）k*; i=1，2，…，n， j=1，2，…，s，k∈MPij，k*∈MPi（j+1）（4）

etijk=stijk+tijk; i=1，2，…，n， j=1，2，…，s，k∈MPij（5）

若rjk=i，則：

stijk=0，????????? j=1， r=1

et（r-1）jkjk，j=1，r>1

eti（j-1）k-，r=1， j>1

max（et（r-1）jkjk，eti（j-1）k-），r>1， j>1

其中：

k∈MPij，k-∈MPi（j-1），r=1，2，…，Njk（6）

Chi=etisk;

i=1，2，…，n，ks∈MPis（7）

xijk∈{0，1}，xijk-=1，i， j，k，r（8）

式（1）為問題的目標函數，即最大化加權成套訂單數;式（2）表示每個工件在每道工序最多只能選擇一臺機器加工;式（3）表示一臺機器在同一時間只能加工一個工件;式（4）表示如果工件的前一道工序未完成，不可開始后續工序;式（5）表示對于任何工件，其每道工序的結束完工時間取決于該工序開始時間與加工時間;式（6）表示當工件i是第j道工序在機器k上加工的第r個任務時，工序開始時間取決于該工件前一道工序的結束時間與本機器的前一任務結束時間;式（7）表示任意工件的完工時間為該工件最后一道工序的結束加工時間;式（8）為變量取值范圍。

1.4 問題特點

本文所研究的并行機帶工藝約束混合流水車間的成套訂單問題與其他車間調度問題相比，具有以下特點：

1）解的組成結構復雜。

傳統調度問題可看作二維排序問題，即確定工件加工順序與開始加工時間，本文車間環境下的調度還需根據工件的特殊工藝約束合理選擇加工機器，即確定工件各階段加工排序、開始時間以及加工機器，可看作三維排序問題，解的組成結構復雜。

2）搜索空間巨大。

相對于單個階段車間調度問題，混合流水車間環境的各個階段生產排序之間存在緊密聯系，在特定優化目標下，每階段的生產排序都會對結果產生影響，只能在綜合求解空間中尋找最優解，當工件數量和工序數量增多時，可行解的數量會顯著增加，搜索空間巨大。

3）易陷入局部最優。

在尋優過程中，提高加權成套訂單數需當前未成套的訂單成套完成，而同一訂單內包含多個工件，需全部工件同時滿足交貨期要求，由于問題求解空間巨大、解的形式復雜等特點，以加權成套訂單數為目標的搜索過程難以跳出局部最優狀態。

2 算法設計

本文所研究的混合流水車間成套訂單問題屬于NP-Hard問題，在問題規模較大時，如何控制求解搜索空間，在可接受的時間范圍內得到滿意解是解決問題的關鍵。分支定界法這類深度遍歷式分析算法以及傳統遺傳算法、蟻群算法等難以適合此類問題的最優化求解。因此本文設計啟發式遺傳算法求解上述模型，基于分批調度策略對工件進行生產排序，內層采用遺傳算法以最小化完工時間進行調度優化，外層啟發式規則將目標轉化為最大化加權成套訂單數尋找相鄰解，不斷重復內外層算法循環，直至滿足目標條件。

2.1 外層啟發式規則

外層啟發式規則基本步驟如下：

步驟1 零件分批。

將全部工件的交貨期按照交貨期最早（Earliest Due Date， EDD）規則排列，得到G個不相同的交貨期時間點dg（d1

步驟2 生成調度方案。

令加工矩陣中Xh=0的訂單中全部工件pig=0，更新分組加工矩陣Pig。以加工優先級順序分批采用內層遺傳算法進行優化調度，優化目標為：

min（max（Chipig））（9）

其中，當g=1 且pig=1時，第一道工序開始時間sti1k=0;當g>1且pig=1時，sti1k為機器k的上一工序完工時間。

步驟3 分析交貨期瓶頸。

根據調度結果得到G批工件的完工時間，計算各批交貨期瓶頸值Bg：

Bg=max{B′g，0}

其中

B′g=min（max（Chipig））-dg;1≤g≤G，1≤i≤n（10）

若存在∑Gg=1Bg>0，轉步驟4。

若∑Gg=1Bg=0，則在該調度中，全部工件滿足交貨期要求，保存該加工排序方案，計算加權成套訂單數，輸出結果。

步驟4 訂單評價。

定義Vh表示訂單h對于消除交貨期瓶頸的貢獻。

Vh=∑Gg=1min（Sg，Bg）; Bg>0

其中，Sg=Tgh，????????? g=1

Tgh+max（Tg-1h-Bg-1，0），g>1

其中，Tgh=λ∑i∈QhTipig

其中，Ti為工件i的各工序加工時間總和：

Ti=∑sj=1tijkxijk

λ為一個模糊值，λTi表示生產任務中剔除工件i后可能節約的完工時間，λ與車間類型以及生產任務規模有關：

λ=（max（ChipiG））/∑Gg=1∑ni=1Tipig;

i=1，2，…，n， j=1，2，…，s，1≤g≤G，1≤h≤H，k∈MPij（11）

選擇Vh/ωh值最大的訂單h，延遲加工或拒絕接受。令訂單h的成套系數Xh=0，轉步驟2。

循環步驟2、3、4，直到∑Gg=1Bg=0。

2.2 內層改進的遺傳算法

分批調度可以看作多個以最小化完工時間為目標的混合流水車間調度問題。本文采用改進的遺傳算法作為內層算法對問題進行求解。

2.2.1 編碼與解碼

一般混合流水車間調度問題類型可看作三維排序問題，并行機帶工藝約束的混合流水車間較一般混合流水車間問題更為復雜，特殊工藝約束機器只能加工具有特定規格或工藝的工件，且可能重疊。本文采取多層編碼的方式，每層編碼分別表示不同含義，從而使一個染色體完整地表達問題的解。染色體編碼方法為整數編碼，第一層編碼表示所有全部工序的加工順序，第二層編碼表示對應工序選擇的加工機器。若待加工的工件總數為n，第i個工件有mi道工序，則個體長度為2∑ni=1mi。對于個體的前∑ni=1mi位，采用基于工件的編碼方法，指定所有的工件編號，工件編號在染色體中出現的次序代表該工件的工序。對于個體的后∑ni=1mi位，每位代表前半段染色體相應位置工序的加工機器編號。解碼時，根據個體給出的優先順序，將染色體轉化為有序調度并產生調度方案。

2.2.2 初始種群與適應度值

在各組生成初始種群時，隨機生成第一層編碼，表示全部工序的加工順序。在第一層編碼第i位產生后，判斷該基因表示的工件編號和工序，在適用于該工件的并行機集內選擇一個臺機器，形成第二層編碼的第i位。機器被選概率與機器已被選次數有關，被選次數少的機器被選中概率更大，多次實驗表明概率選擇比隨機選擇更利于資源均衡分配。適應度函數以目標函數表示，完工時間越短的染色體越好。

2.2.3 選擇、交叉與變異

1）選擇算子。本算法采用精英保留策略與輪盤賭法相結合的方式進行隨機選擇。計算種群中染色體適應度，將每代種群中適應度函數值最大的染色體直接復制進入下一代，其他采用輪盤賭選擇法產生，保證了最優個體進入下一代，同時也保證了種群多樣性。

2）交叉算子。采用整數交叉的方法獲得新染色體。只對染色體的第一層代碼部分隨機選擇交叉位點進行交叉，對第二層代碼所表示的機器基因，按照交叉前個體的對應關系進行調整。交叉后產生的染色體可能出現工件工序的多余與缺失，采用多刪缺補的原則調整。交叉概率的取值在0.8～1。

3）變異算子。采用位點變異的方式，隨機選擇一個個體編碼串的一個基因座，按照變異概率進行變異。變異概率的取值在0.001～0.02之間。

3 實例分析

本文以某船用管類生產企業的混合流水生產車間生產過程作為實例研究對象。該企業生產車間可抽象描述為帶約束并行多機混合流水車間，所有產品由初始狀態（毛胚）到最終狀態（工件）共經過5道工序過程，工序順序為切割、彎管、點焊、全焊、打磨，車間共有加工設備19臺。該企業主要生產的產品分為直管、彎管兩大類，根據管徑大小分為不同規格，工件的規格與品類如表1所示。

由于工件規格、工藝存在差異性，并行設備因工藝約束而適用于特定類型的工件，直管類產品不需經過彎管工序，為了便于研究，本文設虛擬機器用以直管工件的彎管工序加工，加工時間為0，機器生產參數如表2所示。

本文設置三組實驗以驗證所建模型與求解算法的有效性，選用Matlab為平臺進行。實驗一為選取該企業一次實際生產任務作為研究對象，采用不同算法種群規模分別進行10次實驗。實驗二為應用仿真隨機生成10組不同規模調度算例，分別采用啟發式規則、傳統遺傳算法和本文算法對模型進行求解。實驗三為隨機選取10次企業已完成的生產調度案例，對比采用本文算法優化后與優化前企業實際調度結果。由于文章篇幅有限，實驗二、實驗三僅展示結果對比數據，實驗一中展示訂單信息與算法優化過程及調度甘特圖。

實驗一 選取企業一次實際生產任務作為實驗對象，共40個待加工工件來自8組不同客戶，全部工件到達時間為0，訂單信息如表3所示。

該問題為大規模組合優化問題，利用動態規劃可以得知該問題的最優值為f=0.92，X=11110111。設置實驗種群規模分別為20、50、100，分別進行10次運算，每次實驗都在50代以內得到近優可行解，運算時間較短，運算結果如表4所示。結果表明，種群增大可以提高最優解出現次數。

由于算法優化循環進行，故僅展示第一次內層算法優化過程，如圖1所示。該優化過程為初始狀態下以最小完工時間為目標對第一組的加工排序優化，對應該組工件加工方案甘特圖如圖2所示，縱坐標表示機器編號，橫坐標表示時間，數字表示工件編號及工序，例如，1603表示16號工件的第3道工序。

結果顯示，該算例可經過3次以內的內外層循環得到近優解，最優解為X=11110111，最大加權成套數為0.920。最優加工方案為延遲5號訂單的全部工件，其余工件的完工時間全部滿足交貨期要求，如圖3所示。

實驗二 為驗證模型與算法的有效性，設置10種規模不同的調度案例，其中工件類型、訂單權重、訂單內工件數量隨機生成，根據EDD規則仿真結果與實驗經驗設置工件交貨期。 采用臨界比最小（Smallest Critical Ratio， SCR）法則、遺傳算法（Genetic Algorithm， GA）、啟發式遺傳算法進行比較，兩種算法的參數與編碼方式一致。表5為算例仿真結果得到的加權成套數。

從表5可以看出，與SCR規則相比，啟發式遺傳算法能夠在以成套訂單問題中求得更好的解。當調度問題規模較小時，傳統遺傳算法與啟發式遺傳算法均能夠得到最優解;隨著問題規模增大，傳統遺傳算法已無法在有效時間內得出可行解。由此可見，在訂單數量與工件數量均較大時，啟發式遺傳算法體現出顯著優越性。

實驗三 隨機選擇企業實際生產中10次已完成的生產調度案例，采用本文算法對生產任務進行優化調度，可得到本文算法優化后加權成套訂單數與企業實際加權成套訂單數對比結果，如圖4所示。本文算法優化后調度完工時間不包含拒絕訂單的加工時間，因此，將延遲加工訂單安排在成套系數為1的訂單之后以最小完工時間加工，得到的完工時間與企業實際調度完工時間對比結果，如圖5所示。

由圖4可得，在10次生產任務對比實驗中，采用本文算法調度優化后的加權成套訂單數均明顯高于企業實際調度結果，平均10次實驗優化后目標值為原目標值的1.64倍;由圖5可得，10次實驗中優化后的總加工時間相比于優化前均有減少，平均10次實驗優化后總加工時間比原加工時間減少了5.1%。

上述三組實驗中，實驗一、實驗二的結果表明在求解并行機帶工藝約束混合流水車間調度環境下的成套訂單問題時，啟發式遺傳算法體現收斂速度快、不易陷入局部最優等優越性，實驗三結果表明了算法具有實用性與有效性。

4 結語

本文研究了并行機帶工藝約束混合流水車間環境下的成套訂單問題，基于分批調度策略提出了啟發式遺傳算法，在求解大規模成套訂單問題時能夠改善求解時間過長、易陷入局部最優等現象，在MTO型生產企業中有較高的實際應用價值。以某船用零件制造企業為背景，以生產實例、不同算法仿真、與實際結果對比三組實驗進行驗證，結果表明本文算法與企業原方法相比能夠顯著提高加權成套訂單數，在保證訂單履約力的同時能縮短企業加工時間。本文所研究問題在MTO模式且具有工件交貨期約束的生產企業中具有較高應用價值。另外，在相關研究中，訂單中具有相同交貨期的不同工件視為同一工件，加工時間為各工件加工時間之和，在混合流水車間中并不適用，因此本文研究不考慮訂單中存在相同交貨期工件的情況，考慮訂單中存在交貨期相同的不同類型工件的情況值得繼續深入研究。

參考文獻

[1]呂秀芬.復雜環境下MTO企業交貨期優化研究[D].廣州：廣東工業大學，2011：6-13.（LYU X F. Research on due-date optimization for MTO manufacture based in complex environment [D]. Guangzhou： Guangdong University of Technology， 2011： 6-13.）

[2]周水銀，陳榮秋.單機加權成套訂單數遺傳算法研究[J].系統工程，2005，23（5）：22-24.（ZHOU S Y， CHEN R Q. A genetic algorithm： weighted single machine scheduling problems to maximize the whole-set orders [J]. Systems Engineering， 2005， 23（5）： 22-24.）

[3]蘇亞，傅青.并行機含調整時間成套訂單數問題遺傳算法[J].控制工程，2007，14（1）：78-81.（SU Y， FU Q. Genetic algorithm for whole-set order problem of identical parallel scheduling with setup time [J]. Control Engineering of China， 2007，14（1）：78-81.）

[4]YU Z， YANG X. Full glowworm swarm optimization algorithm for whole-set orders scheduling in single machine [J]. The Scientific World Journal， 2013（1）：652061.

[5]肖世昌，孫樹棟，楊宏安.混合分布估計算法求解隨機Jobshop提前/拖期調度問題[J].控制與決策，2015（10）：1854-1860.（XIAO S C， SUN S D， YANG H A. Hybrid estimation of distribution algorithm for stochastic Job shop scheduling with earliness/tardiness penalty [J]. Control and Decision， 2015（10）：1854-1860.）

[6]桂玲，謝勇，王紅衛.鋼箱梁生產的提前/拖期調度問題研究[J].系統工程理論與實踐，2017，37（5）：1274-1281.（GUI L， XIE Y， WANG H W. Early/tardy scheduling problem for the steel box girders production and construction [J]. Systems Engineering—Theory and Practice， 2017，37（5）：1274-1281.）

[7]HOOGEVEEN J A， LENSTRA J K， VELTMAN B. Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard [J]. European Journal of Operational Research， 1996， 89（1）：172-175.

[8]TAMAKI H， NISHINO E， ABE S. A genetic algorithm approach to multi-objective scheduling problems with earliness and tardiness penalties [C]// Proceedings of the 1999 Congress on Evolutionary Computation. Piscataway， NJ： IEEE， 1999，1： No. 99TH8406.

[9]PORTMANN M C， VIGNIER A， DARDILHAC D， et al. Branch and bound crossed with GA to solve hybrid flowshops [J]. European Journal of Operational Research， 1998， 107（2）： 389-400.

[10]WANG C， LIU C， ZHANG Z H， et al. Minimizing the total completion time for parallel machine scheduling with job splitting and learning [J]. Computers and Industrial Engineering， 2016， 97（C）： 170-182.

[11]WANG W-L， WANG H-Y， ZHAO Y-W， et al. Parallel machine scheduling with splitting jobs by a hybrid differential evolution algorithm [J]. Computers and Operations Research， 2013， 40（5）： 1196-1206.

[12]史青濤.基于遺傳算法的單工序并行機分批調度研究[D].大連：大連理工大學， 2014：25-34.（SHI Q T. Research on lot splitting scheduling for parallel machines with single operation based on genetic algorithm [D]. Dalian： Dalian University of Technology， 2014： 25-34.）

[13]WANG C， LIU C， ZHANG Z-H， et al. Minimizing the total completion time for parallel machine scheduling with job splitting and learning [J]. Computers and Industrial Engineering， 2016， 97（C）： 170-182.

[14]趙海丹.有模具限制的并行機臺調度問題研究[D].長春：吉林大學，2016： 19-32.（ZHAO H D. Study on parallel machines with mold constraint scheduling problem [D]. Changchun： Jilin University， 2016： 19-32.）

[15]高家全，趙端陽，何桂霞，等.解特殊工藝約束拖后調度問題的并行遺傳算法[J].計算機工程與應用，2007，43（27）：184-186.（GAO J Q， ZHAO D Y， HE G X， et al. Parallel genetic algorithm for tardiness scheduling problem with special process constraint [J]. Computer Engineering and Applications， 2007， 43（27）： 184-186.）

JIA Yeling， born in 1995， M. S. candidate. Her research interests include intelligent scheduling， intelligent algorithm.

DONG Shaohua， born in 1960， M. S.， professor. His research interests include logistics system simulation， manufacturing execution system.