基于緊急訂單的并行流水線動態(tài)調(diào)度研究

朱華炳，涂學(xué)明，王 龍

（1.合肥工業(yè)大學(xué) 機(jī)械與汽車工程學(xué)院，合肥 230009；2.天納克汽車工業(yè)（蘇州）有限公司，蘇州 215000）

0 引言

生產(chǎn)調(diào)度問題就是調(diào)動各種可用資源在規(guī)定的時間內(nèi)完成生產(chǎn)任務(wù)，同時給出該加工任務(wù)中各種加工工序的加工次序以及時間參數(shù)[1]。多年來，研究者們對并行流水車間調(diào)度問題（Parallel Flow Shop Scheduling Problem，PFSP）的研究多以最大完工時間為目標(biāo)[2～6]，較少考慮工件交貨期的影響。當(dāng)考慮交貨期時，一般又都假設(shè)交貨期為固定值[7～9]，而沒有把交貨期考慮為模糊變量，事實上，在生產(chǎn)調(diào)度實踐中，由于一些調(diào)度信息的不確定性，工件的完工時間與交貨期存在一些偏離是能夠接受的。

在實際生產(chǎn)過程中，流水車間生產(chǎn)具有動態(tài)性、隨機(jī)性等特點。它常常要面臨隨機(jī)動態(tài)事件的干擾，如原材料延遲到達(dá)、急件插入、交貨期變更、機(jī)器故障、零件報廢等[10]，這使得通常要根據(jù)事件的擾動及時調(diào)整調(diào)度方案。于是學(xué)者們提出了動態(tài)調(diào)度問題，它比靜態(tài)調(diào)度問題更符合實際生產(chǎn)的需要，同時由于隨機(jī)事件的影響，動態(tài)調(diào)度具有更大的計算復(fù)雜性，它是比靜態(tài)調(diào)度更為復(fù)雜的NP-hard難題。

針對動態(tài)調(diào)度問題的復(fù)雜性，本文提出了一種基于改進(jìn)遺傳算法與仿真分析相結(jié)合的混合智能方法，考慮訂單的模糊交貨期，以完工時間和交貨懲罰為優(yōu)化目標(biāo)，建立動態(tài)仿真模型，并進(jìn)行優(yōu)化，然后在分析緊急訂單這一擾動因素基礎(chǔ)上，實現(xiàn)并行流水線的動態(tài)調(diào)度。

1 多目標(biāo)模糊并行流水線動態(tài)調(diào)度問題

1.1 多目標(biāo)模糊并行流水線調(diào)度數(shù)學(xué)模型

假設(shè)αjk,βjk分別為工件i的提前完工和拖期的單位時間懲罰系數(shù)，交貨期窗口為[ej,k,dj,k]；對于任意機(jī)器Mj，指派到該機(jī)器的工件集為Jj，則滿足Jj? J 。

i：工件代號；

k：位置代號；

j：流水線代號。

Kj：工件集Jj中包含的工件數(shù)目。

Jj,k：工件集Jj中的工件序列之一，即Jj,k∈Jj其

Pi,j：工件i在流水線j上的加工時間,i=1,2,··· ,n;j=1,2,···,m。

Bj,k：工件集Ji中，排在第k個位置上的工件在第j條流水線上的工件，即Jj,k的開始加工時刻。

Cj,k：工件Jj,k的完工時刻。

Ej,k：工件Jj,k提前時間值。

Tj,k：工件Jj,k拖期時間值。

Xi,k：0-1變量,i=1,2,···,n, k=1,2,···,n，當(dāng)工件i被排在第k個位置時, Xi,k=1,否則Xi,k=0。

由以上變量可得：

基于以上的描述，多目標(biāo)模糊并行流水線調(diào)度數(shù)學(xué)模型描述如下：給定一個調(diào)度方案σ∈П，則最優(yōu)調(diào)度為：

約束(1)表示每個位置有且只有一個工件；

約束(2)表示每個工件必須被安排在某一流水線上進(jìn)行生產(chǎn)；

約束(3)～(6)定義了工件在各流水線上的加工開始時刻，并且當(dāng)前工件要滿足：當(dāng)前工件的前一個工件在當(dāng)前流水線上生產(chǎn)完畢的條件；

約束(7)定義了每個工件在條流水線上的完工時間。其中加工順序Xi,k和開始加工時刻Bj,k(i=1,2, ···, n；j=1, 2, ···, m；k = 1, 2, ···, n)為決策變量。

1.2 緊急訂單下多目標(biāo)模糊并行流水線動態(tài)調(diào)度

假設(shè)對于任意流水線Mj，指派到該流水線的工件集為Jj，

i：工件代號。

k：位置代號。

j：流水線代號。

t0：再調(diào)度時刻。

Ej：t0時刻前，Jj中包含的工件數(shù)目。

Dj：t0時刻后，Jj中包含的工件數(shù)目。

Kj：工件集Jj中包含的工件數(shù)目，Kj=Ej+Dj。

Jj,k：工件集Ji其中的工件序列之一，即Jj,k∈Jj

Pi,j：工件i在流水線j上的加工時間,i=1,2,···,n;j=1,2,···,m。

Bj,k：Jj,k的開始加工時刻。

Cj,k：Ji,k完工時間，q=1,2,···,k; k=1,2,···,Kj）。

1) t0時刻，流水線Mj處于加工狀態(tài)。待加工的工件的開始加工時間B為的完工時間和再調(diào)j,k度時刻t0的最大值決定。即Bj,k的計算公式為：

2) t0時刻，流水線Mj處于待加工狀態(tài)。對于待加工工件，如果工件的釋放時間不等于再調(diào)度時刻t，則待加工的工件的開始加工時間B為

0j,k的完工時間和工件的釋放時間ri最大值決定。即Bj,k的計算公式為：

2 遺傳算法和計算機(jī)仿真

2.1 遺傳算法

1) 染色體編碼和解碼

編碼是遺傳算法要解決的首要和關(guān)鍵問題，選擇合理的編碼方法對算法的質(zhì)量和效率有很大影響。為此，本文設(shè)計了工序與加工流水線相融合的兩層編碼方法，如圖1所示。第一層為工件順序編碼，第二層為工件對應(yīng)的加工流水線編碼。

圖1 雙染色體編碼

2) 染色體交叉和變異

(1)染色體交叉

部分匹配交叉（partially mapping crossover，PMX）。首先隨機(jī)選取兩個交叉點，交換父代個體交叉點之間的片段，對于交叉點外的基因，若它不與交換過來的基因沖突則保留，若沖突則通過部分映射來確定，直到?jīng)]有沖突的基因為止，從而獲得后代個體。

(2) 染色體變異

染色體變異采用互換變異的方式，在染色上隨機(jī)選擇兩個基因，然后互換其位置。

(3) 構(gòu)造適應(yīng)度函數(shù)

本文以完工時間和交貨懲罰為優(yōu)化目標(biāo)，因此，適應(yīng)度函數(shù)用多目標(biāo)加權(quán)平均的方式表示，其中a,b可以根據(jù)實際求解需要來取值。

2.2 計算機(jī)仿真方法

計算機(jī)仿真技術(shù)是以多種學(xué)科和理論為基礎(chǔ)，以計算機(jī)及其相應(yīng)的軟件為工具，通過虛擬試驗的方法來分析和解決問題的一門綜合性技術(shù)[11]。它被廣泛應(yīng)用于機(jī)械制造、航空、交通和通信等工程領(lǐng)域。eM-plant仿真軟件，可以為建模、仿真模擬和顯示提供了一種完全面向?qū)ο蟮摹D形化的、集成的工作環(huán)境。對多目標(biāo)模糊并行流水線調(diào)度問題進(jìn)行仿真研究一般要經(jīng)過三個步驟：仿真模型建立、仿真模型參數(shù)設(shè)定和仿真邏輯控制、仿真模型運(yùn)行并對結(jié)果進(jìn)行分析。

2.3 改進(jìn)GA和仿真分析的混合智能方法

遺傳算法在優(yōu)化搜索效率方面具有的獨特優(yōu)勢，而仿真軟件在問題建模方面具有的簡易、快速的特點。本文將改進(jìn)遺傳算法整合到eM-plant仿真軟件中，設(shè)計了改進(jìn)遺傳算法與仿真分析相結(jié)合的混合智能方法，具體流程如圖2所示。

3 實例分析

3.1 問題描述

合肥某機(jī)械廠沖壓車間主要負(fù)責(zé)上料和沖壓兩道工序，車間共有六條沖壓生產(chǎn)線。工件在各生產(chǎn)線上的加工時間及懲罰因子和交貨期窗口分別如表1和表2所示。其中α，β分別為提前完工和拖期的單位時間懲罰系數(shù)，Ei_time交貨期窗口下限，Li_time為交貨期窗口上限。

3.2 仿真模型建立

根據(jù)問題描述，在eM-plant仿真軟件中建立多目標(biāo)并行流水線的仿真動態(tài)模型，如圖3所示。

圖2 混合智能方法

圖3 動態(tài)仿真模型

表1 工件在不同生產(chǎn)線上的加工時間

表2 懲罰因子和交貨期窗口

將有關(guān)數(shù)據(jù)輸入仿真模型，并運(yùn)行模型對多目標(biāo)模糊并行流水線調(diào)度問題進(jìn)行優(yōu)化求解。各參數(shù)設(shè)定為：種群規(guī)模為30，迭代次數(shù)100，交叉概率0.8，變異概率0.1。求解獲得滿意調(diào)度方案，甘特圖和最優(yōu)解的迭代搜索過程分別如圖4和圖5所示。

圖4 Gantt圖

圖5 迭代搜索曲線

3.3 問題求解

當(dāng)有緊急訂單時，生產(chǎn)調(diào)度人員必須根據(jù)原有的調(diào)度方案調(diào)整調(diào)度計劃，以滿足實際生產(chǎn)的需求，臨時訂單在各生產(chǎn)線上加工時間如表3所示，交貨期窗口如表4所示。

表3 臨時插入工件的加工時間

表4 臨時緊插入工件交貨期窗口

通過將改進(jìn)遺傳算法整合到eM-plant仿真軟件中，結(jié)合兩者各自的優(yōu)點，建立并行流水線混合模型，求解獲得最佳的調(diào)度方案，t0時刻和動態(tài)調(diào)度后的甘特圖分別如圖6和圖7所示。最優(yōu)解的搜索迭代過程如圖8所示。

圖6 t0=26min時的動態(tài)調(diào)度方案Gantt圖

圖7 動態(tài)調(diào)度最優(yōu)解Gantt圖

圖8 動態(tài)調(diào)度迭代搜索曲線

4 結(jié)束語

本文針對多目標(biāo)模糊并行流水線動態(tài)調(diào)度問題，以最小化最大完工時間、最小化交貨懲罰為優(yōu)化目標(biāo)，建立了數(shù)學(xué)模型，提出了一種基于改進(jìn)遺傳算法和仿真分析的混合方法，并建立了動態(tài)仿真模型。通過實例分析，結(jié)果驗證了該方法的有效性和可行性，為解決多目標(biāo)模糊并行流水線動態(tài)調(diào)度問題提供了一種新思路，具有一定的理論研究意義和實踐價值。

[1] 鄭永前.生產(chǎn)系統(tǒng)工程[M].北京:機(jī)械工業(yè)出版社.2011:5-6.

[2] 趙建峰,朱曉春,汪木蘭,等.基于自適應(yīng)遺傳算法混合Flow-shop的調(diào)度與仿真[J].組合機(jī)床與自動化加工技術(shù),2010(3):99-102.

[3] 劉民,吳澄,楊英杰.并行多機(jī)調(diào)度問題的一種基于組合規(guī)則的遺傳算法[J].電子學(xué)報,2000,28(5):1-3.

[4] Cheng R,Gen M.Parallel Machine Scheduling Problems Using Memetic Algorithms[J].Computers Industrial Engineering,1997,vol,33,PP.761-764.

[5] 劉志雄.置換流水車間調(diào)度粒子群優(yōu)化與局部搜索方法研究[J].機(jī)械設(shè)計與制造,2010:167-169.

[6] 李崢峰,喻道遠(yuǎn),楊曙年.基于工序約束并行機(jī)模型的沖壓線調(diào)度[J]. 計算機(jī)集成制造系統(tǒng),2009,15(12):2432-2438.

[7] 劉民,吳澄.解決并行多機(jī)提前/拖后調(diào)度問題的混合遺傳算法方法[J].自動化學(xué)報,2000,26(2):258-262.

[8] Kramer F J, Lee C Y. Due windows scheduling for parallel machine[J].Math Compute Modeling,1994,20(2):22-36.

[9] 蔡蘭,郭順生,王彬.基于交貨期的流水線車間調(diào)度算法設(shè)計與實現(xiàn)[J].機(jī)械設(shè)計與制造,2005,8:161-163.

[10] 錢曉龍,唐立新,劉文新.動態(tài)調(diào)度的研究方法綜述[J].控制與決策,2001,16(2):141-145.

[11] 侯揚(yáng).基于仿真的制造系統(tǒng)對象建模及其應(yīng)用[D].上海交通大學(xué),2000.