考慮維護且原材料易變質(zhì)的單機調(diào)度問題

石 梅，石 帥，汪 晴

(1.淮北師范大學，安徽 淮北 235000；2.皖西學院，安徽 六安 237012)

機器調(diào)度問題作為一類重要的組合優(yōu)化問題，被廣泛應用于企業(yè)生產(chǎn)管理等領域。傳統(tǒng)的機器調(diào)度問題一般假設機器在一個調(diào)度周期內(nèi)一直可用，而在現(xiàn)實的生產(chǎn)作業(yè)環(huán)境下，機器往往由于需要進行定期維護及生產(chǎn)工具更換而造成在某段時間無法連續(xù)使用。機器故障耗費成本相對于維護成本來說更大，產(chǎn)生的后果也更為嚴重，實施維護對機器性能保證更為有利。因此，將機器因維護導致的機器不可用情形考慮到生產(chǎn)調(diào)度中具有重要的現(xiàn)實意義。

近年來，基于維護的單機調(diào)度問題引起許多學者關注，Lee 和Liman[1]對單機情形下機器具有維護時段的完工時間和問題進行分析，證明出SPT(shortest processing time，短作業(yè)優(yōu)先)規(guī)則求解此問題的最壞情況誤差界為2/7。針對同樣的問題，Qi等[2]給出了3種啟發(fā)式算法和一個分支定界算法進行求解。以上都針對作業(yè)不可中斷情形，也有一些學者對作業(yè)部分可恢復的單機調(diào)度問題進行研究，目標函數(shù)為最小化最大完工時間時，LPT(longest processing time，長作業(yè)優(yōu)先)算法求解此問題的最大情況誤差界為α/2，其中α為需要再一次進行加工的系數(shù)[3]，馬英等[4]在另一篇文章中為此問題求解構(gòu)造了一個啟發(fā)式算法，并給出了其相對誤差界。

上述研究僅考慮了機器具有不可用時段一個約束，也有學者將機器具有不可用時段和其他因素結(jié)合考慮。蔣志高和董明[5]同時考慮了機器維護和作業(yè)加工時長可變兩種約束，目標函數(shù)為最小化最大完工時間。謝謝等[6]則認為對于一些加工時間較長且懲罰較小的工件存在拒絕加工情形，將機器具有周期維護和工件可拒絕結(jié)合分析，求解目標為最小化加工工件的總完工時間與拒絕工件的懲罰和。王昕等[7]同時考慮了周期維護和工時惡化兩種約束，以最小化最大拖期成本和維護成本為求解目標。甘捷和曾建潮[8]對預防性維護和維修共存的情形進行分析，基于故障閥值的視情維護和役齡的混合維修策略建立了加工作業(yè)總期望完成時間最小化的集成優(yōu)化模型；針對同一目標問題，甘捷[9]在視情維修的基礎上增加了性能可靠性約束，為建立隨機集成優(yōu)化模型，推導出預防性維修概率及概率密度函數(shù)表達式，并給出了求解方法。

目前，大多數(shù)研究集中在經(jīng)典調(diào)度環(huán)境，不考慮原材料、產(chǎn)成品會變質(zhì)的情形，而現(xiàn)實生活中許多產(chǎn)品如牛奶、水果等都會隨著時間推移發(fā)生變質(zhì)。易變質(zhì)產(chǎn)品對作業(yè)環(huán)境要求更高，機器故障的損失更大，也更普遍，維護保養(yǎng)對這類環(huán)境的機器性能保證尤為重要。因此，本文對原材料易變質(zhì)性和機器存在維護時段聯(lián)合約束下的單機調(diào)度問題進行分析，目標函數(shù)為作業(yè)的總變質(zhì)成本最小。

1 問題描述和符號表示

B：維護時段的開始時間；

F：維護時段的結(jié)束時間；

pj：作業(yè)Jj的加工時間，?j∈{1,2,…,n}；

λj1：作業(yè)Jj的原材料在第一階段單位時間的變質(zhì)成本，即變質(zhì)率；

λj2：作業(yè)Jj的原材料在第二階段的單位時間變質(zhì)成本，即變質(zhì)率；

tk：原材料變質(zhì)率的分界點，即[0,tk]屬于第一階段，(tk，+∞)屬于第二階段，tk為一具體的常數(shù)，不因作業(yè)的不同而改變；

sj：作業(yè)Jj的開工時間，?j∈{1,2,…,n}；

tcj：作業(yè)Jj的變質(zhì)成本；

TC：所有作業(yè)的總變質(zhì)成本；

目標函數(shù)為：minTC.

2 最優(yōu)解性質(zhì)

通過分析該調(diào)度問題最優(yōu)解的特征，根據(jù)解的性質(zhì)提出相應的解決方法，思路主要是基于最優(yōu)解性質(zhì)設計啟發(fā)式算法和對模擬退火算法進行改進。

性質(zhì)1：在最優(yōu)解中，對于維護時段之前的作業(yè)集和維護時段之后的作業(yè)集，其tk在之前開工的作業(yè)子集分別服從以第一階段變質(zhì)率λj1為權重的WSPT(Weighted Shortest Processing Time first)規(guī)則。

圖1 性質(zhì)1作業(yè)加工順序交換示意圖

Δ=λk1*s1-λj1*(s1+pk)-λj1*s1-λk1*(s1+pi)

=λi1*pk-λk1*pi

性質(zhì)2：對于維護時段之前的作業(yè)集和維護時段之后的作業(yè)集，在tk之后開工的作業(yè)分別服從以第二階段變質(zhì)率λj2為權重的WSPT規(guī)則。

圖2 性質(zhì)2作業(yè)加工順序交換示意圖

Δ=λj1*tk+λj2*(s-tk)+λi1*tk+λi2*(s+pj-tk)-λi1*tk

+λi2*(s+tk)+λj1*tk+λj2*(s+pi-tk)

=λi2*pj*λj2*pi

3 求解算法

為解決該問題，結(jié)合上述性質(zhì)設計了啟發(fā)式算法和改進的模擬退火算法，分布用H1和SA1表示，基于算法進行調(diào)度所有作業(yè)，實現(xiàn)作業(yè)的總變質(zhì)成本最小化的目標。

3.1 啟發(fā)式算法H1

Step 2：將在維護時段之前完工的作業(yè)加工時間和記為T，將F之后的作業(yè)ji重新編號，i=1,2,…,n。令初始i=1。

Step 3：驗證T

Step 4：驗證ji是否滿足T+pi≤B，若滿足則插入，將T=T+pi轉(zhuǎn)第五步，否則轉(zhuǎn)第五步。

Step 5：i=i+1，若i≤n轉(zhuǎn)第三步，否則轉(zhuǎn)第六步。

Step 6：將維護時段之前的作業(yè)集合記為B1，將維護時段之后的作業(yè)集合記為B2，將B1中開工時間在tk之前的作業(yè)集合記為B1a，開工時間等于tk或大于tk的作業(yè)集合記為B1b，將B2中開工時間在tk之前的作業(yè)集合記為B2a，開工時間等于tk或大于tk的作業(yè)集合記為B2b。

3.2 改進的模擬退火算法SA1

Step 2：設置相關參數(shù)。初始溫度設置為TE=1000*TC*；算法終止的溫度設置為ε=0.001，降溫速度θ設為0.95；同一溫度下迭代次數(shù)設置為L=n2/2。

Step 3：若TE≤ε則返回當前解π，并計算其目標函數(shù)值TC(π)，結(jié)束。

Step 4：在當前的調(diào)度序列中，隨機選擇一個作業(yè)j(允許作業(yè)j是維護時段之前的作業(yè)，當作業(yè)j為維護時段之前的作業(yè)時，相當于維護時段之前作業(yè)集內(nèi)部轉(zhuǎn)移)，若將作業(yè)j插入到維護時段之前仍能夠在維護時段之前完工，則進行將作業(yè)j插入。轉(zhuǎn)第六步。

Step 5：在當前解中，在維護時段之前開工的作業(yè)中隨機選擇一個作業(yè)j，在維護時段之后的作業(yè)中隨機選擇一個作業(yè)j'，若交換后j'能夠在維護時段之前完工，則交換作業(yè)j和j'的所在位置然后轉(zhuǎn)第六步，否則轉(zhuǎn)第四步。

Step 7：ΔTC=TC(σ)-TC(π)；如果ΔTC<0，則轉(zhuǎn)第九步；否則轉(zhuǎn)第八步。

Step 9：L=L-1；如果L=0，則TE=θ*TE轉(zhuǎn)第三步，否則轉(zhuǎn)第四步。

3.3 算例

本小節(jié)給出一個算例旨在說明算法的求解過程。

例1：[B,F]=[4,6],tk=10，各個作業(yè)的基本信息如表1所示：

表1 例1作業(yè)參數(shù)

根據(jù)算法第一步：對5個作業(yè)進行初始化排序分別為：j5，j1，j4，j2，j3，依照此時排序所有的作業(yè)都將安排在不可用時段之后進行加工，根據(jù)算法第二步：F之后進行加工的作業(yè)從新編號：j1，j2，j3，j4，j5，此時在B之前加工的作業(yè)長度T為0，i=1執(zhí)行算法第三步，當前T

圖3 例1的調(diào)度序列

4 仿真實驗及分析

通過對表2和表3中數(shù)據(jù)的比較分析我們可以發(fā)現(xiàn)：

(1)對于每一種作業(yè)情形下，通過SA1算法得到的目標函數(shù)值總體是優(yōu)于運用啟發(fā)式算法H1得到的目標函數(shù)值，從目標函數(shù)值更優(yōu)的角度SA1算法性能更好。

(2)對于固定的作業(yè)數(shù)目，系數(shù)β的取值不同所得到的標函數(shù)值有所不同，優(yōu)化的程度也有所不同。比較表2和表3中的計算值可以看出，作業(yè)數(shù)目相同時，β=0.5時兩種算法所得到的解都更優(yōu)于β=1.0時所得到的解。

(3)對于固定的系數(shù)β，對比表3和表4中的數(shù)據(jù)可以發(fā)現(xiàn)，隨著作業(yè)數(shù)目的增加，SA1算法得到的解的目標函數(shù)值比算法的優(yōu)化程度更大，也就是誤差界是逐漸增大的。

(4)對比表2和表3可知，SA1算法在作業(yè)長度服從U[1,20]隨機分布時比在作業(yè)分布服從U[1,100]隨機分布時相對于算法的優(yōu)化程度更高，具有更好的效果。

表2 作業(yè)長度服從U[1，20]隨機分布的實驗結(jié)果

表3 作業(yè)長度服從U[1，100]隨機分布的實驗結(jié)果

5 結(jié)論

本文解決了在考慮預防性維護的情形下，同時考慮作業(yè)在調(diào)度時原材料具有變質(zhì)特性的單機調(diào)度問題，目標函數(shù)為最小化作業(yè)的總變質(zhì)成本。通過對調(diào)度問題的分析，提出了一個啟發(fā)式算法H1和改進的模擬退火算法SA1。仿真結(jié)果表明，兩種算法均能在合理的計算時間內(nèi)求解出數(shù)據(jù)規(guī)模較大問題的滿意解，同時計算結(jié)果表明改進的模擬退火算法在求解精度上總體更優(yōu)于啟發(fā)式算法H1，并且隨著作業(yè)量的增多改進更加明顯。

本文僅考慮了單機情形下具有單個維護時段情況，在今后的研究中，可有以下幾種擴展方向，一方面可以保持單機情形，尋求問題的下界或分析更為復雜的維護情形；另一方面可考慮更為復雜的機器環(huán)境，如平行機、同類機等。