張翠林，王 爍，王軍強

(1．西安航空學院經(jīng)濟管理系，陜西西安 710077)

(2．西北工業(yè)大學生產(chǎn)與運作系統(tǒng)性能分析中心，陜西西安 710072)

(3．西北工業(yè)大學現(xiàn)代設計與集成制造技術(shù)教育部重點實驗室，陜西西安710072)

生產(chǎn)調(diào)度是制造單元管理與控制的核心，是制造單元實現(xiàn)有序、平穩(wěn)、高效運轉(zhuǎn)的關(guān)鍵。自1954年Johnson首次進行流水調(diào)度問題n/2/F/Cmax研究以來，許多生產(chǎn)調(diào)度問題作為復雜的組合優(yōu)化問題，早已被證明是NP(Nondeterministic Polynomial)難題。調(diào)度優(yōu)化方法主要包括數(shù)學規(guī)劃方法、啟發(fā)式規(guī)則、智能優(yōu)化算法等。數(shù)學規(guī)劃方法試圖獲取一定條件下調(diào)度問題的精確最優(yōu)解，一直方興未艾，包括分支定界法［1－2］、整數(shù)規(guī)劃法［3］等;啟發(fā)式規(guī)則簡單易操作，是求解大規(guī)模問題的實用方法，在研究與實踐中得到廣泛應用［4－7］;智能優(yōu)化算法是利用算法的優(yōu)化機制和評價機制進行迭代搜索，不斷改善可行解，逐漸獲得問題的趨優(yōu)解或次優(yōu)解，在大規(guī)模問題和優(yōu)化解求解兩者之間找到結(jié)合點，逐漸成為當前研究的熱點［8－10］。

然而，當前調(diào)度理論研究成果并未很好地應用到生產(chǎn)實際中。究其原因，現(xiàn)有的研究是先建數(shù)學模型再進行優(yōu)化求解。一旦模型建立，所有約束條件就被確定，模型只能遵從，不能更改，即模型固化了當時時刻的生產(chǎn)條件。而在實際生產(chǎn)過程中，約束并非完全遵照模型最初的設定，很可能隨著生產(chǎn)進度的進行和現(xiàn)場工況的變化，部分約束在一定條件和一定代價前提下可以獲得一定程度的約束突破。例如，當部分設備加工能力不足時，如果允許工序超越，則調(diào)換相關(guān)工序次序可緩解設備能力不足帶來的加工壓力，或者借用其他工段或單元設備能力，以應對能力不足而可能導致的加工進度延遲問題;或者變串行加工為并行加工，通過改變部分設備的加工批量和運轉(zhuǎn)批量，以變批量加工方式調(diào)整設備上的負荷。顯見，實際生產(chǎn)中，模型可能存在一定修改余地，能力限制存在一定擴張可能。當然，并非所有約束都存在突破可能，而且約束突破肯定是以付出其他代價為前提的。

本文以某加工車間為例，考慮加工批量約束松弛和瓶頸工序順序松弛，研究柔性流水車間調(diào)度(Flexible flow shop scheduling，F(xiàn)FSS)的約束松弛以及對應調(diào)度問題。

1 問題描述

本文研究的某加工車間是典型的流水車間，柔性流水車間調(diào)度問題一般描述如下:有n種待加工工件 Ji(i=1，2，…，n)，每種工件有 ai個，每個零件表示為Jia(a=1，2，…，ai)，m 種可用于加工工件的機器Mj(j=1，2，…，m)，每種機器有bj個相同并行機，每臺機器表示為Mjb(b=1，2，…，bj)，設第k道工序的機器為瓶頸機器。工件Ji的加工過程由m個操作Oi1，Oi2，…，Oim組成，且各工件預先給定的工藝路徑均相同，操作Oij的加工時間為Pij，每種機器Mj上可以同時加工相同種類的零件cj個，且機器一旦開始加工不能停止。經(jīng)典的柔性流水車間問題如圖1所示。

圖1 柔性流水車間問題示意圖

傳統(tǒng)的調(diào)度問題是基于機器唯一性原則和流水順序不變原則進行研究，但實際生產(chǎn)中，此約束存在一定程度的松弛:

a．加工批量約束松弛。一臺機器同一時刻只能加工一個或一批工件。而實際加工車間同一工序的每次加工批量并不相同，或者前后相鄰工序間的加工批量也不盡相同。

b．工藝順序松弛。加工車間為了緩解瓶頸設備的壓力，在允許工序超越的情況下，調(diào)換瓶頸工序和其相鄰的后續(xù)工序的加工順序，即存在加工順序局部可調(diào)的現(xiàn)象。此問題與工藝路線可變的作業(yè)車間調(diào)度問題既有相似性又有很大的不同。工藝路線可變的作業(yè)車間調(diào)度問題指每個零件的加工工藝路線可能有幾條，具體選擇哪一條工藝路線要視機器的空閑情況和調(diào)度問題的目標而定;而該問題加工順序只是局部調(diào)整，并不存在幾條不一樣的加工路線，即存在工序順序松弛現(xiàn)象。

本文所研究的問題是柔性流水車間調(diào)度問題中的一種特殊情況，即考慮加工批量約束松弛和瓶頸工序順序松弛的新型柔性流水車間調(diào)度問題。

2 數(shù)學模型

柔性流水調(diào)度研究假設:(1)不考慮零件加工的優(yōu)先權(quán);(2)操作允許等待，即前一個操作未完成，后面的操作需要等待;(3)在整個加工過程中，零件每道工序的加工時間保持不變;(4)每臺設備前都有一個無限容量的緩沖;(5)在零時刻所有零件都可開始加工;(6)工序一旦開始不允許中斷;(7)不考慮零件在機器間的轉(zhuǎn)移時間、準備時間。所建數(shù)學模型如下:

式中:t為時間間隔，t=1，2，…，T，T表示足夠長的時間以使所有的工件都能完成加工;Biajb表示工件Jia在機器Mjb第j工序加工的開始時間;Ciajb表示工件Jia在機器Mjb加工的完成時間。

式(1)為數(shù)學模型的目標函數(shù)，以最小化調(diào)度系統(tǒng)的Makespan為優(yōu)化目標;式(2)表示在時刻t、處于工序j加工的工件數(shù)必須不超過那個時刻可利用的機器數(shù);式(3)表示操作一旦開始就不允許中斷;式(4)是順序約束;式(5)表示工件Jia在機器Mj的時間為加工時間;式(6)表示工件Jia在機器Mjb所占用的所有時間間隔在其完成時間之前;式(7)表示工件Jia在機器Mjb開始時間應在時間間隔(Ciaib－Pij)后;式(8)表示同一時間每臺機器最多加工的相同種類工件數(shù)量應小于等于機器可以同時加工的工件數(shù);式(9)表示相同機器上，下個零件的開始時間在上個零件結(jié)束時間之后;式(10)、(11)、(12)是決策變量;式(12)表示一臺機器在相同時刻只能加工相同種類的零件，且當j，b，t不變時，只有一個i能使其值為1，其余均為0。

3 基于遺傳算法的求解方法

遺傳算法(Genetic Algorithm，GA)具有優(yōu)良的并行性和全局尋優(yōu)能力，在求解FFSS時，序號編碼方式比非序號編碼更直接、更方便，但序號編碼的染色體不能在任意位置進行交叉，必須使用PMX、OX和CX等特殊的交叉算子，這些交叉算子遺傳操作過程復雜，計算效率不高。李茂軍［11－12］等提出的單親遺傳算法(Partheno Genetic Algorithm，PGA)取消了傳統(tǒng)序號編碼GA的交叉算子，代之以僅在一條染色體上操作的基因重組等遺傳算子，簡化了遺傳操作，提高了計算效率，并且不要求初始群體的多樣性，也不存在“早熟收斂”問題［11］。文獻［12］證明了PGA的基因重組算子隱含了序號編碼TGA的交叉算子的功能，并沒有影響進化，并驗證了PGA在flow shop問題中的應用效果，因此本文采用PGA進行求解。隨機產(chǎn)生初始化染色體種群，計算當代種群中個體適應度，適應度函數(shù)以柔性flow shop調(diào)度問題的最大完工時間max Ciamb為判斷依據(jù)，對適應度函數(shù)值較小的個體以較大概率進行保留，再通過基因易位操作產(chǎn)生新一代染色體種群，如此循環(huán)直到滿足終止條件，輸出最優(yōu)調(diào)度方案。

3．1 編碼

文獻［13］針對混合流水車間調(diào)度問題設計了如下形式的染色體:

染色體由S個小段組成，每小段表示一道加工工序，每個小段包括L個不同的基因，第p段(1≤p≤S)上的每個基因apq表示第q(1≤q≤L)個工件在第p道工序上加工的機器和加工次序。其中apq由整數(shù)和小數(shù)兩部分組成，整數(shù)部分代表工序p加工用的工序序號，小數(shù)部分表示在同一臺機器上加工發(fā)生沖突后的先后順序。如果某臺機器上存在需要加工兩個或兩個以上的工件的沖突，此時小數(shù)部分決定加工它們的先后順序，較小的數(shù)先被加工。

此編碼方式無法對批量約束松弛問題進行求解，因此本文在文獻［14］的基礎上做了如下改進:

a．a(chǎn)pq改由3位數(shù)組成。百位表示工件在該道工序的第(apq/100)臺并行機上加工，十位和個位用確切的數(shù)字表示工件在該機器上的加工次序，如apq=302表示工件q的第p個工序在該工序的第3臺并行機上第2個加工。

b．在同一個工序同一臺機器上加工的工件，其編碼的十位數(shù)和個位數(shù)表示的加工次序必須是從1開始并且連續(xù)地遞增，不能跳躍遞增。例如不允許工序1在第一臺機器上加工的編碼為101、103。

c．允許同一工序同一機器上不同工件具有相同的編碼，即表示幾個不同的工件在該機器上同時加工(同時開始同時結(jié)束)，但是不同工件的個數(shù)要小于等于該機器上允許同時加工的零件數(shù)。

d．由于假設只有相同種類的零件才能同時加工，所以相同的編碼只能出現(xiàn)在同一種類的零件中。

例如，某車間有2類工件，第1類工件有3個，第2類工件有4個。每類工件都有3道工序:第1道工序的并行機機器數(shù)為2，第2道工序的并行機機器數(shù)為3，第3道工序的并行機機器數(shù)為1。用此編碼方式，得到此柔性flow shop調(diào)度問題的一個染色體為:

該染色體第1行表示第1道工序:工件3在并行機1上第1個加工，在并行機2上依次加工的工件號為1，5，2，6，4，7。第 2 行表示第 2 道工序:工件1在并行機1上第1個加工，工件3，6在并行機2 上加工，加工次序為工件 3，6，工件 2，4，5，7 在并行機3上加工，加工次序為工件2，5，4，7。第3行表示第3道工序:工件1，3在并行機1上第1個同時開始加工，工件2在并行機1上第2個開始加工，工件5，6在并行機1上第3個同時開始加工，工件4，7在并行機1上第4個同時開始加工。

3．2 選擇算子

采用基于輪盤賭的比例選擇法確定哪些個體被選擇進行基因移位操作。為防止過早收斂，本文采用非線性排序來確定個體被選擇的概率，首先將種群中各染色體按適應度值從高到低進行排序，使得排在前面的適應度值較高的個體被選擇到的概率ui也較大。

式中:λ為常數(shù)。

3．3 基因移位算子

基因移位操作是按一定的概率把一條染色體中的一個(或一些)子串中的基因依次后移，并把該子串的最后一個基因移到最前面的位置，移位是在同一條染色體中進行?；蛞莆坏淖哟捌溟L度是隨機的。本文采用的基因移位示意圖如圖2所示。

圖2 基因移位示例圖

3．4 解碼

編碼操作和遺傳操作會得到不同的染色體，這些染色體必須利用解碼技術(shù)才能被轉(zhuǎn)化成各個機器上工件的實際加工順序。本文解碼算法的偽代碼如下:

For i=1∶n(工件總數(shù))

Bia1b=0(初始值設為0)

//工件Jia在第一道工序的機器M1b的開始時間

Cia1b=Bia1b+T1，b，ia，n－ 1

//下一個零件的開始時間為上一個零件的結(jié)束時間

B(ia)'1b=Ciajb

End

For x=2∶m //第x道工序:

For i=1∶n(工件總數(shù))

//C(ia)'xb為在機器Mxb上加工工件Jia前一個工件的結(jié)束時間

//Cia(x－1)(ax－1，ia/100)為工件 Jia上一道工序的結(jié)束時間，即兩者都有空閑時才能加工

//ax－1，ia/100表示工件 Jia在第 x 道工序的加工機器。

End

End

Output:makespan=max［Ciam1，Ciam2，…，Ciamn］。

4 算例及結(jié)果分析

算例來自某車間實際算例。該車間有2類工件，第1類工件有3個，第2類工件有4個。工藝順序為:粗車—精車—拉床—加工中心，每道工序并行機的數(shù)量分別為2，3，2，3。其中拉床為瓶頸設備。當瓶頸設備繁忙時，可以調(diào)換零件在拉床和加工中心的加工順序。每個工件在每道工序上加工的時間已知，見表1。

表1 工件、工序、機器與加工時間表

采用仿真軟件進行仿真，軟件平臺為:Windows 7操作系統(tǒng)。取基因移位操作概率為0．8，變異概率為0．05，種群規(guī)模為30，仿真代數(shù)為100。

當不考慮本文所提的約束松弛條件，只是按照傳統(tǒng)的FFSS進行排程，所得結(jié)果如圖3所示，其Makespan為25。當只考慮加工批量約束松弛時，所得結(jié)果如圖4所示，其Makespan為22，比不考慮加工批量約束松弛調(diào)度Makespan縮短12%。

圖3 傳統(tǒng)FFSS的甘特圖

圖4 考慮加工批量約束松弛的甘特圖

當只考慮瓶頸工藝順序松弛時的調(diào)度結(jié)果如圖5所示，其Makespan為22，比不考慮瓶頸工藝順序松弛調(diào)度Makespan縮短12%。調(diào)整加工順序的工件是零件2和零件3。

圖5 考慮瓶頸工藝順序松弛的甘特圖

從圖4、圖5可知，考慮加工批量約束松弛和瓶頸工藝順序松弛時，得到的調(diào)度結(jié)果更優(yōu)，比不考慮約束松弛得到調(diào)度的Makespan縮短了12%。顯而易見，根據(jù)現(xiàn)場工況調(diào)整部分約束，不僅可以緩解設備能力不足帶來的生產(chǎn)壓力，更能為生產(chǎn)變更或生產(chǎn)調(diào)整提供更多的選擇余地。因此在實際的生產(chǎn)過程中，考慮約束松弛具有較強的實際意義。

5 結(jié)束語

本文立足企業(yè)生產(chǎn)實際，突破傳統(tǒng)調(diào)度中假設滿足機器唯一性和流水順序不變等的約束，通過考慮加工批量約束松弛和瓶頸工序順序松弛，得到了Makespan性能更優(yōu)的調(diào)度方案?？紤]約束松弛進行調(diào)度優(yōu)化不僅緩解了設備能力不足帶來的生產(chǎn)壓力，更為生產(chǎn)調(diào)度管理人員實施調(diào)度提供了更多的選擇，也為分析調(diào)度約束、提高調(diào)度性能提供了實用的分析工具。未來考慮多種混合約束松弛進行約束柔性流水調(diào)度研究，并將此研究推廣到作業(yè)車間的調(diào)度研究中。

［1］ BRAH SA，HUNSUCKER JL．Branch and bound algorithm for the flow shop with multiple processors［J］．European Journal of Operational Research，1991，51(1):88 －99．

［2］ MOURSLIO，POCHET Y．A branch and bound algorithm for the hybrid flow shop［J］．International Journal of Production E-conomics，2000，64(13):113 －125．

［3］ SAWIK T．Integer programming approach to production scheduling for make to order manufacturing［J］．Mathematical and Computer Modeling，2005，41(1):99 －118．

［4］ WITTROCK R J．An adaptable scheduling algorithms for flexible flow lines［J］．Operations Research，1988，33(4):445 － 453．

［5］ LIU Z，XIE J，LIJ，et al．A heuristic for two stage no wait hybrid flow shop scheduling wit h a single machine in either stage［J］．Tsinghua Science and Technology，2003，8(1):43－ 48．

［6］ LEE GC，KIM Y D，CHOISW．Bottleneck focused scheduling for a hybrid flow shop［J］．International Journal of Production Research，2004，42(1):165 －181．

［7］ 王柏琳，李鐵克．等待時間受限的置換流水車間調(diào)度啟發(fā)式算法［J］．管理科學學報，2012，15(6):22 －32．

［8］ HALL N G，SRISKANDARAJAH C．A survey of machine scheduling problems with blocking and no － wait in process［J］．Operations Research，1996，44(3):510 －525．

［9］ 唐海波，葉春明，劉長平，等．基于知識進化粒子群算法的模糊交貨期流水車間調(diào)度問題［J］．計算機集成制造系統(tǒng)，2012，18(4):807 －812．

［10］ 顧文斌，唐敦兵，鄭堃，等．基于激素調(diào)節(jié)機制改進型自適應粒子群算法在置換流水車間調(diào)度中的應用研究［J］．機械工程學報，2012，48(14):177 －182．

［11］ 李茂軍，朱陶業(yè)，童調(diào)生．單親遺傳算法與傳統(tǒng)遺傳算法的比較研究［J］．系統(tǒng)工程，2001(1):61－66．

［12］ 李茂軍，童調(diào)生．單親遺傳算法在Flow－Shop問題中的應用［J］．系統(tǒng)工程與電子技術(shù)，2000，22(6):84－86．

［13］ 崔建雙，李鐵克，張文新．混合流水車間調(diào)度模型及其遺傳算法［J］．北京科技大學學報，2005，27(5):624－626．