具有復(fù)雜緩沖的分段多流水車間調(diào)度問題

張志英，代乙君，隋毅

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

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

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

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

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

1 問題描述和數(shù)學(xué)模型

1.1 問題描述

區(qū)別于傳統(tǒng)的機(jī)器間有無限緩沖、工件的加工順序相同，且在緩沖中都遵從FIFO規(guī)則的典型流水車間調(diào)度問題，該問題包括車間內(nèi)部的調(diào)度問題和相鄰車間緩沖中的調(diào)度問題。其特殊性有:

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

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

3)緩沖重調(diào)度:在車間之間的緩沖中對工件進(jìn)行再排序。

4)返工:當(dāng)工件在某一臺機(jī)器上的阻塞時(shí)間超過阻塞時(shí)間限制上限時(shí)，工件需在當(dāng)前機(jī)器上重新加工，返工次數(shù)不限。

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

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

圖1 多車間調(diào)度Fig.1 Multi-shop scheduling

1.2 具有復(fù)雜緩沖的分段多流水車間調(diào)度模型

1.2.1 假設(shè)條件

1)工件在機(jī)器上加工時(shí)不可中斷;

2)工件的移動時(shí)間不計(jì);

3)準(zhǔn)備時(shí)間包含在加工時(shí)間中;

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

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

1.2.2 數(shù)學(xué)建模

1)車間內(nèi)調(diào)度。

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

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

緩沖0中的工件進(jìn)入車間的時(shí)間表示為

車間內(nèi)工件在機(jī)器上的完工時(shí)間表示為

工件離開車間和緩沖的時(shí)間表示為

式中:表示工件h到達(dá)緩沖g的時(shí)間。

工件在車間內(nèi)和緩沖中的阻塞時(shí)間表示為

式中:表示阻塞時(shí)間。

2)車間之間調(diào)度。

工件的返工條件表示為

式中:Z為阻塞時(shí)間上限。

工件離開緩沖的時(shí)間表示為

式中:表示離開緩沖g的時(shí)間。

緩沖的面積限制表示為

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

能力之內(nèi)和受能力約束工件的最早開始加工時(shí)間分別表示為

工件離開緩沖的時(shí)間表示為

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

所有工件的完工時(shí)間表示為

3)目標(biāo)函數(shù)。

模型的目標(biāo)函數(shù)表示為

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

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

工件可能出現(xiàn)阻塞表示為

加工順序的約束表示為

緩沖中重調(diào)度、返工次數(shù)為非負(fù)值表示為

2 啟發(fā)式算法

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

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

2.1 基于NEH的迭代插入算法

NEH算法的思路為按工件總加工時(shí)間的降序?qū)ぜ判?，再依次取出工件進(jìn)行迭代插入操作。但當(dāng)機(jī)器之間的緩沖面積很小或不存在緩沖時(shí)，按總加工時(shí)間的降序排列會使工件的阻塞時(shí)間遠(yuǎn)大于按升序排列的情況［11］。由于車間內(nèi)不存在緩沖，用NEH算法產(chǎn)生第一個車間內(nèi)工件的加工順序時(shí)，按照總加工時(shí)間的升序排列。

2.2 染色體編碼方式

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

2.3 啟發(fā)式算法的規(guī)則

首先根據(jù)2.1中的算法產(chǎn)生第一個車間內(nèi)工件的加工順序R1，然后根據(jù)啟發(fā)式算法的步驟產(chǎn)生其他車間內(nèi)工件的加工順序R2至RG?？尚械募庸ろ樞虮仨毞弦韵乱?guī)則:

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

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

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

2.4 初始種群構(gòu)造算法

初始種群構(gòu)造步驟如圖3所示。圖3中，B是緩沖可用面積，r為相關(guān)度系數(shù)，其計(jì)算公式為

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

圖3 初始種群產(chǎn)生步驟Fig.3 The procedure of generating the initial population

2.5 交叉和變異

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

式中:為同一臺機(jī)器上所有工件加工時(shí)間的均值。

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

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

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

2.6 選擇

選擇操作同時(shí)考慮建造周期與阻塞時(shí)間，并按照目標(biāo)函數(shù)值從小到大的順序?qū)θ旧w排序。選擇概率公式為

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

該式表示適應(yīng)度值小的染色體被選擇的概率較大，且遠(yuǎn)大于適應(yīng)度值大的。

2.7 適應(yīng)度函數(shù)

本文的目標(biāo)函數(shù)是最小化建造周期和阻塞時(shí)間，表示為

式中:λ為(0，1)之間的實(shí)數(shù)，表示權(quán)重。

3 實(shí)例驗(yàn)證與數(shù)值分析

3.1 實(shí)例驗(yàn)證

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

由于實(shí)際造船廠的組立車間和涂裝車間沒有傳統(tǒng)意義上的流水車間的機(jī)器含義，因此，為了不失一般性，將組立、涂裝車間內(nèi)的工位和工位上的設(shè)備抽象為機(jī)器。

圖5表示分段在船廠流水車間內(nèi)的加工流程，分段在多個車間內(nèi)的調(diào)度有以下特征:

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

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

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

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

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

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

圖6 組立車間內(nèi)調(diào)度示例Fig.6 An example of scheduling in assembly workshop

圖7 涂裝車間內(nèi)調(diào)度示例Fig.7 An example of scheduling in painting workshop

3.2 數(shù)值分析

假設(shè)工件在4個連續(xù)的流水車間機(jī)器上的加工時(shí)間在［3，15］間隨機(jī)生成，車間內(nèi)機(jī)器數(shù)在［3，10］間隨機(jī)生成，緩沖面積在［1 600，2 500］間隨機(jī)生成。

數(shù)值分析過程對λ取定值0.8。為證明此啟發(fā)式算法有效，分別用以下方法進(jìn)行比較分析。

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

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

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

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

圖10 不同約束條件下運(yùn)行結(jié)果對比Fig.10 The comparison of results under different constrains

表2是3種算法在不同的規(guī)模下多次運(yùn)行結(jié)果的平均值，可以看出該構(gòu)造型啟發(fā)式算法在求解規(guī)模較大的問題時(shí)的性能仍然較優(yōu)，并且隨著規(guī)模的增大，利用率在逐步提高。

表2 不同規(guī)模下隨機(jī)運(yùn)行結(jié)果對比Table 2 Comparison of results under different dimensions

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

由上可知，可通過適當(dāng)增大緩沖面積和增加單個生產(chǎn)周期內(nèi)加工的工件數(shù)來提高機(jī)器的利用率。

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

4 結(jié)論

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

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

［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］張其亮，陳永生.帶有阻塞限制的混合流水車間調(diào)度問題的混合粒子群求解算法［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］劉心報(bào)，郭盈，程浩.一種基于NEH算法的有效求解半flowshop問題的迭代插入算法［J］.儀器儀表學(xué)報(bào)，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］晏鵬宇，楊乃定，車阿大.自動制造單元最小完工時(shí)間調(diào)度問題的混合啟發(fā)式算法［J］.計(jì)算機(jī)集成制造系統(tǒng)，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］張志英，李殿勤.船舶平面分段的非完全混合流水線調(diào)度［J］.計(jì)算機(jī)集成制造系統(tǒng)，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.