基于緊急訂單的并行流水線動態調度研究

朱華炳，涂學明，王 龍

（1.合肥工業大學 機械與汽車工程學院，合肥 230009；2.天納克汽車工業（蘇州）有限公司，蘇州 215000）

0 引言

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

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

針對動態調度問題的復雜性，本文提出了一種基于改進遺傳算法與仿真分析相結合的混合智能方法，考慮訂單的模糊交貨期，以完工時間和交貨懲罰為優化目標，建立動態仿真模型，并進行優化，然后在分析緊急訂單這一擾動因素基礎上，實現并行流水線的動態調度。

1 多目標模糊并行流水線動態調度問題

1.1 多目標模糊并行流水線調度數學模型

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

i：工件代號；

k：位置代號；

j：流水線代號。

Kj：工件集Jj中包含的工件數目。

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，當工件i被排在第k個位置時, Xi,k=1,否則Xi,k=0。

由以上變量可得：

基于以上的描述，多目標模糊并行流水線調度數學模型描述如下：給定一個調度方案σ∈П，則最優調度為：

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

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

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

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

1.2 緊急訂單下多目標模糊并行流水線動態調度

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

i：工件代號。

k：位置代號。

j：流水線代號。

t0：再調度時刻。

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

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

Kj：工件集Jj中包含的工件數目，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處于加工狀態。待加工的工件的開始加工時間B為的完工時間和再調j,k度時刻t0的最大值決定。即Bj,k的計算公式為：

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

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

2 遺傳算法和計算機仿真

2.1 遺傳算法

1) 染色體編碼和解碼

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

圖1 雙染色體編碼

2) 染色體交叉和變異

(1)染色體交叉

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

(2) 染色體變異

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

(3) 構造適應度函數

本文以完工時間和交貨懲罰為優化目標，因此，適應度函數用多目標加權平均的方式表示，其中a,b可以根據實際求解需要來取值。

2.2 計算機仿真方法

計算機仿真技術是以多種學科和理論為基礎，以計算機及其相應的軟件為工具，通過虛擬試驗的方法來分析和解決問題的一門綜合性技術[11]。它被廣泛應用于機械制造、航空、交通和通信等工程領域。eM-plant仿真軟件，可以為建模、仿真模擬和顯示提供了一種完全面向對象的、圖形化的、集成的工作環境。對多目標模糊并行流水線調度問題進行仿真研究一般要經過三個步驟：仿真模型建立、仿真模型參數設定和仿真邏輯控制、仿真模型運行并對結果進行分析。

2.3 改進GA和仿真分析的混合智能方法

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

3 實例分析

3.1 問題描述

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

3.2 仿真模型建立

根據問題描述，在eM-plant仿真軟件中建立多目標并行流水線的仿真動態模型，如圖3所示。

圖2 混合智能方法

圖3 動態仿真模型

表1 工件在不同生產線上的加工時間

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

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

圖4 Gantt圖

圖5 迭代搜索曲線

3.3 問題求解

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

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

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

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

圖6 t0=26min時的動態調度方案Gantt圖

圖7 動態調度最優解Gantt圖

圖8 動態調度迭代搜索曲線

4 結束語

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

[1] 鄭永前.生產系統工程[M].北京:機械工業出版社.2011:5-6.

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

[3] 劉民,吳澄,楊英杰.并行多機調度問題的一種基于組合規則的遺傳算法[J].電子學報,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] 劉志雄.置換流水車間調度粒子群優化與局部搜索方法研究[J].機械設計與制造,2010:167-169.

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

[7] 劉民,吳澄.解決并行多機提前/拖后調度問題的混合遺傳算法方法[J].自動化學報,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] 蔡蘭,郭順生,王彬.基于交貨期的流水線車間調度算法設計與實現[J].機械設計與制造,2005,8:161-163.

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

[11] 侯揚.基于仿真的制造系統對象建模及其應用[D].上海交通大學,2000.