考慮維護且原材料易變質的單機調度問題

石 梅，石 帥，汪 晴

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

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

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

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

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

1 問題描述和符號表示

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

F：維護時段的結束時間；

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

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

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

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

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

tcj：作業Jj的變質成本；

TC：所有作業的總變質成本；

目標函數為：minTC.

2 最優解性質

通過分析該調度問題最優解的特征，根據解的性質提出相應的解決方法，思路主要是基于最優解性質設計啟發式算法和對模擬退火算法進行改進。

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

圖1 性質1作業加工順序交換示意圖

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

=λi1*pk-λk1*pi

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

圖2 性質2作業加工順序交換示意圖

Δ=λ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 求解算法

為解決該問題，結合上述性質設計了啟發式算法和改進的模擬退火算法，分布用H1和SA1表示，基于算法進行調度所有作業，實現作業的總變質成本最小化的目標。

3.1 啟發式算法H1

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

Step 3：驗證T

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

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

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

3.2 改進的模擬退火算法SA1

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

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

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

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

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

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

3.3 算例

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

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

表1 例1作業參數

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

圖3 例1的調度序列

4 仿真實驗及分析

通過對表2和表3中數據的比較分析我們可以發現：

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

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

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

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

表2 作業長度服從U[1，20]隨機分布的實驗結果

表3 作業長度服從U[1，100]隨機分布的實驗結果

5 結論

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

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