任丹妮，熊禾根，陽光燦

(武漢科技大學(xué)a.冶金裝備及其控制教育部重點實驗室;b.機械傳動與制造工程湖北省重點實驗室,武漢 430000)

0 引言

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

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

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

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

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

1.1 問題描述

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

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

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

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

(3)同一時刻，一臺機器只能加工一個工件，且一個工件只能被一臺機器加工；

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

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

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

(7)不考慮機器故障、機器維護、機器維修等動態(tài)因素；

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

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

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

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

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

續(xù)表

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

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

(1)

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

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

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

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

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

2 求解FSP-CTW的改進遺傳算法

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

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

2.1 編碼與解碼

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

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

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

2.2 選擇

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

2.3 交叉與變異

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

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

步驟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)用兩點交換變異算子。交叉操作和變異操作協(xié)同完成搜索空間的全局搜索和局部搜索。

2.4 禁忌搜索

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

圖4 算法流程圖

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

圖5 禁忌搜索示例

3 案例仿真與分析

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

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

表2 實驗設(shè)計

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

表3 實驗結(jié)果

從實驗結(jié)果可以看出A、B、C三組的最優(yōu)結(jié)果存在C>B>A的關(guān)系，表明作息時間的存在、加工可恢復(fù)與加工不可恢復(fù)均對調(diào)度目標存在影響。A組中，Case1、Case2的結(jié)果最為集中，其在B組中的結(jié)果最為集中，表明采用的算法具有較好的效果。結(jié)合單因素分析方法，通過對比分析作息時間的存在、加工可恢復(fù)與加工不可恢復(fù)均對調(diào)度目標的影響。對比組合為A-B、A-C與B-C，顯著性水平設(shè)置為0.05，分析結(jié)果p值均小于0.05，表明作息時間的存在、加工可恢復(fù)與加工不可恢復(fù)均對調(diào)度目標存在顯著影響。因此，在調(diào)度中有必要考慮休息時段和考慮工件加工是否恢復(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時20分、2020年7月16日16時20分與2020年7月17日14時47分，與圖6～圖8吻合。當加工可恢復(fù)時，一些工序跨越了休息時間段，而加工不可恢復(fù)時，工序均不可跨越休息時間段，僅被安排在工作時段內(nèi)，驗證了算法的正確性。

4 結(jié)論

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

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

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

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

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

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