任丹妮，熊禾根，陽光燦

(武漢科技大學(xué)a.冶金裝備及其控制教育部重點(diǎn)實(shí)驗(yàn)室;b.機(jī)械傳動(dòng)與制造工程湖北省重點(diǎn)實(shí)驗(yàn)室,武漢 430000)

0 引言

流水車間調(diào)度問題(flow-shop scheduling problems,FSP)是當(dāng)前很多以流水線方式生產(chǎn)的制造車間調(diào)度的抽象模型，作為一個(gè)離散的非數(shù)值化優(yōu)化問題，也被證明是一個(gè)典型的NP-hard問題，具有很高的理論研究價(jià)值和實(shí)踐價(jià)值[1]。

在實(shí)際生產(chǎn)過程中，流水車間調(diào)度模型的建立中存在各種不確定因素和資源約束條件，如機(jī)器具有不可用時(shí)間限制的約束。LEE[2]研究了當(dāng)工件是部分可恢復(fù)時(shí)，機(jī)器具有不可用時(shí)間間隔的雙機(jī)FSP；SAFARI等[3]將實(shí)際生產(chǎn)過程中機(jī)器需要進(jìn)行預(yù)防性維護(hù)以及可能發(fā)生故障的約束條件加入FSP，提出了此類問題的流水車間調(diào)度模型；AGGOUNE等[4]假設(shè)機(jī)器存在周期性的不可用時(shí)間段，設(shè)計(jì)了結(jié)合啟發(fā)式規(guī)則的禁忌搜索算法，有效地提高了加工效率。

為了實(shí)現(xiàn)FSP的最優(yōu)調(diào)度求解，國內(nèi)外很多學(xué)者也做了大量的研究。遺傳算法由于較好的搜索能力被廣泛應(yīng)用，NEPPALLI等[5]提出解決雙機(jī)雙目標(biāo)FSP的遺傳算法；KARIMI等[6]提出解決混合FSP的多階段遺傳算法；DUGARDIN等[7]提出的求解可重入FSP的多目標(biāo)改進(jìn)遺傳算法。當(dāng)傳統(tǒng)單一算法難以得到最優(yōu)解時(shí)，通?？梢赃x擇混合算法使保持多樣性與搜索最優(yōu)解的能力相平衡，王芳等[8]提出了結(jié)合瓶頸啟發(fā)式的引力搜索算法用于解決柔性FSP；TSENG等[9]利用遺傳算法進(jìn)行全局搜索，再結(jié)合兩種局部搜索解決了FSP最小化流程時(shí)間目標(biāo)；軒華等[10]提出結(jié)合迭代貪婪算法的混合遺傳融合優(yōu)化策略對解決實(shí)際柔性流水車間的多處理器調(diào)度問題能夠獲得較好的近似解；吳永明等[11]提出了解決無等待FSP的改進(jìn)蛙跳算法，其中結(jié)合高斯變異和擾動(dòng)因子，提高了局部搜索及全局搜索能力。

即使已有研究考慮到機(jī)器的不可用狀態(tài)，但是很少有研究考慮到車間存在作息時(shí)間導(dǎo)致的機(jī)器不可用問題，導(dǎo)致調(diào)度方案不能很好地指導(dǎo)實(shí)際應(yīng)用。因此，本文針對考慮作息時(shí)間的流水車間調(diào)度問題(flow-shop scheduling problem with consideration of timetable of work,FSP-CTW)進(jìn)行研究，提出相關(guān)調(diào)度模型與改進(jìn)算法，在一定程度上保證了調(diào)度方案與實(shí)際生產(chǎn)調(diào)度相吻合，提高生了產(chǎn)效率，具有明確的現(xiàn)實(shí)意義，符合企業(yè)的實(shí)際生產(chǎn)需求。

1 考慮作息時(shí)間的流水車間調(diào)度模型

1.1 問題描述

流水車間調(diào)度問題可以描述為：n個(gè)工件以相同的順序經(jīng)過m臺(tái)機(jī)器，每臺(tái)機(jī)器上工件加工順序相同。給定工件在各機(jī)器上的加工時(shí)間，安排工件的加工優(yōu)先級(jí)，在滿足工件加工的工藝順序約束與機(jī)器加工工件的先后順序約束條件下，實(shí)現(xiàn)調(diào)度目標(biāo)。

考慮作息時(shí)間的流水車間調(diào)度問題不僅要滿足FSP的約束條件，還要滿足工件加工的開始時(shí)刻、完成時(shí)刻在工作時(shí)段內(nèi)，即機(jī)器的可用時(shí)段內(nèi)，達(dá)到調(diào)度目標(biāo)。與FSP相比，F(xiàn)SP-CTW雖然在解的空間上沒有變化，但新添了約束條件，也增加了問題求解的難度。對FSP-CTW做出如下假設(shè)：

(1)給定不同工作時(shí)段數(shù)的工作時(shí)間與休息時(shí)間；

(2)工作制、工作時(shí)間段數(shù)、工作日的開始工作時(shí)刻設(shè)定后，在調(diào)度過程中保持不變；

(3)同一時(shí)刻，一臺(tái)機(jī)器只能加工一個(gè)工件，且一個(gè)工件只能被一臺(tái)機(jī)器加工；

(4)加工無搶占性，即不允許任意工件的加工插入另一工件的加工過程中；

(5)不同工件的加工優(yōu)先級(jí)相同；

(6)給定工序加工是否可恢復(fù)；

(7)不考慮機(jī)器故障、機(jī)器維護(hù)、機(jī)器維修等動(dòng)態(tài)因素；

(8)不考慮機(jī)器調(diào)整時(shí)間、工件運(yùn)輸時(shí)間，將其計(jì)入對應(yīng)的加工時(shí)間內(nèi)；

(9)工件在機(jī)器上的加工順序確定后，不再改變。

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

為建立該問題的數(shù)學(xué)模型，首先根據(jù)問題描述定義相關(guān)符號(hào)與決策變量如表1所示。

表1 相關(guān)符號(hào)及含義

續(xù)表

其中，aij=1表示工序Oij的加工可恢復(fù)，即工序Oij的加工可跨越工作時(shí)段，在工作時(shí)段的結(jié)束時(shí)刻，工序Oij剩余的加工可在下一工作時(shí)段繼續(xù)進(jìn)行；aij=0表示工序Oij的加工不可恢復(fù)，即工序Oij的加工不可跨越工作時(shí)段，工序Oij的加工開始時(shí)刻、完成時(shí)刻均要在同一工作時(shí)段內(nèi)；zijkt=1表示工序Oij的加工過程包含工作時(shí)段Mkt，即工序Oij的加工開始時(shí)刻或完成時(shí)刻在工作時(shí)段Mkt內(nèi)；zijkt=0表示工序Oij的加工過程不包含工作時(shí)段Mkt，即工序Oij的加工開始時(shí)刻或完成時(shí)刻不在工作時(shí)段Mkt內(nèi)。

定義決策變量以確定工件在機(jī)器上的加工順序：

(1)

目標(biāo)函數(shù)為最小化最大完工時(shí)間：

MinimizeCmax=Cim,Xin=1

(2)

約束條件如下：

(3)

(4)

Sij≥ri,?i∈J,j∈U

(5)

Sij≥Ci(j-1),?i∈J,j∈Ji∧j>1

(6)

Sgh≥Cij,?i,g∈J,j=h∈U,p,q∈J,i≠g,pXgp>qXiq

(7)

Wkt≤Sij

(8)

Wkt

(9)

(10)

(11)

(12)

式中，J表示工件集合；U表示機(jī)器集合和工序集合；Q表示工作時(shí)段集合。式(3)表示一個(gè)工件能且只能占一個(gè)加工位置；式(4)表示一個(gè)加工位置能且只能被一個(gè)工件占用；式(5)表示工件的加工開始時(shí)刻不得早于工件的釋放時(shí)刻；式(6)約束了同一工件的加工開始時(shí)刻與完成時(shí)刻；式(7)約束了同一機(jī)器上不同工件的加工開始時(shí)刻與完成時(shí)刻；式(8)表示存在某個(gè)工作時(shí)段，滿足對任意工件的加工開始時(shí)刻大于等于其工作時(shí)段的開始時(shí)刻，小于其工作時(shí)段的結(jié)束時(shí)刻；式(9)表示存在某個(gè)工作時(shí)段，滿足對任意工件的加工完成時(shí)刻大于其工作時(shí)段的開始時(shí)刻，小于等于其工作時(shí)段的結(jié)束時(shí)刻；式(10)表示若工件加工可恢復(fù)，則工件的加工過程可以包含多個(gè)工作時(shí)段，即工件的加工開始時(shí)刻、完成時(shí)刻可以在不同的工作時(shí)段內(nèi)；式(11)表示若工件加工不可恢復(fù)，則工件的加工過程能且只能在一個(gè)工作時(shí)段內(nèi)完成，即工件的加工開始時(shí)刻、完成時(shí)刻必須在同一工作時(shí)段內(nèi)；式(12)表示工序的加工完成時(shí)刻與加工開始時(shí)刻、加工時(shí)間、工序加工過程所包含的工作時(shí)段的關(guān)系。

1.3 作息時(shí)間設(shè)計(jì)方法

為方便對FSP-CTW進(jìn)行研究，作息時(shí)間的設(shè)計(jì)通過設(shè)置每臺(tái)機(jī)器上的工作制、工作時(shí)段數(shù)、工作時(shí)間與休息時(shí)間來實(shí)現(xiàn)。比如，一個(gè)機(jī)器數(shù)量為3的FSP-CTW的作息時(shí)間設(shè)計(jì)如圖1所示。

圖1 作息時(shí)間設(shè)計(jì)示例

以機(jī)器1作詳細(xì)說明。依次從左往右看，5表示機(jī)器1為5天工作制；0 1 2 3 4表示周一至周五工作；8表示每個(gè)工作日的調(diào)度起始時(shí)刻為8:00；2表示每個(gè)工作日有兩個(gè)工作時(shí)間段；4表示第一個(gè)工作時(shí)段的工作時(shí)間為4 h；1表示第一個(gè)工作時(shí)段的休息時(shí)間為1 h；5表示第二個(gè)工作時(shí)段的工作時(shí)間為5 h；-1表示一個(gè)工作日的結(jié)束并自動(dòng)確定休息時(shí)長，其余行以此類推。作息時(shí)間設(shè)計(jì)將人與機(jī)器分離，不從排班角度考慮設(shè)置機(jī)器的可用時(shí)段，而從機(jī)器本身的可用時(shí)段進(jìn)行考慮，具有簡單高效、包含的信息較為全面的優(yōu)點(diǎn)。

2 求解FSP-CTW的改進(jìn)遺傳算法

遺傳算法是一種高效的全局搜索方法，它能在搜索過程中不受搜索空間的局限，從種群開始利用適應(yīng)度函數(shù)和概率轉(zhuǎn)移策略指導(dǎo)其自動(dòng)獲取相關(guān)搜索空間的內(nèi)容，并且能自適應(yīng)地控制搜索過程以便求得最優(yōu)解，在車間調(diào)度問題中得到很好的應(yīng)用[12]。

但是傳統(tǒng)遺傳算法在解決確定型流水車間調(diào)度問題時(shí)，其計(jì)算結(jié)果往往趨于不穩(wěn)定，容易陷入過早收斂和局部化最優(yōu)?；趯ψ飨r(shí)間的考慮，本節(jié)對傳統(tǒng)遺傳算法做了相應(yīng)的改進(jìn)。對流水車間調(diào)度模型采用了基于工件的編碼，創(chuàng)建染色體和初始化種群，進(jìn)行選擇、交叉、變異等一系列操作后，利用了禁忌搜索改進(jìn)遺傳算法的局部搜索能力，提高解的質(zhì)量。

2.1 編碼與解碼

有效的編碼在不產(chǎn)生非法解的情況下能表達(dá)出個(gè)體與可行解的關(guān)系。對流水車間調(diào)度模型染色體主要采用基于工件的十進(jìn)制編碼方式。以6個(gè)工件為例，316245表示為每一臺(tái)機(jī)器上均以工件3開始加工并依次加工余下工件，也代表了問題的一個(gè)解。

不同的解碼方式產(chǎn)生的最大完工時(shí)間及機(jī)器的利用效率也會(huì)不同。在FSP-CTW中，由于休息時(shí)間段的存在，因此，在解碼過程中需要考慮工件加工可恢復(fù)與不可恢復(fù)情形，如圖2所示。從圖中可知加工可恢復(fù)與加工不可恢復(fù)對工件的加工完成時(shí)刻存在明顯影響。

圖2 工件加工可恢復(fù)與不可恢復(fù)的解碼示例

2.2 選擇

為盡可能讓適應(yīng)度高的個(gè)體被保留，本文選擇后代個(gè)體的方式是以輪盤賭策略為基礎(chǔ)，輔以精英策略相結(jié)合。輪盤賭策略可有效防止問題的解步入局部最優(yōu)化陷阱，精英策略則確保種群向更高質(zhì)量的方向進(jìn)化，兩者有效結(jié)合，加速了種群的迭代和求解速度。

2.3 交叉與變異

在遺傳算法中，交叉操作是為了在不發(fā)生優(yōu)質(zhì)基因損失的情況下產(chǎn)生新的個(gè)體。本文主要采用部分映射交叉PMX。具體步驟如下：

步驟1：隨機(jī)選擇并交換父代的基因片段；

步驟2：找到步驟1基因片段的映射關(guān)系；

步驟3：根據(jù)步驟2的映射關(guān)系合法化子代。

以n=6的流水車間調(diào)度為例，PMX如圖3所示，其中父代1選擇的基因片段為6、2、4；對應(yīng)的父代2選擇的基因片段為2、1、3；基因片段的映射關(guān)系為6對應(yīng)1，4對應(yīng)3。

圖3 PMX示例

為了避免陷入局部最優(yōu)解，應(yīng)該使用變異算子來增加交叉后種群的多樣性。本文應(yīng)用兩點(diǎn)交換變異算子。交叉操作和變異操作協(xié)同完成搜索空間的全局搜索和局部搜索。

2.4 禁忌搜索

在FSP-CTW中，由于作息時(shí)間的存在，工件的加工可能在不同的工作時(shí)段，而工作時(shí)段之間存在休息時(shí)段，因此可能不存在完整的關(guān)鍵路徑，為提高搜索效率，在原有算法的基礎(chǔ)上加入了禁忌搜索，防止在搜索過程中陷入局部最優(yōu)的同時(shí)還可以搜索更多解空間。具體流程如圖4所示。

圖4 算法流程圖

在車間調(diào)度問題的求解中，常用的禁忌搜索方法是插入式方法，即將工件插入到其他工件之間加工。將搜索方式分為3種：向前插入，向后插入，交換。搜索方式與任意兩道工序結(jié)合構(gòu)成禁忌表。比如，以圖2的編碼為例，禁忌搜索表為{1,5，“1”}，則表示將工件5插入到工件1之前，即工件5的加工在工件1之前，示例及結(jié)果如圖5所示。

圖5 禁忌搜索示例

3 案例仿真與分析

為方便研究FSP-CTW，設(shè)計(jì)15個(gè)案例，工件數(shù)量10～100，機(jī)器數(shù)量5～20，加工時(shí)間服從1～100的均勻分布，加工時(shí)間單位為min。將調(diào)度起始日期設(shè)置為2020年7月6日，工作制、工作時(shí)段均設(shè)置為5 0 1 2 3 4 8 2 4 1 4 -1，即均為5天工作制，每個(gè)工作日的調(diào)度起始時(shí)刻為8 h，則每個(gè)工作日的工作時(shí)段為8 h～12 h，13 h～17 h。

實(shí)驗(yàn)設(shè)計(jì)如表2所示，其中A組不考慮作息時(shí)間，B組中工件加工均可恢復(fù)，可采取直接映射的策略，即將調(diào)度方案直接應(yīng)用在FSP-CTW模型中，并重新解碼，C組中工件加工均不可恢復(fù)，采取兩階段優(yōu)化策略，即在第一階段不考慮作息時(shí)間，第二階段考慮作息時(shí)間并將第一階段的調(diào)度方案作為初始調(diào)度方案，進(jìn)行再優(yōu)化。

表2 實(shí)驗(yàn)設(shè)計(jì)

A、B組以及C組第一階段的算法參數(shù)設(shè)置為種群規(guī)模為200，交叉概率為0.80，變異概率為0.05，最大迭代次數(shù)為150。C組中第二階段的算法參數(shù)將最大迭代次數(shù)設(shè)置為60，最大值滯留代數(shù)設(shè)置為20。每個(gè)案例各運(yùn)行10次，實(shí)驗(yàn)結(jié)果如表3所示，其中L表示總工序數(shù)量，A～C列的值表示算法的最優(yōu)結(jié)果，表示2020年7月6日至調(diào)度最大完成時(shí)刻的時(shí)間，時(shí)間單位為min。

表3 實(shí)驗(yàn)結(jié)果

從實(shí)驗(yàn)結(jié)果可以看出A、B、C三組的最優(yōu)結(jié)果存在C>B>A的關(guān)系，表明作息時(shí)間的存在、加工可恢復(fù)與加工不可恢復(fù)均對調(diào)度目標(biāo)存在影響。A組中，Case1、Case2的結(jié)果最為集中，其在B組中的結(jié)果最為集中，表明采用的算法具有較好的效果。結(jié)合單因素分析方法，通過對比分析作息時(shí)間的存在、加工可恢復(fù)與加工不可恢復(fù)均對調(diào)度目標(biāo)的影響。對比組合為A-B、A-C與B-C，顯著性水平設(shè)置為0.05，分析結(jié)果p值均小于0.05，表明作息時(shí)間的存在、加工可恢復(fù)與加工不可恢復(fù)均對調(diào)度目標(biāo)存在顯著影響。因此，在調(diào)度中有必要考慮休息時(shí)段和考慮工件加工是否恢復(fù)。其中Case9的A-C組最優(yōu)結(jié)果的甘特圖分別如圖6～圖8所示。

圖6 Case9的A組最優(yōu)甘特圖

圖7 Case9的B組最優(yōu)甘特圖

圖8 Case9的C組最優(yōu)甘特圖

由表3可知，Case9的A-C組最優(yōu)結(jié)果分別為4280、15 380與16 727，分別對應(yīng)2020年7月8日23時(shí)20分、2020年7月16日16時(shí)20分與2020年7月17日14時(shí)47分，與圖6～圖8吻合。當(dāng)加工可恢復(fù)時(shí)，一些工序跨越了休息時(shí)間段，而加工不可恢復(fù)時(shí)，工序均不可跨越休息時(shí)間段，僅被安排在工作時(shí)段內(nèi)，驗(yàn)證了算法的正確性。

4 結(jié)論

本文以最小化工期為目標(biāo)研究了考慮作息時(shí)間的流水車間調(diào)度問題(FSP-CTW)：

(1)描述了FSP-CTW的特征，建立了同時(shí)考慮工件加工可恢復(fù)與加工不可恢復(fù)的FSP-CTW數(shù)學(xué)模型；

(2)簡要分析了加工可恢復(fù)與加工不可恢復(fù)情形下的解碼及對工期的影響；

(3)采用遺傳算法、禁忌搜索求解FSP-CTW，同時(shí)為減少運(yùn)算量，提出了兩種求解策略：直接映射和兩階段優(yōu)化；

(4)設(shè)計(jì)了15個(gè)不同規(guī)模的案例進(jìn)行仿真實(shí)驗(yàn)，結(jié)果驗(yàn)證了模型及算法的正確性、有效性；

(5)采用單因素分析方法對仿真結(jié)果進(jìn)行分析，通過兩兩對比分析，發(fā)現(xiàn)了作息時(shí)間的存在、工件加工可恢復(fù)與不可恢復(fù)對調(diào)度工期有著顯著影響。