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

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

0 引言

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

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

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

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

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

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

i：工件代號(hào)；

k：位置代號(hào)；

j：流水線代號(hào)。

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

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

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

Bj,k：工件集Ji中，排在第k個(gè)位置上的工件在第j條流水線上的工件，即Jj,k的開(kāi)始加工時(shí)刻。

Cj,k：工件Jj,k的完工時(shí)刻。

Ej,k：工件Jj,k提前時(shí)間值。

Tj,k：工件Jj,k拖期時(shí)間值。

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

由以上變量可得：

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

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

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

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

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

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

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

i：工件代號(hào)。

k：位置代號(hào)。

j：流水線代號(hào)。

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

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

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

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

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

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

Bj,k：Jj,k的開(kāi)始加工時(shí)刻。

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

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

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

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

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

2.1 遺傳算法

1) 染色體編碼和解碼

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

圖1 雙染色體編碼

2) 染色體交叉和變異

(1)染色體交叉

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

(2) 染色體變異

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

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

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

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

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

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

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

3 實(shí)例分析

3.1 問(wèn)題描述

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

3.2 仿真模型建立

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

圖2 混合智能方法

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

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

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

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

圖4 Gantt圖

圖5 迭代搜索曲線

3.3 問(wèn)題求解

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

表3 臨時(shí)插入工件的加工時(shí)間

表4 臨時(shí)緊插入工件交貨期窗口

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

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

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

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

4 結(jié)束語(yǔ)

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

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

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

[3] 劉民,吳澄,楊英杰.并行多機(jī)調(diào)度問(wèn)題的一種基于組合規(guī)則的遺傳算法[J].電子學(xué)報(bào),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è)計(jì)與制造,2010:167-169.

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

[7] 劉民,吳澄.解決并行多機(jī)提前/拖后調(diào)度問(wèn)題的混合遺傳算法方法[J].自動(dòng)化學(xué)報(bào),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è)計(jì)與實(shí)現(xiàn)[J].機(jī)械設(shè)計(jì)與制造,2005,8:161-163.

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

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