機(jī)器故障的柔性加工與裝配作業(yè)車間分批聯(lián)合調(diào)度算法

柳冬，宋豫川，楊云帆，雷琦

（重慶大學(xué) 機(jī)械傳動(dòng)國(guó)家重點(diǎn)實(shí)驗(yàn)室，重慶 400044）

作業(yè)車間調(diào)度問題(job-shop scheduling problem,JSP)最早由GAREY 提出，并被證明是一個(gè)NP-Hard 問題[1]。柔性作業(yè)車間調(diào)度問題(flexible job-shop scheduling problem,FJSP)是JSP 的拓展問題，不同于JSP，F(xiàn)JSP 中一道工序可在多臺(tái)機(jī)器上加工，也已經(jīng)被證明為NP-Hard 問題[2]。因其復(fù)雜性、不確定性和多約束性等特點(diǎn)，學(xué)者一般會(huì)選用智能優(yōu)化算法來求解車間調(diào)度問題，例如遺傳算法[3]、灰狼算法[4]、蟻群算法[5]等。

近年來，大量學(xué)者對(duì)FJSP 進(jìn)行了深入的研究，比如石小秋等[6]以最小化完工時(shí)間為優(yōu)化目標(biāo)，提出一種自適應(yīng)變級(jí)遺傳雜草算法求解FJSP。李明等[7]針對(duì)具有順序準(zhǔn)備時(shí)間(sequence dependent setup time,SDST)和關(guān)鍵目標(biāo)的低碳FJSP，給出了一種有效策略加強(qiáng)對(duì)關(guān)鍵目標(biāo)優(yōu)化的同時(shí)兼顧非關(guān)鍵目標(biāo)的持續(xù)改進(jìn)，提出了一種新型帝國(guó)競(jìng)爭(zhēng)算法求解該問題。但是上述文獻(xiàn)沒有考慮到工件的批次和批量，引入批次和批量之后的FJSP 更加貼近實(shí)際，有著重大研究?jī)r(jià)值。徐本柱等[8]提出了基于工序分批調(diào)度的概念，建立了以關(guān)鍵路徑工序?yàn)橹行牡姆峙{(diào)度模型并證明了該模型的有效性。李聰波等[9]以車間總能耗最低和完工時(shí)間最小為優(yōu)化目標(biāo)建立了多工藝路線柔性作業(yè)車間分批優(yōu)化調(diào)度模型，并采用多目標(biāo)模擬退火算法對(duì)模型進(jìn)行優(yōu)化求解。

在實(shí)際生產(chǎn)中，工件的加工是制造過程的最底層，加工完成的工件需要組裝為組件再由組件組裝為成品，而無(wú)論是組件或者成品都有其物料清單(bill of material,BOM)需求。因此，把裝配過程考慮到調(diào)度問題中是有必要的。柔性裝配作業(yè)車間調(diào)度問題(flexible assembly job shop scheduling problem,FAJSP)是在FJSP 的基礎(chǔ)上考慮工件的裝配關(guān)系約束的更為復(fù)雜和常見的問題。在FJSP 中完工時(shí)間是指最后一個(gè)工件的最后一道工序的加工完成時(shí)間，而在FAJSP 中完工時(shí)間是指最后一個(gè)成品的裝配工序的完工時(shí)間。學(xué)者Nourali 等[10-11]最早建立了FAJSP 的混合整數(shù)規(guī)劃數(shù)學(xué)模型，并在靜態(tài)環(huán)境中以makespan 為優(yōu)化目標(biāo)提出一種粒子群算法進(jìn)行求解。但是其并沒有考慮到動(dòng)態(tài)環(huán)境因素，相比于靜態(tài)車間調(diào)度問題，動(dòng)態(tài)車間調(diào)度問題(dynamic job-shop scheduling problem,DJSP)與實(shí)際的生產(chǎn)環(huán)境更為相似。DJSP 在靜態(tài)調(diào)度的基礎(chǔ)上需要考慮各種突發(fā)事件，比如機(jī)器損壞、緊急插單、工件交貨期改變或者物料延遲等，其中機(jī)器損壞是動(dòng)態(tài)事件中常見的事件之一，也是本文主要研究的動(dòng)態(tài)事件。針對(duì)動(dòng)態(tài)調(diào)度，Zhang 等[12]提出了一種名為混合多智能體/蟻群算法(hybrid MAS/ACO,HMA)的結(jié)合了多智能體系統(tǒng)協(xié)商和蟻群優(yōu)化的方法，并利用實(shí)驗(yàn)證明了該方法在求解DFJSP 上的有效性和可行性；劉愛軍等[13]對(duì)遺傳算法進(jìn)行改進(jìn)并結(jié)合滾動(dòng)窗口再調(diào)度技術(shù)，設(shè)計(jì)了基于事件和周期驅(qū)動(dòng)的重調(diào)度策略用于解決DFJSP；Baykaso?lu等[14]利用貪婪隨機(jī)自適應(yīng)搜索算法，給出了一種具有機(jī)器容量約束和建立次數(shù)依賴于序列的FJSP和DFJSP 的求解算法并驗(yàn)證了其適用性。針對(duì)FAJSP 的動(dòng)態(tài)調(diào)度，楊小佳等[15]考慮現(xiàn)實(shí)生產(chǎn)中存在的隨機(jī)擾動(dòng)，采用了完全反應(yīng)式與預(yù)測(cè)?反應(yīng)式兩類動(dòng)態(tài)調(diào)度策略，并提出了相應(yīng)的優(yōu)先度規(guī)則算法和周期性滾動(dòng)遺傳算法用于求解該問題。

目前DFJSP 已有大量研究，但是考慮到工件批量和裝配因素的研究卻十分匱乏。基于上述分析可知，綜合考慮批量加工與裝配聯(lián)合調(diào)度的FAJSP 具有重大的研究?jī)r(jià)值，本文將該問題描述為：柔性加工與裝配作業(yè)車間分批聯(lián)合調(diào)度問題。本文以最小化最大完工時(shí)間為優(yōu)化目標(biāo)，在考慮機(jī)器故障的基礎(chǔ)上，建立了柔性加工與裝配作業(yè)車間動(dòng)態(tài)調(diào)度模型，并利用改進(jìn)遺傳算法進(jìn)行求解。

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

1.1 問題描述

本文研究的是柔性加工與裝配作業(yè)車間分批聯(lián)合調(diào)度問題，包括靜態(tài)、動(dòng)態(tài)調(diào)度問題，其中靜態(tài)調(diào)度問題可以描述為：給定一組待生產(chǎn)的產(chǎn)品，其裝配結(jié)構(gòu)已知，同一車間中有m臺(tái)不同的加工機(jī)器用來加工工件，am臺(tái)不同的裝配設(shè)備用來裝配工件，n種工件在m臺(tái)加工機(jī)器上加工，各工件包含多道工序且工序順序固定不變，每道工序可在多臺(tái)不同的機(jī)器上加工，各道工序在不同機(jī)器上的加工時(shí)間可能不同。完成加工的工件均由裝配設(shè)備裝配，這里本文提出裝配柔性，類推工件加工柔性，即同一組件可選擇不同的裝配設(shè)備進(jìn)行裝配，在不同設(shè)備上的裝配時(shí)間可能不同。調(diào)度的目標(biāo)是為每一道加工工序和裝配工序分配機(jī)器與設(shè)備，使成品的最終完工時(shí)間最小。

動(dòng)態(tài)調(diào)度在靜態(tài)調(diào)度的基礎(chǔ)上考慮到車間緊急事件的影響，系統(tǒng)對(duì)該事件做出應(yīng)急反應(yīng)。針對(duì)動(dòng)態(tài)調(diào)度問題的研究來分類，可將其分為3 類：周期性重調(diào)度、事件驅(qū)動(dòng)重調(diào)度以及周期性和事件驅(qū)動(dòng)混合重調(diào)度[16]。本文考慮機(jī)器故障，為了及時(shí)響應(yīng)動(dòng)態(tài)事件，采用基于事件的重調(diào)度策略。

1.2 數(shù)學(xué)模型

本文將在以下假設(shè)說明的前提下建立上述問題的數(shù)學(xué)模型：

1)本文采用等量一致分批策略[17]；

2)一道裝配工序同一時(shí)刻只能在一臺(tái)裝配設(shè)備上進(jìn)行裝配；

3)在整個(gè)調(diào)度作業(yè)過程中最多只有一臺(tái)機(jī)器發(fā)生故障；

4)機(jī)器故障后可以經(jīng)過維修時(shí)長(zhǎng)Lt后繼續(xù)投入使用；

5)機(jī)器故障時(shí)加工到一半的工件視為廢品，應(yīng)取出一個(gè)新的備用工件重新加工；

6)各種工件、組件最終組裝成同一種成品。

①相關(guān)符號(hào)定義

i：工件號(hào)，i=1,2···,n。

k：加工機(jī)器號(hào)，k=1,2,···,m。

Bi：工件i的總批量。

b：加工批次號(hào)。

Bib：工件i的b批次的批量。

Oi：工件i的工序數(shù)。

j：加工工序號(hào)，j=1,2,···,Oi。

Pibj：工件i的b批次的第j道加工工序。

u：裝配設(shè)備號(hào)，u=1,2,···,am。

z：組件號(hào)，z=1,2,···,d。

c：成品號(hào)，c=1,2,···,f。

RZz、RCc：當(dāng)前預(yù)組裝件z和成品c的數(shù)量。

Azu、Acu：組件z和成品c在裝配設(shè)備u上的裝配工序。

②約束條件

式(1)為目標(biāo)函數(shù)，即最小化成品的最大完工時(shí)間：

式中：Cmax為最大完工時(shí)間；為成品在裝配設(shè)備u上的裝配完工時(shí)間。

式(2)為各工件各批次的加工工序之間的約束關(guān)系：

式(3)表示加工工序Pibj在同一時(shí)刻只能在一臺(tái)加工機(jī)器上加工：

式中Xkibj取值為0 或1，若Pibj在機(jī)器k上加工，Xkibj=1，否則Xkibj=0。

式(4)為劃分批次后的總工序數(shù)，pi為共件i的批次數(shù)。

式(5)表示同一時(shí)刻一臺(tái)加工機(jī)器只能加工一道工序：

式(6)表示同一時(shí)刻一臺(tái)裝配設(shè)備只能進(jìn)行一道組件或成品的裝配工序：

式中：R代表 RZz或者 RCc；若裝配設(shè)備u上的A1(Azu或者Acu)先于A2加工，=1，否則=0；為工序A1的單件裝配時(shí)間。

式(7)、(8)、(9)為加工工序與裝配工序的開始時(shí)間與結(jié)束時(shí)間的計(jì)算式。

2 算法設(shè)計(jì)

遺傳算法原理簡(jiǎn)單，通用性強(qiáng)，不受限制條件的約束，具有隱含并行性和全局解空間搜索能力[18]，但其缺點(diǎn)是容易早熟收斂。本文選用改進(jìn)過后的遺傳算法解決上述NP-hard 問題，輔以鄰域搜索來增強(qiáng)局部搜索能力。針對(duì)本文問題特性設(shè)計(jì)出鄰域結(jié)構(gòu)N1，給出一種混合型解碼方式進(jìn)行求解，并在機(jī)器故障時(shí)提出相應(yīng)調(diào)度策略。

2.1 編碼與初始化

染色體的編碼是遺傳算法的關(guān)鍵，良好的編碼方式會(huì)提高執(zhí)行效率。本文采用MSOS 編碼方式[19]。染色體總長(zhǎng)度為總工序數(shù)E，如圖1 所示，由兩部分組成，第一部分為基于工序的編碼，用來確定各工件各批次各工序的加工順序，從左往右第一個(gè)21 表示工件2 第1 批次的第1 道工序，以此類推；第二部分為基于加工機(jī)器的編碼，用來確定加工各道工序的加工機(jī)器。由于裝配階段的獨(dú)特性，編碼中沒有給出裝配設(shè)備號(hào)。

圖1 編碼Fig.1 Encoding

初始解的質(zhì)量對(duì)算法的求解速度和質(zhì)量極為重要，為提高初始解在機(jī)器選擇部分中的質(zhì)量和初始種群的多樣性，使用GLR 初始化方法[20]。設(shè)置全局選擇、局部選擇和隨機(jī)選擇的比例分別為0.6、0.3 和0.1。

2.2 遺傳算子設(shè)計(jì)

2.2.1 選擇

選擇是為了使質(zhì)量高的個(gè)體能以更高的幾率生存，避免有效基因的損失，從而加快全局收斂性，提高計(jì)算效率。本文使用錦標(biāo)賽選擇并輔以精英保留策略，錦標(biāo)賽選擇的操作方法為每次從種群中選出3 個(gè)個(gè)體進(jìn)行適應(yīng)度的比較，將適應(yīng)度高的個(gè)體插入到交叉池，如此循環(huán)，直到填滿交叉池為止。

2.2.2 交叉

交叉是主要的遺傳操作，利用父代個(gè)體產(chǎn)生適應(yīng)度更高的新個(gè)體，有效增加種群多樣性以保證算法的全局搜索能力。交叉的方式有很多，為避免產(chǎn)生非法解，工序部分采用基于工件優(yōu)先順序的交叉算子[21]，基于加工機(jī)器的編碼則采用兩點(diǎn)交叉[22]。

2.2.3 變異

變異通過隨機(jī)改變?nèi)旧w的某些基因來生成新的個(gè)體，增加種群多樣性，在一定程度上影響著遺傳算法的局部搜索能力。本文采用兩種變異算子，基于工序的編碼采用交換變異算子，即從染色體中隨機(jī)選擇兩個(gè)位置的基因，然后將它們進(jìn)行位置交換；基于加工機(jī)器的編碼則采用單點(diǎn)變異算子，隨機(jī)選擇一個(gè)基因位置，然后生成一個(gè)不大于該位置工序可選加工機(jī)器總數(shù)的隨機(jī)整數(shù)，并將其填入所選的基因位置。

2.2.4 鄰域搜索

遺傳算法作為一種群優(yōu)化算法，存在早熟和局部搜索能力差的問題。變鄰域搜索算法通過不同鄰域結(jié)構(gòu)間的系統(tǒng)化切換，可以防止搜索陷入局部最優(yōu)，增強(qiáng)局部搜索能力[23]。在柔性加工與裝配作業(yè)車間分批聯(lián)合調(diào)度問題中，最大完工時(shí)間為最終成品的組裝完成時(shí)間，而組件和成品的組裝開始時(shí)刻又受到零件最后一道工序完工時(shí)間的影響?；诖颂攸c(diǎn)，本文設(shè)計(jì)了一種針對(duì)該問題的工件末工序前移的鄰域結(jié)構(gòu)N1和一種隨機(jī)的鄰域結(jié)構(gòu)N2。

N1：在染色體中找到工件i的第b批次的最后一道工序，并將其向前移動(dòng)到之間隨機(jī)一個(gè)位置。對(duì)所有工件的所有批次的最后一道工序都執(zhí)行上述操作，便可提前進(jìn)行裝配操作從而縮減最大完工時(shí)間。例如圖2 中，假設(shè)染色體c為某完整染色體片段，工件1 和工件3 的工序數(shù)均為3，將工序11 和23 的最后一道工序向前移動(dòng)至其可移動(dòng)范圍，則c'為移動(dòng)后的一種情況。

圖2 N1 鄰域結(jié)構(gòu)Fig.2 Neighborhood structure of N1

N2：隨機(jī)選擇某個(gè)零件i總數(shù)基因10%的基因，為這些基因重新分配加工機(jī)器。

2.3 基于裝配設(shè)備負(fù)載均衡的混合貪婪解碼

車間調(diào)度領(lǐng)域的解碼方式可以分為三大類：半主動(dòng)解碼、主動(dòng)解碼和全主動(dòng)解碼[24]，比如傳統(tǒng)的貪婪解碼屬于主動(dòng)解碼。由于考慮到批量裝配，而裝配設(shè)備號(hào)未編入編碼，所以單一的貪婪解碼并不適用于此問題?？紤]該問題的特性并希望快速和有效的完成解碼，本文設(shè)計(jì)了一種基于裝配設(shè)備負(fù)載均衡的混合貪婪解碼，流程圖如圖3所示。

圖3 基于裝配設(shè)備負(fù)載均衡的混合貪婪解碼Fig.3 Hybrid greed decoding based on load balancing of assembly equipment

在工件加工的部分采用貪婪解碼，在裝配部分提出一種基于裝配設(shè)備負(fù)載均衡的裝配設(shè)備選擇策略，該策略步驟如下：

1)得到當(dāng)前需要進(jìn)行組裝的工序Azu(或者Acu)信息；

2)列出此工序所有可用裝配設(shè)備u；

3)選擇可選設(shè)備中完成該裝配工序時(shí)刻早的設(shè)備進(jìn)行裝配，即u為使(或者)取得最小值的設(shè)備。

融合上述策略后，基于裝配設(shè)備負(fù)載均衡的混合貪婪解碼具體步驟為：

1)初始化參數(shù)，令基因位置g=1；

2)判斷當(dāng)前基因代表的工序是否為某一工件i的最后一步工序，若是則更新工件i的完工數(shù)，寫入矩陣Gjn(i,1)，Gjn(i,1)為n×1矩陣，記錄各個(gè)工件當(dāng)前已完成加工而未參與組裝的數(shù)目；更新記錄完工時(shí)間，寫入矩陣Gjt(i,b)，Gjt(i,b)為n×pi矩陣，記錄各個(gè)工件各批次加工完成的時(shí)間；否則，令g=g+1并重復(fù)步驟2)；

3)根據(jù)BOM 結(jié)構(gòu)圖判斷更新完成的工件數(shù)量是否能組裝成組件z，若能則為此道裝配工序分配機(jī)器進(jìn)行組裝并更新已完成的組件數(shù)，寫入矩陣Zjn(z,1)，Zjn(z,1)為d×1矩陣，記錄現(xiàn)有各個(gè)組件的數(shù)目，同時(shí)更新Gjn；否則直接轉(zhuǎn)步驟4)。更新Zjn和Gjn具體方法為：假設(shè)某BOM 結(jié)構(gòu)如圖4，圖中括號(hào)里的數(shù)字代表組成單件成品或組件需要的組件或者工件的數(shù)量，則式(10)、(11)為更新表達(dá)式，為方便描述，用M代表括號(hào)中的數(shù)字。

圖4 BOM 結(jié)構(gòu)Fig.4 BOM structure

式中RZ矩陣為對(duì)應(yīng)的預(yù)裝組件數(shù)矩陣，比如在BOM 結(jié)構(gòu)的前提下，式(10)中RZ與Gjn相對(duì)應(yīng)，為。

4)根據(jù)BOM 結(jié)構(gòu)判斷更新完成后的工件數(shù)量和組件數(shù)量是否能組裝成為成品，若能則為此道工序分配設(shè)備進(jìn)行組裝并更新已完成成品數(shù)量，同時(shí)按照式(10)、(12)更新Gjn和Zjn；否則令g=g+1轉(zhuǎn)步驟2)。

式(10)、(11)、(12)中M表示一個(gè)可變參數(shù)，與參與計(jì)算的工件或者組件有關(guān)，比如Gjn(1,1)=Gjn(1,1)?中M與工件i1相關(guān)，則M=2，而Zjn(1,1)=Zjn(1,1)+中M與組件z1相關(guān)，則M=1。

2.4 機(jī)器故障發(fā)生后的調(diào)度策略

2.4.1 裝配設(shè)備發(fā)生故障

與FJSP 中的機(jī)器損壞不完全一樣，在柔性加工與裝配作業(yè)車間中除了工件加工機(jī)器可能會(huì)發(fā)生故障，用于裝配的裝配設(shè)備也存在著發(fā)生故障的可能性。由于本文引入了柔性裝配，若裝配設(shè)備發(fā)生故障，便不必停工等待設(shè)備修理，可以進(jìn)行重調(diào)度，選擇其他的裝配設(shè)備進(jìn)行裝配作業(yè)，盡可能縮短最大完工時(shí)間。

2.4.2 加工機(jī)器發(fā)生故障

加工機(jī)器發(fā)生故障時(shí)會(huì)面臨兩種情況：

情況一：故障時(shí)此機(jī)器處于空閑狀態(tài)；

情況二：故障時(shí)此機(jī)器正在加工某一批零件。

若為情況一，則根據(jù)靜態(tài)調(diào)度的結(jié)果，記錄當(dāng)前還未完成加工的工序，在機(jī)器損壞時(shí)進(jìn)行完全重調(diào)度。

若為情況二，機(jī)器損壞時(shí)正在被此機(jī)器加工的Pibj將會(huì)被分成兩個(gè)批次，一批為已經(jīng)完成了此道工序加工的工件，另外一批為還未來得及完成此道加工工序的工件。此時(shí)，由于工件i的批次和批量都發(fā)生了改變，原來的染色體便不再合法，因此無(wú)法直接進(jìn)行重調(diào)度。需要對(duì)染色體進(jìn)行調(diào)整，加入新的基因，使重調(diào)度能夠順利進(jìn)行，關(guān)于染色體的調(diào)整將結(jié)合算例1 進(jìn)行具體說明，算法總流程圖如圖5 所示。

圖5 改進(jìn)遺傳算法總流程Fig.5 Improved general flow of genetic algorithm

綜上，機(jī)器故障發(fā)生后的調(diào)度策略具體步驟為：

1)判斷在Ts時(shí)刻發(fā)生故障的機(jī)器類型，若是裝配設(shè)備u故障則轉(zhuǎn)至步驟2)；若是加工機(jī)器k則轉(zhuǎn)至步驟3)；

2)判斷設(shè)備u在故障時(shí)刻是否正在組裝工件，若是則記錄此工序完成組裝的組件或者成品個(gè)數(shù)，轉(zhuǎn)至步驟5)；否則直接轉(zhuǎn)至步驟5)；

3)判斷機(jī)器k的當(dāng)前情況，若是情況1 則轉(zhuǎn)至步驟5)；若是情況2，即工序Pibj正在被此機(jī)器加工，則轉(zhuǎn)至步驟4)；

4)將Bib個(gè)工件i劃分成已經(jīng)完成此道工序加工的Bib1件和未完成加工的Bib2件兩個(gè)批次，將新的基因考慮到動(dòng)態(tài)染色體中；

5)記錄現(xiàn)有的已完工工件數(shù)、組件數(shù)、成品數(shù)和所有機(jī)器的可開工時(shí)間；

6)根據(jù)當(dāng)前已完成加工的工序和最優(yōu)靜態(tài)甘特圖得到還未加工的工序，將其考慮到動(dòng)態(tài)染色體中；

7)初始化動(dòng)態(tài)染色體開始重調(diào)度，獲得最優(yōu)方案。

3 算例分析

為了驗(yàn)證本文算法以及動(dòng)態(tài)調(diào)度策略的有效性，以下設(shè)計(jì)了兩個(gè)算例進(jìn)行說明。在MATLAB 2016a 上進(jìn)行算例測(cè)試，運(yùn)行環(huán)境為：Windows 10操作系統(tǒng)，3.00 GHz，8 GB RAM。設(shè)置算法相關(guān)參數(shù)：靜態(tài)初始種群規(guī)模為400，動(dòng)態(tài)初始種群規(guī)模為200，交叉率為0.8，變異率為0.2，迭代次數(shù)為120 次。

3.1 算例1

算例1 選用文獻(xiàn)[25]中提出的問題并適當(dāng)拓展修改。5 種工件的批量分別為20、10、10、30、20，共有10 臺(tái)零件加工機(jī)器，3 臺(tái)裝配設(shè)備。最后組裝成一種成品，BOM 結(jié)構(gòu)如圖4，裝配工序信息如表1。

表1 裝配工序信息Table 1 Assembly process information min

為與文獻(xiàn)[25]進(jìn)行對(duì)比，在不同的分批原則上利用本文算法求解該問題，以最小化最大完工時(shí)間為優(yōu)化目標(biāo)得到的結(jié)果如表2。

表2 算例1 結(jié)果比較Table 2 Comparison of results of example 1 min

從表2 可以看出，除了在等分2 批的情況下本文的最優(yōu)值與文獻(xiàn)[25]相同，在等分3 批和等分4 批的情況下本文的最優(yōu)值均優(yōu)于文獻(xiàn)[25]，驗(yàn)證了本文算法的整體有效性，等分4 批時(shí)本文最優(yōu)解甘特圖如圖6 所示。

圖6 等分4 批時(shí)本文最優(yōu)解甘特圖Fig.6 Optimal solution of Gantt chart with four equal batches

為了說明本文所提算法和解碼在處理機(jī)器故障時(shí)的可行性，對(duì)該算例進(jìn)行了適當(dāng)拓展。不失一般性，在等分4 批的情況下隨機(jī)選擇機(jī)器故障時(shí)間Ts∈[55,75]，隨機(jī)選擇故障機(jī)器k∈[1,10]。假設(shè)損壞情況為4 號(hào)機(jī)器在Ts=68 min 時(shí)發(fā)生故障，故障時(shí)長(zhǎng)Lt=10 min，即4 號(hào)機(jī)器在78 min 時(shí)可以正常運(yùn)轉(zhuǎn)。利用本文算法求解得動(dòng)態(tài)調(diào)度后的最優(yōu)解，給出機(jī)器4 在Ts時(shí)刻故障后的重調(diào)度甘特圖(如圖7)，可見其在Ts時(shí)刻之前(紅色線條左邊)的調(diào)度順序與靜態(tài)甘特圖6 一致。

圖7 加工機(jī)器4 故障后的動(dòng)態(tài)最優(yōu)解(算例1)Fig.7 Dynamic optimal solution after machine four failure (example 1)

結(jié)合圖例簡(jiǎn)單說明解碼機(jī)器故障時(shí)染色體的更改原則：進(jìn)行重調(diào)度之前首先判斷在Ts時(shí)刻機(jī)器k上工件的加工情況。例如：由圖7 可知，在68 min 時(shí)機(jī)器4 正在加工工件4 的第4 批次的第二道工序(圖7 中紫紅色方塊)，此道工序中有3 件工件完成了加工，有6 件未完成加工，因此工件4 在后續(xù)加工中由4 個(gè)批次（批量分別為7、7、7、9）變成5 個(gè)批次（批量分別為7、7、7、3、6）。進(jìn)而重調(diào)度時(shí)需要將基因45 也考慮進(jìn)入染色體編碼當(dāng)中，由于45 并未完成第二道工序加工，因此45 剩4 道工序(綠色方塊)在重調(diào)度后進(jìn)行，44 則剩3 道工序(黃色方塊)在重調(diào)度后進(jìn)行。

3.2 算例2

在FAJSP 的問題模型下引入批量和動(dòng)態(tài)元素后的問題十分復(fù)雜而且本文提出了裝配柔性，故而目前暫未尋得相關(guān)算例也沒有基準(zhǔn)測(cè)試算例集。在此生成一個(gè)參數(shù)隨機(jī)的算例并完成靜態(tài)與動(dòng)態(tài)調(diào)度，用于說明本文所提算法和策略的有效性與可行性。算例2 的BOM 結(jié)構(gòu)依舊采用圖4，分批原則采用等分4 批，其他模型參數(shù)設(shè)置如表3所示。加工工序信息和裝配工序信息分別見表4和表5。

表3 模型參數(shù)設(shè)置Table 3 Model parameter setting

表4 加工工序信息Table 4 Process information min

續(xù)表 4

表5 裝配工序信息Table 5 Assembly process information min

靜態(tài)調(diào)度情況：為驗(yàn)證鄰域結(jié)構(gòu)N1在柔性加工與裝配作業(yè)車間分批聯(lián)合調(diào)度問題中的有效性。分2 種情況各獨(dú)立運(yùn)行程序20 次得到的結(jié)果如表6。

表6 不同鄰域情況下的結(jié)果比較Table 6 Comparison of results under different neighborhood structures min

可見同時(shí)采用N1和N2時(shí)的最優(yōu)值和均值均比單獨(dú)采用N2時(shí)更好，驗(yàn)證了N1鄰域結(jié)構(gòu)在考慮批量裝配問題上的有效性，在一定程度上提高了算法的局部搜索能力和整體性能。利用本文算法多次運(yùn)行后得到的最優(yōu)解甘特圖如圖8 所示。

圖8 靜態(tài)調(diào)度最優(yōu)解對(duì)應(yīng)的甘特圖Fig.8 Gantt chart corresponding to the optimal solution of static scheduling

動(dòng)態(tài)調(diào)度情況：

1)工件加工機(jī)器發(fā)生故障：隨機(jī)選擇機(jī)器故障時(shí)間Ts∈[55,100]，隨機(jī)選擇故障機(jī)器k∈[1,8]，設(shè)置故障時(shí)長(zhǎng)Lt=10 min。隨機(jī)抽取兩種情況并利用本文算法解得對(duì)應(yīng)靜態(tài)調(diào)度最優(yōu)解圖8 的動(dòng)態(tài)調(diào)度甘特圖如圖9、圖10 所示。

圖9 加工機(jī)器4 故障后的動(dòng)態(tài)最優(yōu)解(算例2)Fig.9 Dynamic optimal solution after machine four failure (example 2)

圖10 加工機(jī)器7 故障后的動(dòng)態(tài)最優(yōu)解Fig.10 Dynamic optimal solution after machine seven failure

①情況1：Ts=88,k=4。

②情況2：Ts=93,k=7。

圖9 和圖10 中的綠色方塊均為重調(diào)度后產(chǎn)生的工件的第5 批次，紅色方塊為機(jī)器故障時(shí)刻正在被加工的工序。由于在機(jī)器損壞時(shí)，工件4 的第3 批次還未完成一道工序的加工，因此圖9中Ts時(shí)刻重調(diào)度后將沒有43 工序塊。

2)裝配設(shè)備發(fā)生故障：隨機(jī)選擇機(jī)器故障時(shí)間Ts∈[110,160]，隨機(jī)選擇故障機(jī)器u∈[1,4]，設(shè)置故障時(shí)長(zhǎng)Lt=10 min。隨機(jī)抽取兩種情況并利用本文算法解得對(duì)應(yīng)靜態(tài)調(diào)度最優(yōu)解圖8 的動(dòng)態(tài)調(diào)度甘特圖，如圖11、圖12 所示：

圖11 裝配設(shè)備1 故障后的動(dòng)態(tài)最優(yōu)解Fig.11 Dynamic optimal solution after assembly device one failure

圖12 裝配設(shè)備3 故障后的動(dòng)態(tài)最優(yōu)解Fig.12 Dynamic optimal solution after assembly device three failure

①情況1：Ts=126,u=1。

②情況2：Ts=135,u=3。

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

本文針對(duì)考慮機(jī)器故障的柔性加工與裝配作業(yè)車間分批聯(lián)合調(diào)度問題進(jìn)行了研究，以成品的最終組裝完成時(shí)間為優(yōu)化目標(biāo)，引入裝配柔性，在遺傳算法的基礎(chǔ)上進(jìn)行了改進(jìn)后求解，并得出了以下結(jié)論：

1)設(shè)計(jì)了一種針對(duì)該問題的工件末工序前移的鄰域結(jié)構(gòu)N1，通過算例結(jié)果分析可知N1鄰域結(jié)構(gòu)的采用使本文算法的局部搜索能力得到提高，求解質(zhì)量得到改善。

2)針對(duì)工件加工和組件裝配兩種不同類型的工序不能單一采用貪婪解碼的問題，提出了一種基于裝配設(shè)備負(fù)載均衡的混合貪婪解碼，在裝配解碼部分融入一種基于裝配設(shè)備負(fù)載均衡的裝配設(shè)備選擇策略，成功地解決了本文所研究的調(diào)度問題。

3)針對(duì)工件加工機(jī)器和裝配設(shè)備故障問題，提出了相應(yīng)的調(diào)度策略和染色體更改規(guī)則用于處理機(jī)器故障動(dòng)態(tài)事件。

4)通過對(duì)已有算例和本文自編算例的測(cè)試，驗(yàn)證了本文所提算法在處理柔性加工與裝配作業(yè)車間分批聯(lián)合調(diào)度問題上的可行性和有效性。

針對(duì)柔性加工與裝配作業(yè)車間分批聯(lián)合調(diào)度問題，本文提出了相關(guān)解碼和策略，但在分批原則上采用的是等量一致分批，動(dòng)態(tài)事件只是考慮了一種。多樣的分批原則和其他動(dòng)態(tài)事件的考慮都是進(jìn)一步研究的方向和要點(diǎn)。