一種啟發(fā)式算法和改進(jìn)遺傳混合算法在流水車間重調(diào)度中的應(yīng)用

王 森, 熊福力,李 志

(西安建筑科技大學(xué) 信息與控制工程學(xué)院,西安 710055)

0 引言

流水車間重調(diào)度問題是以流水車間調(diào)度問題(flow shop scheduling problem,FSP)為基礎(chǔ)模型的一種動(dòng)態(tài)調(diào)度問題，多年來，研究者們大多關(guān)注以最大完工時(shí)間為優(yōu)化目標(biāo)，較少關(guān)注工件交貨期對(duì)流水車間調(diào)度問題的影響。在考慮交貨期時(shí)，一般認(rèn)為交貨期是一個(gè)固定的值，而不是一個(gè)模糊變量。遺傳算法作為一種群體智能算法，具有全局搜索的特點(diǎn)，是求解流水車間調(diào)度問題常用的一種算法。然而，傳統(tǒng)遺傳算法存在收斂速度慢、穩(wěn)定性差等缺點(diǎn)[1]。

在實(shí)際生產(chǎn)過程中，干擾事件的突然到來往往導(dǎo)致原調(diào)度不在可行，繼而重新生成新調(diào)度方案，即為重調(diào)度。重調(diào)度即在盡量小損耗原調(diào)度性能水平的同時(shí)追求調(diào)度穩(wěn)定性的優(yōu)越， 如何既經(jīng)濟(jì)又髙效地實(shí)施干擾，重調(diào)度一直以來備受國內(nèi)外調(diào)度學(xué)者與實(shí)踐者的關(guān)注。常見的生產(chǎn)干擾事件有機(jī)器突然故障、一批新工件到達(dá)、工件返工、訂單撤銷、交貨期提前、誤操作等等[2]。

Chan和Hu[3]介紹了一種基于人工智能的制造業(yè)流水調(diào)度方法，并通過對(duì)預(yù)制生產(chǎn)特點(diǎn)的分析，建立了預(yù)制生產(chǎn)流水車間排序模型。Benjaoran[4]等人研究了模具數(shù)量對(duì)預(yù)制生產(chǎn)車間進(jìn)度的影響，提出了定制預(yù)制生產(chǎn)車間進(jìn)度模型。Ko和Wang[5]通過包括緩沖區(qū)大小的限制，即臨時(shí)存儲(chǔ)位置的大小，改進(jìn)了人工智能調(diào)度的可行性，在機(jī)器之間，將待完工的部分完工預(yù)制件(以下簡(jiǎn)稱在制品)存儲(chǔ)到優(yōu)化模型中，并開發(fā)出相應(yīng)的調(diào)度系統(tǒng)。Yang[6]等人提出了多條預(yù)制生產(chǎn)線的流水車間調(diào)度模型，以促進(jìn)多條預(yù)制生產(chǎn)線的優(yōu)化調(diào)度。動(dòng)態(tài)調(diào)度出現(xiàn)較早，Jackson對(duì)靜態(tài)調(diào)度和動(dòng)態(tài)調(diào)度做了區(qū)分。Yang[7]提出了流水車間預(yù)制生產(chǎn)多條生產(chǎn)線優(yōu)化重調(diào)度模型。

本文針對(duì)傳統(tǒng)遺傳算法的不足之處對(duì)其作了相應(yīng)的改進(jìn)，在選擇階段引入了精英保留策略來確保算法的收斂性，在進(jìn)行重調(diào)度時(shí)引入啟發(fā)式算法；最后通過實(shí)驗(yàn)分析了該算法的優(yōu)點(diǎn)，描述了流水車間重調(diào)度模型，并且通過實(shí)驗(yàn)分析了啟發(fā)式算法和改進(jìn)遺傳混合算法求解流水車間重調(diào)度問題。

1 重調(diào)度的數(shù)學(xué)模型

FSP一般描述如下：有m臺(tái)機(jī)器和n個(gè)作業(yè)；每個(gè)作業(yè)由m個(gè)操作組成，每個(gè)操作需要不同的機(jī)器。必須在所有機(jī)器上以相同的順序處理n個(gè)作業(yè)[8]。其目的是找出作業(yè)順序，使最大流動(dòng)時(shí)間最小化，這在技術(shù)上被稱為生產(chǎn)計(jì)劃的最大完成時(shí)間。兩個(gè)重要的約束為：① 一臺(tái)機(jī)器上不能同時(shí)加工多個(gè)工件，且一個(gè)工件不能同時(shí)在多臺(tái)機(jī)器上加工[9]；② 同一機(jī)器上工件的加工次序不限制，每個(gè)工件的加工路線亦無限制。預(yù)制構(gòu)件都要經(jīng)過6個(gè)生產(chǎn)步驟，即6道工序，它們分別為成型(M1)、放置鋼筋和埋件(M2)、澆注(M3)、養(yǎng)護(hù)(M4)、脫模(M5)和精加工(M6)。其中，養(yǎng)護(hù)是一個(gè)并行過程，可以同時(shí)處理多個(gè)作業(yè)。除養(yǎng)護(hù)外，其余步驟是串行過程。澆筑，養(yǎng)護(hù)不可中斷，其余步驟可中斷；

1)優(yōu)化目標(biāo)

合同懲罰和存儲(chǔ)成本是優(yōu)化目標(biāo)中，將隨著工件數(shù)量線性增加。即優(yōu)化目標(biāo)表示為：

minfcs=αi*Max[0,duedate(i)-C(Ji,M6)]+

βi*Max[0,C(Ji,M6)-duedate(i)]

(1)

其中：fcs代表合同懲罰和存儲(chǔ)成本；

Ji是按順序i生產(chǎn)的工件號(hào)，Mk是處理第k步的機(jī)器的序號(hào);

C(Ji,Mk)是預(yù)制件Ji在機(jī)器Mk上的離開時(shí)間;

αi,βk為早期懲罰與延期懲罰的懲罰系數(shù);

duedate(i)是預(yù)制件Ji的交貨期。

2)優(yōu)化約束

(1)機(jī)器生產(chǎn)率約束

在調(diào)度過程中，不僅要考慮正常生產(chǎn)對(duì)機(jī)器生產(chǎn)率的約束，還要考慮生產(chǎn)緊急情況對(duì)機(jī)器生產(chǎn)率的制約。約束取決于生產(chǎn)條件變化的原因。式(2)和式(3)表示生產(chǎn)率的約束；

S(JiMk)≥

(2)

C(Ji,Mk)≥S(Ji,Mk)+Pi,k

(3)

其中：C(Ji,Mk),S(Ji,Mk),Pi,k是預(yù)制件Ji在機(jī)器Mk上的離開時(shí)間、進(jìn)入時(shí)間、處理時(shí)間。

(2)八小時(shí)工作制的約束

式(4)表示澆注工序每天八小時(shí)的工作；式(5)表示養(yǎng)護(hù)工序每天八小時(shí)的工作；式(6)表示其他工序每天八小時(shí)的工作。

C(Ji,M3)≥

(4)

C(Ji,M4)≥

(5)

C(Ji,Mk)≥

(6)

其中：HW，HN,HE是每天允許工作時(shí)間、非工作時(shí)間和加班時(shí)間。T是在不考慮8小時(shí)工作制的情況下計(jì)算C(Ji,Mk)得到的。D=(T/24)是從生產(chǎn)開始到C(Ji,Mk)的總天數(shù)，D取整。

當(dāng)有緊急加工工件時(shí)，對(duì)其進(jìn)行重調(diào)度處理，對(duì)緊急工件的處理方式本文的做法為：給予緊急加工工件更高的加工權(quán)重，使其先加工；在重調(diào)度過程中盡可能早地完工緊急加工工件；而對(duì)于重調(diào)度的開始時(shí)間的設(shè)置，假設(shè)原調(diào)度的開始時(shí)間從零開始，在急件到達(dá)時(shí)刻RT>0，而工件交付日期不變，故而重調(diào)度的開始時(shí)間Txtart即為RT時(shí)刻當(dāng)前工件的6個(gè)工序的離開時(shí)間：

Txtart=C(JRT,Mk)

(7)

其中：JRT取整數(shù)；

重調(diào)度策略的步驟如下所示：

①在已排好的調(diào)度計(jì)劃基礎(chǔ)上，有緊急訂單到來；

②假設(shè)有多個(gè)緊急訂單，確定影響訂單優(yōu)先級(jí)的各個(gè)因素，將所有訂單按優(yōu)先級(jí)進(jìn)行排序；

③根據(jù)緊急訂單策略，將緊急訂單依次插入到待加工工序，找到庫存成本與延期交貨的懲罰之和最小的位置；

④找到所有緊急訂單的插單位置，得出最小懲罰，插單結(jié)束。

2 啟發(fā)式算法和改進(jìn)遺傳混合算法

2.1 改進(jìn)遺傳算法

遺傳算法是一種模擬達(dá)爾文生物進(jìn)化論的模型，是通過模擬自然進(jìn)化來尋找最優(yōu)解的一種群體優(yōu)化算法。改進(jìn)遺傳算法在傳統(tǒng)遺傳算法的基礎(chǔ)上，加入精英保留策略以及動(dòng)態(tài)變異率，最后經(jīng)過調(diào)參，找出結(jié)果最優(yōu)的遺傳算法各個(gè)參數(shù)，從而使得改進(jìn)遺傳算法結(jié)果更優(yōu)。

2.1.1 編碼

本文采用工件號(hào)編碼來表示個(gè)體(染色體)，一組編碼代表一種加工方案，如對(duì)于6個(gè)工件中的工序 [4 1 3 2 6 5]，其中數(shù)字的順序代表工件在各個(gè)機(jī)器上的順序，數(shù)字代表著相應(yīng)的工件號(hào)，如數(shù)字“4”表示在機(jī)器上第一個(gè)加工工件為工件4，數(shù)字“1”表示機(jī)器上第二個(gè)加工工件為工件1，以此類推，數(shù)字“5”表示在機(jī)器上第六個(gè)加工工件為工件5。所有工件在機(jī)器上的加工順序相同，且每臺(tái)機(jī)器在同一時(shí)刻只能加工一個(gè)工件。

2.1.2 初始種群的產(chǎn)生

在本文中，初始種群是隨機(jī)產(chǎn)生的。使用MATLAB軟件中的隨機(jī)排序函數(shù)“randperm”對(duì)染色體進(jìn)行隨機(jī)編碼，給定種群大小，通過多次調(diào)用該函數(shù)得到所需大小的初始種群。

2.1.3 計(jì)算個(gè)體適應(yīng)度值

以目標(biāo)函數(shù)的倒數(shù)作為個(gè)體的適應(yīng)度值，并采用精英保留策略[10]使最優(yōu)個(gè)體存活下來。

2.1.4 選擇

本文采用合同懲罰和存儲(chǔ)成本最小的指標(biāo)來對(duì)調(diào)度個(gè)體的適應(yīng)度值進(jìn)行評(píng)價(jià)，即個(gè)體適應(yīng)度值大的為優(yōu)良個(gè)體。在計(jì)算完每個(gè)調(diào)度個(gè)體的適應(yīng)度值后，采用精英保留策略進(jìn)行個(gè)體選擇。

2.1.5 交叉

本文采用部分映射交叉(Partial-Mapped Crossover，PMX)進(jìn)行交叉，首先，隨機(jī)選擇一對(duì)染色體(父代)中多個(gè)基因的起始和終止位置(在同一位置選擇兩條染色體)；然后，交換兩組基因的位置；最后，進(jìn)行重復(fù)檢測(cè)，并建立基于兩組交換基因的映射關(guān)系，如圖1所示，以1-6-3這一映射關(guān)系為例，可以看到第二步結(jié)果中Child1存在兩個(gè)重復(fù)基因1，則將基因1先變?yōu)榛?，在變?yōu)榛?，Child2存在兩個(gè)重復(fù)基因3，與Child1基因轉(zhuǎn)變順序相反，這時(shí)將其通過映射關(guān)系將Child1中的重復(fù)基因1轉(zhuǎn)變?yōu)榛?，將Child2中的重復(fù)基因3轉(zhuǎn)變成基因6，可以看到第三步Mid1存在兩個(gè)重復(fù)基因6，Mid2也存在兩個(gè)重復(fù)基因6，再通過映射關(guān)系將Mid1中的重復(fù)基因6轉(zhuǎn)變?yōu)榛?，Mid2中的重復(fù)基因轉(zhuǎn)變?yōu)榛?。以此類推至沒有重復(fù)基因?yàn)橹?，即圖2中第四步Final1和Final2所示。最后所有重復(fù)的基因都會(huì)經(jīng)過映射轉(zhuǎn)變?yōu)榱硪粋€(gè)基因，保證形成的新子代基因無重復(fù)基因。

2.1.6 變異

交叉操作后形成的新個(gè)體具有一定的基因突變概率。與選擇操作一樣，這種操作是基于概率的，這就變成了變異概率pm。一般來說，變異概率設(shè)置得很小，一般pm≤0.05。

對(duì)交叉后代集中每個(gè)后代的每一位，產(chǎn)生一個(gè)隨機(jī)數(shù)rand∈[0,1]，若rang

改進(jìn)遺傳算法的流程圖如圖2所示。

2.2 啟發(fā)式算法和改進(jìn)遺傳混合算法

對(duì)于啟發(fā)式算法，本文選取NEH快速啟發(fā)式算法，該算法為快速求解生產(chǎn)調(diào)度問題的算法。由于遺傳算法具有可擴(kuò)展性，容易與其他算法結(jié)合的優(yōu)點(diǎn)。因此當(dāng)干擾事件到來時(shí)，采用啟發(fā)式算法與改進(jìn)遺傳混合算法，改進(jìn)遺傳算法得出的最優(yōu)結(jié)果作為初始解傳入快速啟發(fā)式算法中，作為快速啟發(fā)式算法的初始解，將緊急加工工件依次插入到每個(gè)位置上，得到不同位置的解，找出最小懲罰的調(diào)度工序的位置，可以快速解決干擾事件帶來的影響，而且兩種算法的優(yōu)點(diǎn)都體現(xiàn)出來，不僅運(yùn)行時(shí)間短，而且得到合適解與對(duì)應(yīng)的調(diào)度工序。

2.3 啟發(fā)式算法和改進(jìn)遺傳混合算法流程

1)利用MATLAB軟件中的隨機(jī)排序函數(shù)“randperm”產(chǎn)生染色體的初始種群，每個(gè)染色體代表一個(gè)生產(chǎn)安排；

2)生成與染色體相對(duì)應(yīng)的條件最優(yōu)調(diào)度；

3)基于優(yōu)化目標(biāo)對(duì)它們進(jìn)行評(píng)估并確定是否終止；

4)如果要繼續(xù)，則基于前一個(gè)染色體，通過變異和交叉并返回到第二個(gè)步驟來生成新的染色體群；否則，結(jié)束計(jì)算并輸出由步驟3選擇的最優(yōu)調(diào)度。

當(dāng)?shù)螖?shù)達(dá)到調(diào)度器給定的極限時(shí)，優(yōu)化終止，得到最合適的調(diào)度工序。

5)先提取出調(diào)度工序，在上述步驟完成后，當(dāng)有緊急加工工件即在RT時(shí)刻有新工件到來，將RT時(shí)刻之后的未加工工件的工序提?。?/p>

6)保持原有調(diào)度工序，將緊急工件依次插入所有位置，每次找出最優(yōu)解的位置，逐次進(jìn)行到最后一個(gè)緊急加工工件，最終得出最優(yōu)調(diào)度。

3 實(shí)驗(yàn)結(jié)果及分析

程序運(yùn)行平臺(tái)是Windows10操作系統(tǒng)中的MATLAB軟件，經(jīng)過調(diào)參可得各種參數(shù)如下：種群規(guī)模大小取為NIND=50,迭代次數(shù)取為MAXGEN=200,改進(jìn)遺傳算法采用部分映射交叉方法進(jìn)行交叉操作，采用換位法進(jìn)行變異操作，交叉率和變異率分別取作：Pc=0.85，Pm=0.02。以下面5種規(guī)模來驗(yàn)證改進(jìn)遺傳混合算法的性能。本仿真實(shí)驗(yàn)包含10*6、20*6、30*6、50*6、70*6五種問題規(guī)模，每個(gè)規(guī)模在相同條件下運(yùn)行30次。通過模擬緊急加工工件干擾下的重調(diào)度情景，統(tǒng)計(jì)了合同違約金與倉儲(chǔ)成本(Earliness/Tardiness，E/T)的實(shí)施方案，在相同運(yùn)行時(shí)間下與不同運(yùn)行時(shí)間下的不同方案，在不同大小規(guī)模下的方案。

表1為部分結(jié)果，由表1可得，10*6，20*6，30*6，50*6，70*6的最優(yōu)解分別為1 263.9，2 024.8，1 909.5，9 369.1，22 462，緊急訂單規(guī)模分別取4*6，10*6，14*6，20*6，30*6。結(jié)果分析為在小規(guī)模如10*6與20*6規(guī)模情況下，蟻群算法結(jié)果較好，在30*6，50*6，70*6的其他大規(guī)模情況下，改進(jìn)遺傳算法結(jié)果較好，但所需時(shí)間遠(yuǎn)遠(yuǎn)大于提出的改進(jìn)遺傳混合算法的時(shí)間，以70*6為例，蟻群算法與改進(jìn)遺傳算法單次運(yùn)行耗時(shí)50 s左右，而啟發(fā)式算法和改進(jìn)遺傳混合算法單次運(yùn)行耗時(shí)15 s左右，時(shí)間差距比較大，因此，對(duì)3種算法在相同運(yùn)行時(shí)間下進(jìn)行比較。

表1 不同運(yùn)行時(shí)間下合同違約金與倉儲(chǔ)成本E/T的比較

運(yùn)行結(jié)果如表2所示，10*6，20*6，30*6，50*6，70*6的最優(yōu)解分別為1 363.9，4 155.6，3 875，17 122，28 644，結(jié)果分析為在相同運(yùn)行時(shí)間下，在10*6與20*6規(guī)模情況下，蟻群算法結(jié)果較好，對(duì)于30*6，50*6，70*6等其余規(guī)模情況下，啟發(fā)式算法和改進(jìn)遺傳混合算法結(jié)果最優(yōu)。故而，在同運(yùn)行時(shí)間下對(duì)于大規(guī)模情況來說，本文提出的啟發(fā)式算法和改進(jìn)遺傳混合算法結(jié)果最優(yōu)。

表2 同運(yùn)行時(shí)間下合同違約金與倉儲(chǔ)成本E/T的比較

4 結(jié)束語

本文以合同違約金與倉儲(chǔ)成本最小化為優(yōu)化目標(biāo)的流水車間重調(diào)度問題。采用精英保留策略以及動(dòng)態(tài)變異概率對(duì)遺傳算法進(jìn)行了相應(yīng)的改進(jìn)。使算法具有較強(qiáng)的尋優(yōu)能力。同時(shí)，考慮到隨著個(gè)體數(shù)目變大遺傳算法運(yùn)行時(shí)間過長的缺陷，以及遺傳算法容易與其他算法結(jié)合的優(yōu)點(diǎn)，提出了啟發(fā)式算法與改進(jìn)遺傳算法的混合算法，算法包含了兩種算法的優(yōu)點(diǎn)，在前期具有較強(qiáng)的尋優(yōu)能力，隨著個(gè)體數(shù)目變大運(yùn)行時(shí)間也不會(huì)變慢。