具有復雜緩沖的分段多流水車間調度問題

張志英，代乙君，隋毅

(1.同濟大學 機械與能源工程學院，上海200092;2.上海江南長興造船有限責任公司，上海201913)

流水車間的調度問題在離散制造業中是最常見的一類生產調度模式，這類問題受到了較多的關注，并被證明為NP-hard問題［1］。由于現實生產中存在很多制約條件，使得經典的流水車間調度模型生成的調度變得不可行，需要實用性較好的調度方案。船舶企業在制定生產計劃時按照分段的加工順序依次排產，缺乏對各個車間以及堆場中調度的整體考慮，導致實際生產中“前拖后趕”的情況，造成生產低效率和工期延誤。

近年來，許多學者從理論和算法上對典型流水車間調度問題進行了較為深入的研究，HEJAZI R等對以制造期為優化目標的典型流水車間調度問題進行了較為詳細的總結［2］。但基于機器間帶無限緩沖的假設在實際中往往是無法滿足的。有學者研究帶有限緩沖或不存在緩沖的流水車間調度問題。張其亮等對帶有阻塞限制的混合流水車間調度問題進行優化求解［3］;劉世強等［4］分別對典型流水車間調度問題、帶阻塞的流水車間調度問題、無等待的流水車間調度問題和帶有限緩沖的流水車間調度問題進行了分析。目前求解流水車間調度問題的優化方法主要有精確計算法、構造法和智能計算法，精確算法主要包括規劃法等，但只適用于中小規模的問題，構造法是從局部最優中尋找全局最優的方法，適合局部搜索，其中NEH(Nawaz Enscore and Ham)被公認為是最好的構造法;智能算法例如遺傳算法，應用廣，但有時計算效率不高［5］。較多學者用智能算法對帶阻塞的混合流水車間調度問題進行了研究［6-8］。

具有復雜緩沖的分段多流水車間調度問題與帶緩沖的單流水車間調度有一定的相似性，但由于船舶分段加工的特殊性、堆場與流水車間內緩沖的區別，使得該問題更加復雜。船舶分段的返工、堆場中分段重調度以及阻塞是船舶建造經常出現的情況，如果不能合理的協調解決，會降低設備的利用率、延長建造周期。目前對多流水車間的整體調度問題研究的文獻較少。考慮緩沖的流水車間調度的研究中，工件在緩沖中大部分是遵從先進先出(first in first out，FIFO)規則［9-11］，但船舶分段在車間之間的堆場中并不受FIFO規則約束，所以多流水車間調度需在緩沖中對工件進行再排序來優化調度。

本文根據船廠的實際生產運作情況，提出了考慮分段生產的多流水車間調度模型，設置3種不同的緩沖類型，考慮緩沖中工件重調度和返工，建立調度模型，并利用某船廠的數據進行實例驗證。

1 問題描述和數學模型

1.1 問題描述

區別于傳統的機器間有無限緩沖、工件的加工順序相同，且在緩沖中都遵從FIFO規則的典型流水車間調度問題，該問題包括車間內部的調度問題和相鄰車間緩沖中的調度問題。其特殊性有:

1)復雜緩沖:存在3種緩沖類型，分別為無限能力緩沖、無緩沖和有限能力緩沖。

2)緩沖能力不確定:對有限能力緩沖，由于工件的面積各異，而緩沖的面積確定，所以緩沖中能存放的工件數量不確定。

3)緩沖重調度:在車間之間的緩沖中對工件進行再排序。

4)返工:當工件在某一臺機器上的阻塞時間超過阻塞時間限制上限時，工件需在當前機器上重新加工，返工次數不限。

該問題可以描述為:H個工件依次經過G個流水車間加工，不同車間內機器數量不同，工件進入車間后從機器1到Mg依次進行加工，機器是串聯的，并且機器間不存在緩沖。工件需依次經過所有車間的所有的機器加工后才可離開。

整個加工過程分為2個部分，車間內完工后的工件進入緩沖中，在緩沖中完成重調度的工件依次進入下游車間。車間內工件的加工順序作為下游緩沖重調度的輸入，重調度的結果作為下一車間工件加工順序的輸入，工件的返工又會反過來影響緩沖重調度。多車間調度如圖1所示。

圖1 多車間調度Fig.1 Multi-shop scheduling

1.2 具有復雜緩沖的分段多流水車間調度模型

1.2.1 假設條件

1)工件在機器上加工時不可中斷;

2)工件的移動時間不計;

3)準備時間包含在加工時間中;

4)工件依次經過機器的順序相同;

5)每臺機器每次至多可以加工一個工件，每個工件每次至多被一臺機器加工。

1.2.2 數學建模

1)車間內調度。

加工的第一個工件的完工時間和離開時間表示為

式中:G表示車間(g=1，2，…，G)，Mg表示機器(m=1，2，…，M)，πg(h)為車間g內按照 πg排序后的第h個工件為完工時間表示離開時間表示加工時間。

緩沖0中的工件進入車間的時間表示為

車間內工件在機器上的完工時間表示為

工件離開車間和緩沖的時間表示為

式中:表示工件h到達緩沖g的時間。

工件在車間內和緩沖中的阻塞時間表示為

式中:表示阻塞時間。

2)車間之間調度。

工件的返工條件表示為

式中:Z為阻塞時間上限。

工件離開緩沖的時間表示為

式中:表示離開緩沖g的時間。

緩沖的面積限制表示為

式中:bg為緩沖g的面積大小，rπg(h)表示工件的面積。

能力之內和受能力約束工件的最早開始加工時間分別表示為

工件離開緩沖的時間表示為

式中:βhg為0～1變量，1表示工件h發生了重調度，否則為0;Xfh為0～1變量，1表示工件f為工件h的前一個工件，否則為0;Xf＇h為 0 ～1 變量，1 表示工件f＇為工件h在緩沖中重調度后的前一個工件，否則為0。

所有工件的完工時間表示為

3)目標函數。

模型的目標函數表示為

同一個工件同一時刻最多只能在一臺機器上加工，一臺機器每次至多加工一個工件，此約束表示為

式中:ψπg(h)mz為0～1變量，1表示車間g內的工件在機器m上，否則為0。

工件可能出現阻塞表示為

加工順序的約束表示為

緩沖中重調度、返工次數為非負值表示為

2 啟發式算法

用于求解流水車間調度問題的算法主要有構造型和通用型啟發式算法，其中NEH算法被公認為目前構造型啟發式算法中的最優算法［12］。遺傳算法(genetic algorithm，GA)可根據實際問題靈活的變換編碼方式來縮小搜索空間，但對交叉變異算子有較大的依賴性［13］。為了在合理的時間內找到所描述問題的較優解，利用NEH算法在初始序列排序方法和其后的工件插入步驟方面的優勢［12］，生成車間1內工件的加工順序，根據工件的相似度選擇進入下游車間的工件，利用GA靈活的編碼方法，采用基于工件加工順序的染色體編碼方式，根據問題設計交叉變異算子。結合NEH和GA的優點，構建構造型啟發式算法，求解步驟見圖2。

圖2 啟發式算法步驟Fig.2 The procedure of the heuristic algorithm

2.1 基于NEH的迭代插入算法

NEH算法的思路為按工件總加工時間的降序對工件排序，再依次取出工件進行迭代插入操作。但當機器之間的緩沖面積很小或不存在緩沖時，按總加工時間的降序排列會使工件的阻塞時間遠大于按升序排列的情況［11］。由于車間內不存在緩沖，用NEH算法產生第一個車間內工件的加工順序時，按照總加工時間的升序排列。

2.2 染色體編碼方式

采用基于工件加工順序的染色體編碼方式，將工件在各車間內的加工順序、車間序號、工件的編號直接作為染色體的組成。這種編碼方式將工件數作為染色體的空間維度，縮小問題的搜索空間，工件的加工順序信息包含其中，減少染色體的存儲空間。設X=((［1］，［1］，π［1，1］)…(［H］，［G］，π［H，G］))為種群中的一條染色體，基因(［h］，［g］，π［h，g］)表示進入車間g的第h個工件為π［h，g］。

2.3 啟發式算法的規則

首先根據2.1中的算法產生第一個車間內工件的加工順序R1，然后根據啟發式算法的步驟產生其他車間內工件的加工順序R2至RG。可行的加工順序必須符合以下規則:

規則1:0＜g≤G，0 ＜h≤H，(［h］，［g］，π［h，g］)須在(［h-1］，［g］，π［h-1，g］)離開當前的機器后開始加工。

規則 2:任意一條染色體的基因(［h］，［g］，π［h，g］)須包含h∈(0，H)，g∈(0，G)的所有組合，并且h和g按照從小到大的順序依次取值。

規則1保證只有當下游的機器空閑時，當前的工件才可能移到下一臺機器;規則2保證所有的工件從最后一個車間出來時已經完成了所有的操作。

2.4 初始種群構造算法

初始種群構造步驟如圖3所示。圖3中，B是緩沖可用面積，r為相關度系數，其計算公式為

式(21)表示車間g+1內機器1上正在加工的工件與目前緩沖g中工件加工時間的差值，值越小表示兩工件的相關度越高。

圖3 初始種群產生步驟Fig.3 The procedure of generating the initial population

2.5 交叉和變異

由于GA對交叉變異算子有較大的依賴性，本文根據模型設置交叉變異概率計算公式。對交叉操作，在種群中隨機選擇2條染色體作為父代，然后從左到右依次掃描每項基因，提取工件的排序信息。［g］相同時，按照［h］從小到大的順序依次將提取的π［h，g］組成序列Rg，即為車間g內工件的加工順序。接著將提取的父代染色體的加工序列信息進行兩點交叉。只有［g］相同的基因可兩點交叉，提高求解速度。交叉概率如下

式中:為同一臺機器上所有工件加工時間的均值。

變異操作，類似于交叉操作，從父代染色體中提取各車間內工件的加工順序信息，然后對［g］相同的基因按文獻［14］提出的平移插入變異算子的方法進行平移操作，具體見圖4，變異概率為

圖4 鄰域移動操作圖Fig.4 The neighborhood moving operation diagram

式(22)表示阻塞時間長的工件在總加工時間長的車間內發生交叉的概率較大;式(23)表示阻塞時間長的工件在總加工時間長的車間內發生變異的概率大，但其遠遠小于交叉概率。

2.6 選擇

選擇操作同時考慮建造周期與阻塞時間，并按照目標函數值從小到大的順序對染色體排序。選擇概率公式為

式中:f為適應度值，p為染色體被選中的概率，avg為平均，cur為當前染色體，ext是適應度值比均值小且最鄰近均值的染色體，Popsize為種群中染色體數量。

該式表示適應度值小的染色體被選擇的概率較大，且遠大于適應度值大的。

2.7 適應度函數

本文的目標函數是最小化建造周期和阻塞時間，表示為

式中:λ為(0，1)之間的實數，表示權重。

3 實例驗證與數值分析

3.1 實例驗證

為驗證模型和算法的可行性和正確性，以上海某船廠船舶分段在組立、涂裝2個流水作業車間內的計劃調度為例，利用Visual C#在Windows7平臺上進行編程，在處理器為2.10 GHz，內存為2.00 GB的計算機上實現求解算法。

由于實際造船廠的組立車間和涂裝車間沒有傳統意義上的流水車間的機器含義，因此，為了不失一般性，將組立、涂裝車間內的工位和工位上的設備抽象為機器。

圖5表示分段在船廠流水車間內的加工流程，分段在多個車間內的調度有以下特征:

1)堆場的能力不定;堆場0足以存放單位周期內的所有分段，可認為此處的堆場能力是無限制的;堆場1面積有限;分段離開堆場2的時間還受下游車間內機器加工情況的限制，設為能力無限型。

2)車間內部為帶阻塞的流水車間調度;船體分段重并且占用的作業空間較大，工位之間沒有緩沖，加工過程中會出現阻塞［15］。

圖5 分段加工流程圖Fig.5 Block processing flow chart

堆場1面積為2 300 m2，分段及機器的信息見表1。

圖6是用遺傳算法隨機運行一次得到的車間1內分段的加工順序，圖7則是假設不經過重調度，在涂裝車間內仍按原順序加工時的情況，由于分段5在機器2上的阻塞時間大于4 h，需在機器2上返工。返工造成時間和成本的很大浪費，可通過重調度減少返工發生的次數。該模型與算法同樣適用于3個及其以上的流水車間調度，具體見下節。

表1 分段加工信息Table 1 Block process information

圖6 組立車間內調度示例Fig.6 An example of scheduling in assembly workshop

圖7 涂裝車間內調度示例Fig.7 An example of scheduling in painting workshop

3.2 數值分析

假設工件在4個連續的流水車間機器上的加工時間在［3，15］間隨機生成，車間內機器數在［3，10］間隨機生成，緩沖面積在［1 600，2 500］間隨機生成。

數值分析過程對λ取定值0.8。為證明此啟發式算法有效，分別用以下方法進行比較分析。

圖8、9給出了3種算法計算的建造周期和阻塞時間，建造周期1和阻塞時間1對應構造型啟發式算法，建造周期2和阻塞時間2對應GA，建造周期3和阻塞時間3對應粒子群算法。用構造型算法求解時，收斂速度較慢，但其初始解和收斂解的質量優于其他2種算法，說明構造型算法在較小程度上減慢收斂速度的同時可以較大程度上提高解的質量。

圖8 建造周期的對比Fig.8 The comparison of makespan

圖9 阻塞時間的對比Fig.9 The comparison of blocking time

圖10給出了3種算法計算的目標函數值，目標1對應構造型啟發式算法，目標2對應不存在重調度時的算法，目標3對應隨機產生第一個車間內工件的加工順序的啟發式算法。沒有重調度時，初始解較優，但最終收斂解的質量低于構造型;用隨機產生第一個車間內工件的加工順序的方法求解時，初始解較差，但收斂較快。說明使用基于NEH的迭代插入算法產生第一個車間內工件的加工順序會提高初始解的質量，重調度會提高收斂解的質量，同時本文的選擇、交叉和變異公式，較好的克服了遺傳算法早熟的缺點，可較快搜索到高質量的解。

圖10 不同約束條件下運行結果對比Fig.10 The comparison of results under different constrains

表2是3種算法在不同的規模下多次運行結果的平均值，可以看出該構造型啟發式算法在求解規模較大的問題時的性能仍然較優，并且隨著規模的增大，利用率在逐步提高。

表2 不同規模下隨機運行結果對比Table 2 Comparison of results under different dimensions

圖11給出了模型中只有單一類型的緩沖時求得的阻塞時間，阻塞1對應問題中只有無限型緩沖時的結果，阻塞2對應問題中只有能力有限型緩沖時的結果，阻塞3對應問題中只有能力較小型緩沖時的結果。通過比較分析可知，分段的阻塞時間隨著堆場面積的減小而較大程度地增加。

由上可知，可通過適當增大緩沖面積和增加單個生產周期內加工的工件數來提高機器的利用率。

圖11 緩沖面積不同時阻塞時間Fig.11 The blocking time under different buffer areas

4 結論

通過提煉具有船廠生產特征的模型，對多個生產車間以及車間之間緩沖中的調度進行整體考慮，構造啟發式算法，較大程度地縮短分段的建造周期和阻塞時間，從而減少實際生產中工期延誤問題的發生。在提高調度計劃適用性的同時，給求解帶緩沖的多車間調度問題提供了思路。

由于研究沒有考慮機器的可用性約束及分段在堆場中的移動路徑等問題，因此，將更多實際約束考慮到多車間調度中需要進一步研究。

［1］WANG L，ZHANG L，ZHENG D Z.An effective hybrid genetic algorithm for flow shop scheduling with limited buffers［J］.Computers and Operations Research，2005，33:2960-2971.

［2］HEJAZI R，SAGHAFIAN S.Flowshop scheduling problems with makespan criterion:a review［J］.International Journal of Production Research，2005，43:2895-2929.

［3］張其亮，陳永生.帶有阻塞限制的混合流水車間調度問題的混合粒子群求解算法［J］.信息與控制，2013，42(2):252-257.ZHANG Qiliang， CHEN Yongsheng. Heuristic particle swam optimization algorithm for the hybrid flowshop scheduling with blocking constrain［J］.Information and Control，2013，42(2):252-257.

［4］LIU Shiqiang，ERHAN K.Scheduling a flow shop with combined buffer conditions［J］.Int J Production Economics，2009，117:371-380.

［5］TAILLARD E.Some efficient heuristic methods for the flow shop sequencing problem ［J］.European Journal of Operational Research，1990，47(1):65-74.

［6］WANG X，TANG L.A tabu search heuristic for the hybrid flowshop scheduling with finite intermediate buffers［J］.Computers and Operations Research，2009，36:907-918.

［7］HAO Luo，GEORGE Q，HUANG Yingfeng.Two-stage hybrid batching flowshop scheduling with blocking and machine availability constraints using genetic algorithm［J］.Robotics and Computer Integrated Manufacturing，2009，25:962-971.

［8］GICQUEL C，HEGE L.A discrete time exact solution approach for a complex hybrid flow-shop scheduling problem with limited-wait constraints［J］.Computers ＆ Operations Research，2012，39:629-636.

［9］QIAN Bin，WANG Ling.An effective hybrid DE-based algorithm for multi-objective flow shop scheduling with limited buffers［J］.Computer ＆ Operations Research，2009，36:209-233.

［10］WANG Ling，ZHANG Liang，DA Zhongzheng.An effective hybrid genetic algorithm for flow shop scheduling with limited buffers［J］.Computers ＆ Operations Research，2006，33:2960-2971.

［11］QUAN Kepan，WANG Ling，GAO Liang.An effective hybrid discrete differential evolution algorithm for the flow shop scheduling with intermediate buffers［J］.Information Sciences，2011，181:668-685.

［12］劉心報，郭盈，程浩.一種基于NEH算法的有效求解半flowshop問題的迭代插入算法［J］.儀器儀表學報，2009，30(6):261-265.LIU Xinbao，GUO Ying，CHENG Hao.An effective iterated insertion heuristic based on NEH for the semi-flowshop problem［J］.Chinese Journal of Scientific Instrument，2009，30(6):261-265.

［13］晏鵬宇，楊乃定，車阿大.自動制造單元最小完工時間調度問題的混合啟發式算法［J］.計算機集成制造系統，2010，16(4):847-854.YAN Pengyu，YANG Naiding，CHE Ada.Hybrid heuristic algorithm for the scheduling problem in robotic cell with makespan criterion［J］.Computer Integrated Manufacturing Systems，2010，16(14):847-854.

［14］MURATAT T，ISHIBUCHI H，TANAKA H.Genetic algorithms for flow shop scheduling problem［J］.Computers ＆Industrial Engineering，1996，30(4):1061-1071.

［15］張志英，李殿勤.船舶平面分段的非完全混合流水線調度［J］.計算機集成制造系統，2012，18(11):2435-2445.ZHANG Zhiying，LI Dianqin.Research on non-completely hybrid flow line scheduling of panel block in ship building［J］.Computer Integrated Manufacturing System，2012，18(11):2435-2445.