軒 華 王 晶 張慧賢 李 冰

(鄭州大學(xué)管理工程學(xué)院 河南 鄭州 450001)

0 引 言

帶機(jī)器可利用約束和阻塞的混合流水車間調(diào)度問(wèn)題(Hybrid Flowshop Scheduling Problem with Machine Available Constraint and Blocking，HFSP-MACB)同時(shí)考慮了機(jī)器故障和機(jī)器阻塞。由于機(jī)器故障或維護(hù)等使機(jī)器在一定時(shí)間內(nèi)無(wú)法用于正常工作。在實(shí)際生產(chǎn)過(guò)程中，機(jī)器故障是常見(jiàn)的不確定因素，會(huì)對(duì)生產(chǎn)計(jì)劃和結(jié)果產(chǎn)生偏差，甚至可能會(huì)引起配送等環(huán)節(jié)的混亂。因此在制定生產(chǎn)計(jì)劃時(shí)考慮機(jī)器故障干擾，減少機(jī)器故障對(duì)調(diào)度性能的影響。此外，在相鄰生產(chǎn)階段的緩沖區(qū)能力有限或不存在，當(dāng)工件完成前道工序的加工后，如不能進(jìn)入緩沖區(qū)等待則需停留在加工它的機(jī)器上直至下游機(jī)器釋放，從而導(dǎo)致了該機(jī)器的阻塞。這類問(wèn)題在工業(yè)生產(chǎn)中有著較廣泛的應(yīng)用。例如，在船舶平面分段制造模式下，平面分段的重量和體積較大等導(dǎo)致難以儲(chǔ)存，考慮到經(jīng)濟(jì)性，工序之間一般不設(shè)置緩沖區(qū)，當(dāng)前道工序的任務(wù)完成后，需要下道工序的工位釋放后才能繼續(xù)進(jìn)行加工，此時(shí)就形成了阻塞。同時(shí)，分段從前道工序運(yùn)送到后道工序的運(yùn)輸時(shí)間不可忽略。因此，這就形成了考慮運(yùn)輸時(shí)間的HFSP-MACB。Hall等[1]已證明當(dāng)機(jī)器數(shù)多于兩臺(tái)時(shí)不考慮運(yùn)輸時(shí)間的阻塞流水車間是強(qiáng)NP-hard，故所研究的帶運(yùn)輸時(shí)間HFSP-MACB也是強(qiáng)NP-hard。

運(yùn)輸時(shí)間有兩類，一類是與工件相關(guān)，即運(yùn)輸時(shí)間取決于工件自身；另一類是工件無(wú)關(guān)的，即運(yùn)輸時(shí)間由相鄰生產(chǎn)階段之間的距離決定。針對(duì)帶運(yùn)輸考慮的兩階段HFSP，為最小化makespan，文獻(xiàn)[2]假定運(yùn)輸時(shí)間取決于工件，每階段有多臺(tái)同構(gòu)并行機(jī)，提出了一種兩階段啟發(fā)式和一種分支定界精確方法；文獻(xiàn)[3]針對(duì)階段1含多臺(tái)批處理機(jī)而階段2有多臺(tái)離散機(jī)的情況，考慮與工件無(wú)關(guān)的運(yùn)輸時(shí)間，提出一種混合多種啟發(fā)式規(guī)則的差分進(jìn)化算法。針對(duì)帶運(yùn)輸考慮的多階段HFSP，文獻(xiàn)[4]還考慮了可能返工時(shí)間、不同準(zhǔn)備時(shí)間和預(yù)期順序相關(guān)調(diào)整時(shí)間，提出了一種增強(qiáng)入侵雜草優(yōu)化算法以最小化makespan；文獻(xiàn)[5]針對(duì)初始階段有串行批處理機(jī)的情況，提出了改進(jìn)遺傳算法以最小化總加權(quán)完工時(shí)間；文獻(xiàn)[6]則針對(duì)可重入HFSP，提出了兩種拉格朗日松弛算法以最小化總加權(quán)完工時(shí)間。

為解決帶阻塞的混合流水車間makespan問(wèn)題，在中間緩沖能力有限的條件下，文獻(xiàn)[7]提出了啟發(fā)式算法，該方法也可用于求解阻塞HFSP；文獻(xiàn)[8]以表面貼片技術(shù)線為背景，提出了一種精確算法和一種啟發(fā)式方法；文獻(xiàn)[9]提出了一種禁忌搜索算法。在無(wú)中間緩沖的條件下，文獻(xiàn)[10]提出了一種啟發(fā)式算法；文獻(xiàn)[11]基于禁忌搜索和優(yōu)先級(jí)規(guī)則提出一種方法；文獻(xiàn)[12]結(jié)合嵌套變鄰域搜索提出了一種memetic算法；文獻(xiàn)[13]提出了混合粒子群優(yōu)化算法；文獻(xiàn)[14]假定并行機(jī)為無(wú)關(guān)機(jī)，提出了一種改進(jìn)離散布谷鳥(niǎo)搜索算法；文獻(xiàn)[15]假定每階段有不同加工速度的并行機(jī)，相鄰階段間由一個(gè)單爪機(jī)器人運(yùn)送零件，每個(gè)零件在每個(gè)階段只能由指定機(jī)器集中的一臺(tái)進(jìn)行加工，提出了基于模擬退火的求解方法；文獻(xiàn)[16]考慮了無(wú)關(guān)并行機(jī)和機(jī)器合格性約束，利用機(jī)器人卸載、運(yùn)送和裝載零件，每個(gè)零件有釋放時(shí)間，其運(yùn)輸時(shí)間取決于工件，基于蟻群優(yōu)化和遺傳算法提出了兩種超啟發(fā)式算法。

上述文獻(xiàn)均默認(rèn)機(jī)器在所有時(shí)間連續(xù)可用，然而，這種假設(shè)在實(shí)際工業(yè)生產(chǎn)上并不成立。目前關(guān)于機(jī)器可用性與生產(chǎn)集成調(diào)度的研究多為單機(jī)[17-18]、并行機(jī)[18]、流水車間[19-20]和混合流水車間環(huán)境[21]。對(duì)于較為復(fù)雜的阻塞HFSP的研究較少，文獻(xiàn)[22]探討了兩階段阻塞HFSP，假設(shè)機(jī)器不能連續(xù)可用，提出了遺傳算法最小化makespan。但是缺乏關(guān)于同時(shí)考慮阻塞和機(jī)器可利用約束的研究。研究的目標(biāo)多為makespan，而總加權(quán)完成時(shí)間問(wèn)題有助于降低在制品庫(kù)存和加強(qiáng)工序間的時(shí)間銜接等。為此，本文以考慮運(yùn)輸?shù)亩嚯A段HFSP-MACB的集成調(diào)度為研究對(duì)象，以最小化總加權(quán)完成時(shí)間為目標(biāo)，建立基于故障時(shí)間窗的集成優(yōu)化模型，提出一種混合啟發(fā)式和局域搜索的自適應(yīng)混合遺傳算法以有效求解該問(wèn)題。

1 問(wèn)題描述與建模

n個(gè)工件通過(guò)s個(gè)工序進(jìn)行加工，至少存在某個(gè)工序p的同構(gòu)并行機(jī)數(shù)Mp≥2，一臺(tái)機(jī)器一次只能加工一個(gè)工件，一個(gè)工件一次只能在一臺(tái)機(jī)器上加工；工件在相鄰兩個(gè)工序之間傳送都需要運(yùn)輸時(shí)間；相鄰兩個(gè)工序之間無(wú)中間緩存區(qū)；由于機(jī)器長(zhǎng)時(shí)間加工導(dǎo)致磨損、老化等，機(jī)器有一定發(fā)生故障的概率，當(dāng)機(jī)器發(fā)生故障時(shí)，對(duì)機(jī)器進(jìn)行維修，維修期間機(jī)器無(wú)法用于工件加工。通常機(jī)器發(fā)生故障的準(zhǔn)確時(shí)間是無(wú)法預(yù)知的，因此采用機(jī)器故障統(tǒng)計(jì)相關(guān)數(shù)據(jù)的概率分布代替，計(jì)算公式如下：

n∈{1,2，…,N},z∈{1,2，…,Z}

(1)

式中：Pn(z)表示機(jī)器n在時(shí)刻z出現(xiàn)故障的概率；Zn表示機(jī)器n的運(yùn)行時(shí)間。

1) 已知參數(shù)。工件集為J(J=1,2,…,n)，j表示工件序號(hào)，n表示工件總數(shù)；工序序號(hào)為p，總加工工序?yàn)閟；工序p的機(jī)器數(shù)為Mp，機(jī)器序號(hào)為m，總機(jī)器數(shù)為TM；工件j從工序p到p+1的運(yùn)輸時(shí)間為Tj(p,p+1)；工件j在工序p的機(jī)器m上加工時(shí)間為Wjpm；Z表示計(jì)劃時(shí)間范圍，z為時(shí)間段序號(hào)，z∈{1,2，…，Z}；hj表示工件j的權(quán)重。

2) 決策變量。若工件j在工序p使用機(jī)器m加工，Xjpm值為1，否則為0；若工件j在時(shí)刻z正在工序p上加工或阻塞，Yjpz值為1，否則為0；時(shí)刻z第p道工序可用的機(jī)器數(shù)為apz；工件j在工序p的開(kāi)始加工時(shí)間為bjp，完成加工時(shí)間為cjp；工件j的完工時(shí)間為Cj。

3) 目標(biāo)函數(shù)。以最小化總加權(quán)完工時(shí)間為目標(biāo)：

(2)

4) 工序優(yōu)先級(jí)約束。工序優(yōu)先級(jí)約束要求工件在每道工序只有在前一工序加工完成并運(yùn)輸至后一工序，才可開(kāi)始該工序的加工：

Tj(p,p+1)+cjp+1≤bj,p+1j∈J,p∈{1,2，…，s-1}

(3)

5) 機(jī)器能力約束。

(4)

p∈{1,2，…,s},z∈{1,2，…,Z}

(5)

式(4)表示工件在各工序只能在一臺(tái)機(jī)器上進(jìn)行處理；式(5)表示機(jī)器能力約束要求z時(shí)刻在工序p上加工被占用工件數(shù)不能超過(guò)工序p可利用的機(jī)器總數(shù)。

6) 工序加工時(shí)間要求。工件j在第p道工序的加工時(shí)間表示為：

cjp=bjp+Wjpm-1j∈J,p∈{1,2，…，s},m∈{1,2，…,TM}

(6)

7) 機(jī)器占用時(shí)間約束。工件j在工序p上占用機(jī)器時(shí)間等于工件在p+1階段的開(kāi)工時(shí)間減去在p階段的開(kāi)工時(shí)間及工序p到p+1之間的運(yùn)輸時(shí)間：

j∈J,p={1,2，…,s-1}

(7)

2 自適應(yīng)混合遺傳算法

由于HFSP-MACB是強(qiáng)NP-hard問(wèn)題，因此提出基于啟發(fā)式規(guī)則的自適應(yīng)混合遺傳算法(Heuristic Rules Based Adaptive Hybrid Genetic Algorithm, HR-AHGA)求解上述模型。遺傳算法是基于生物進(jìn)化原理提出的一種智能搜索算法，有較好的魯棒性，但容易陷入局部最優(yōu)。設(shè)計(jì)多種啟發(fā)式規(guī)則對(duì)初始種群進(jìn)行改進(jìn)，并采用自適應(yīng)交叉和變異一定程度避免算法早熟。利用局域搜索 (Local Search, LS)對(duì)GA解的鄰域空間作進(jìn)一步搜索，改善解的質(zhì)量。

2.1 基于啟發(fā)式規(guī)則初始化種群

采用自然數(shù)編碼方式，每個(gè)染色體為n個(gè)工件的排序，即μ={μ(1),μ(2),…,μ(n)}，其中μ(k)表示染色體上第k個(gè)位置工件的工件號(hào)，工件個(gè)數(shù)即為染色體長(zhǎng)度。

初始化種群，采用啟發(fā)式規(guī)則(Heuristic Rules, HR)和隨機(jī)產(chǎn)生程序相結(jié)合的方式。基于五種啟發(fā)式規(guī)則HRl(l=1,2，…，5)產(chǎn)生解集{Ω1,Ω2,Ω3,Ω4,Ω5}，30%的初始種群從解集{Ω1,Ω2,Ω3,Ω4,Ω5}中均勻重復(fù)選取，剩余的70%個(gè)體采用隨機(jī)生成的方法，從而構(gòu)成最終的初始種群。其中啟發(fā)式規(guī)則設(shè)計(jì)如下：

(1) 權(quán)重越大越優(yōu)先加工規(guī)則HR1。將工件按權(quán)重Wh的降序排序，依次將工件分配到可利用的機(jī)器上，得到可行解Ω1。

(4) 總阻塞時(shí)間越小越優(yōu)先規(guī)則HR4。隨機(jī)產(chǎn)生多個(gè)可行解，計(jì)算相應(yīng)的總阻塞時(shí)間，得到最小阻塞時(shí)間對(duì)應(yīng)的可行解Ω4。

(5) 最大完工時(shí)間越小越優(yōu)先規(guī)則HR5。對(duì)若干個(gè)隨機(jī)生成的可行解分別計(jì)算最大完工時(shí)間，得到最大完工時(shí)間最小的可行解Ω5。

2.2 適應(yīng)度函數(shù)及選擇

2.3 自適應(yīng)交叉與變異算子

交叉算子采用單點(diǎn)交叉的方式，將選擇后的染色體順序打亂，取相鄰的兩個(gè)父代個(gè)體配成一組，隨機(jī)選擇一個(gè)基因位，交換該基因位之前的染色體片段，形成新的子代染色體，若交換后出現(xiàn)基因重復(fù)，則修正重復(fù)點(diǎn)，從而形成兩個(gè)可行的子代。

變異算子有利于提高種群的多樣性，防止算法陷入早熟。采用兩點(diǎn)倒置變異，隨機(jī)選擇染色體上的兩個(gè)基因位并交換這兩個(gè)基因，形成新的子代，如圖1所示。

圖1 兩點(diǎn)倒置變異

傳統(tǒng)GA的交叉和變異概率通常是個(gè)常數(shù)，而遺傳進(jìn)化本身是一個(gè)動(dòng)態(tài)的過(guò)程，這種設(shè)定可能不利于有效求解。因此，設(shè)計(jì)了隨迭代進(jìn)程動(dòng)態(tài)變化的交叉概率pc和變異概率pm，來(lái)增強(qiáng)GA的搜索能力及更新速度。

(8)

(9)

設(shè)置pcmin=0.35，pmmax=0.15。

當(dāng)1≤g≤G/4時(shí)，pmmin=0.006，pcmax=0.65；

當(dāng)G/4≤g≤3G/4時(shí)，pmmin=0.045，pcmmax=0.5；

當(dāng)3G/4≤g≤G時(shí)，pmnin=0.09，pcmax=0.3。

2.4 應(yīng)用LS更新GA解

為進(jìn)一步提高GA當(dāng)前解，引入局域搜索，在GA解的鄰域中繼續(xù)尋優(yōu)。鄰域解由交換GA解染色體的兩個(gè)基因位產(chǎn)生，將染色體上第k(k=1,2,…,n-1)個(gè)位置的基因分別與第k+1,k+2,…,n位置的基因交換，將得到的適應(yīng)度值最大的染色體對(duì)應(yīng)的序列作為最佳鄰域解。

2.5 算法流程

基于上述描述，得到HR-AHGA的流程，如圖2所示。

圖2 HR-AHGA流程

3 算例實(shí)驗(yàn)及實(shí)驗(yàn)分析

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

設(shè)工件數(shù)n=7，工序數(shù)s=3，每道工序上的并行機(jī)數(shù)分別為2、3、2。工件加工時(shí)間Wjpm、權(quán)重hj和相鄰工序之間的運(yùn)輸時(shí)間Tj(p,p+1)如表1所示，運(yùn)行HR-AHGA得到最佳調(diào)度方案為1→2→4→5→7→6→3，調(diào)度解如圖3所示，其中：M表示機(jī)器；J表示工件，b表示相應(yīng)工件在機(jī)器上阻塞。

表1 算例數(shù)據(jù)

圖3 算例甘特圖

因此，最終的總加權(quán)完工時(shí)間為：

3.2 算法測(cè)試

為了驗(yàn)證算法的有效性，對(duì)HR-AHGA進(jìn)行編譯，并與傳統(tǒng)GA進(jìn)行比對(duì)，兩種算法均在CPU為2.60 GHz，內(nèi)存為4.00 GB的Lenovo G480微機(jī)的MATLAB R2014a上實(shí)現(xiàn)。種群規(guī)模PopSize設(shè)為80，最大迭代次數(shù)G設(shè)為160。通過(guò)對(duì)不同遺傳參數(shù)設(shè)置的仿真測(cè)試，設(shè)置傳統(tǒng)GA的交叉概率設(shè)為0.8，變異概率設(shè)為0.06。實(shí)驗(yàn)場(chǎng)景設(shè)置如表2所示。

表2 參數(shù)設(shè)置

算法性能通過(guò)改進(jìn)率L和計(jì)算時(shí)間CPU衡量，其中目標(biāo)值改進(jìn)率L[9,12]和時(shí)間增加率R定義為：

L=(TWCGA-TWCHR-AHGA)/TWCHR-AHGA×100%

R=(CPUHR-AHGA-CPUGA)/CPUGA×100%

TWC表示由相應(yīng)算法得到的目標(biāo)值，CPU為計(jì)算機(jī)運(yùn)行時(shí)間。

每種組合{n,s,Mp}隨機(jī)產(chǎn)生9個(gè)實(shí)例，共測(cè)試6×2×2×9=216組實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如表3所示，表中數(shù)據(jù)均為同一規(guī)模的9組實(shí)例的均值(除最后一行)。

表3 兩種算法的結(jié)果比對(duì)

續(xù)表3

對(duì)于不同規(guī)模問(wèn)題，GA和HR-AHGA在相同迭代次數(shù)內(nèi)得到的平均目標(biāo)值分別為308.65和252.49，與GA相比，HR-AHGA平均運(yùn)行時(shí)間僅增加了1.96%，由HR-AHGA得到的平均目標(biāo)值改進(jìn)了16.81%。中小規(guī)模(n={30, 60, 90})和大規(guī)模(n={150, 200, 300})問(wèn)題的平均改進(jìn)率分別為7.55%和26.07%，這說(shuō)明了HR-AHGA相對(duì)于GA，在求解大規(guī)模問(wèn)題時(shí)改進(jìn)效果更好。

表4表明了不同工件規(guī)模的平均改進(jìn)率，工件規(guī)模為30時(shí)，平均改進(jìn)率為1.85%，當(dāng)工件規(guī)模達(dá)到300時(shí)，改進(jìn)率達(dá)到30.49%；而平均增加運(yùn)行時(shí)間僅從0.35%增加到2.93%?？梢钥闯?，隨著工件規(guī)模增大，HR-AHGA相對(duì)于GA的改進(jìn)率也逐漸增大。因此，整體來(lái)看，HR-AHGA在合理的計(jì)算時(shí)間內(nèi)能夠得到更好的近優(yōu)解，在求解大規(guī)模問(wèn)題時(shí)更顯著。此外，本文測(cè)試問(wèn)題規(guī)模為n={30,60,90,150,200,300}，s={3,4}，Mp={3,4}，根據(jù)測(cè)試結(jié)果，采用HR-AHGA求解300個(gè)工件4個(gè)階段的各實(shí)例中所需的最長(zhǎng)運(yùn)行時(shí)間為506.25 s ，能夠在較短時(shí)間內(nèi)求出近優(yōu)解。根據(jù)表4，相比GA，引入LS后的HR-AHGA求解所有規(guī)模問(wèn)題的平均時(shí)間增加率為1.96%，故該算法也可以求解其他甚至更大規(guī)模算例。

表4 不同規(guī)模問(wèn)題的平均改進(jìn)率

4 結(jié) 語(yǔ)

本文考慮了機(jī)器故障、無(wú)緩存區(qū)、運(yùn)輸時(shí)間等實(shí)際生產(chǎn)約束條件的混合流水車間調(diào)度問(wèn)題，以最小化總加權(quán)完工時(shí)間為目標(biāo)，建立了MIP模型，提出一種自適應(yīng)混合遺傳算法求解帶運(yùn)輸時(shí)間的HFSP-MACB。設(shè)計(jì)了五種啟發(fā)式規(guī)則改進(jìn)初始種群，一定程度上彌補(bǔ)了不確定性規(guī)則搜索的不足；引入LS對(duì)GA產(chǎn)生的解的鄰域空間進(jìn)一步地搜索來(lái)尋優(yōu)。對(duì)不同規(guī)模問(wèn)題的仿真測(cè)試證明HR-AHGA的可行性和有效性，相比傳統(tǒng)遺傳算法求解效率更好，在求解大規(guī)模問(wèn)題時(shí)，本文算法更具優(yōu)越性，對(duì)于實(shí)際生產(chǎn)效率的提高有很大意義。

本文考慮中間無(wú)緩存區(qū)的混合流水車間問(wèn)題，可將本文模型推廣至有限緩存區(qū)調(diào)度問(wèn)題。采用LS規(guī)則對(duì)GA解進(jìn)行改進(jìn)的策略，進(jìn)一步研究可以采用其他啟發(fā)式算法對(duì)GA改進(jìn)或者將LS嵌入GA迭代過(guò)程中，或者采用其他超啟發(fā)式算法進(jìn)行求解，如粒子群算法、螢火蟲(chóng)算法等。