帶有工件實際加工時間上界的調度問題研究

虞先玉， 游 運， 溫榮生

(東華理工大學理學院，江西 南昌 330000)

在很多的調度問題研究中，工件的加工時間都被認為是在工件加工過程中是保持不變的(Graham et al.，1979;程朋根等，2002;周玨等，2009)。在很多實際情況下，工件的實際加工時間會因為生產機器老化、生產人員不斷積累生產經驗等因素影響而變化。在老化因素主導的環(huán)境中，工件在生產序列中越靠后，工件的實際加工時間就越長;在學習因素主導的環(huán)境中，工件在生產序列中越靠后，工件的實際加工時間就越少。

關于老化和學習影響的調度研究在過去十年里受到越來越多學者們的關注。其中大多數研究假設工件實際加工時間服從特殊的老化或學習函數模型。在這些研究中(如 Biskup，2004;Kuo，2008;Yang et al.，2010a，2010b;Zhao，2010)使用了指數函數模型;另外一些研究(Cheng，2000;Bachman，2004;Wang，2006)考慮了不同形式的線性模型。一些學者則給出了線性函數和指數函數組合的模型(Lee，2004;Cheng et al.，2008;Wang，2007a;Wang，2007b;Cheng，2010)。Yin et al.(2009)研究了一類位置依賴的學習函數模型，其中涵蓋了很多已有的相關研究成果。Lai et al.(2011)提出了一類以已加工工件的加工時間和加工位置為變量的一般性學習函數模型。Yin et al.(2009)和Lai et al.(2011)研究的函數工件實際加工時間模型仍然部分包含有加法及乘法運算。只有少數的研究(Mosheiov et al.，2003;Mosheiov，2011)包含沒有任何特殊結構的工件加工時間函數模型。

在實際的車間生產過程中，生產機器往往會受到磨損或零件老化，需要定期或不定期的機器維護以防止機器持續(xù)不健康運行或損壞。因此，很多研究(Ji et al.，2006;Kuo et al.，2008;Gawiejnowicz et al.，2010;Yang et al.，2010;Zhao et al.，2010)報道了帶有機器維護的調度問題。另外，在實際的食品加工或陶瓷燒制等加工過程中，每件產品往往會有一個不允許超過實際加工時間上界。如果超過時間上界，加工完的產品就會有瑕疵或缺陷。帶有老化或學習時間限制的調度問題近年受到了學者們的關注。Inderfurth et al.(2006)研究了一類舊產品恢復再制造的調度問題，引入了一個給定的產品老化(或惡化)時間限制;如果某個產品沒有超過這個老化時間限制，這個產品就可以回收再利用和制造新產品，否則產品則不能用于再制造。Gawiejnowicz(2007)研究了一類每個工件帶有準備時間和生產期限的單機調度問題。

目前很少有同時考慮加工時間上界、一般性工件加工時間函數和機器維護的調度研究工作。由此啟發(fā)，本文將分別研究帶有工件實際加工時間上界限制的單機調度問題和平行機調度問題。對于單機調度問題，考慮了機器維護，研究的目標函數是最小化工件總完工時間;對于平行機調度問題，分別考慮了工件的實際加工時間函數有單調性和沒有單調性兩種情形，研究的目標函數為最小化機器的總負荷。

1 問題構建和符號說明

基本的模型和所研究問題表述如下:

對于單機調度問題，假設在生產車間中有n個工件J1，J2，……，Jn需要被安排在機器上生產。工件Jj(j=1，2，…，n)的正常加工時間和完工時刻分別記為pj和Cj。假設每次機器維護的時間為t。當機器進行維護時，假設機器是不運轉的，進而生產過程是停止的。經過每次機器維護，機器就恢復到初始狀態(tài)。機器維護頻率記為m，不等式m≤μ(μ往往遠小于工件個數n)，則表示機器維護次數不能超過次維護。

當一個可行的排序調度中進行了k(即m=k)次機器維護時，則所有機器上的工件就被次機器維護劃分成k+1個工件組。令Mi表示第i(1≤I≤k)次維護，Gi表示第i(1≤i≤k+1)個工件組。進而，整個調度可以表示為[G1，M1，G2，M2…，Mk，Gk+1]。當工件Jj被安置在第i個工件組的第r個位置上時，其實際加工時間為:

由于機器在維護后就恢復到初始狀態(tài)，工件實際加工時間只同工件的正常加工時間和工件在每個組中排序位置有關，與工件組序號無關。在不引起混淆的情形下，令

當工件被排在工件組的第一個位置，位置依賴影響沒有發(fā)生，因此得到:

設工件Jj的實際加工時間上界為Uj。對于每一個可行的調度，工件Jj的實際加工時間必須不大于Uj(1≤j≤n)工件的初始加工時間必須滿足pj≤Uj(1≤j≤n)，否則所研究的調度問題就已經沒有可行的調度方案。

對于所要研究的平行機問題，假設在生產車間中有n個工件J1，J2，…，Jn需要被安排在平行機器上生產加工。所有的工件在零時刻開始都是可用于調度的。同單機問題一樣，工件Jj(j=1，2，…，n)的正常加工時間和完工時刻分別記為pj和Cj。當工件Jj安置在機器i上第r個位置上時，其實際加工時間為:

因為平行機的調度中機器是同規(guī)格的，所以同一個工件在不同機器的相同排序位置上的實際加工時間是相同的。在不引起混淆的情形下，令

同(3)式類似，當工件排在機器第一個位置時，其實際加工時間為:

一些研究(Graham et al.，1979;Agnetis et al.，2004 和 Kuo et al.，2008)中所使用的三階段方法表示所研究的問題。

首先考慮的是一類單機調度問題:其優(yōu)化目標為總完工時刻最小化的問題;工件實際加工時間有相應的上界，機器維護的次數有上界。把這類調度問題表示為:

相似地，帶有一般性位置依賴影響的最小化機器總負荷的平行機調度問題可以表示為:

2 問題的相關性質與求解算法

2.1 單機問題

由于prj≤Uj，構建新的工件的實際加工時間函數:

證明: 這里利用類似于Mosheiov(2012)中處理一般性位置依賴的平行機調度問題的方法處理1首先，分別給出各種維護次數下的n個工件的各種分組。當維護次數m=μ時，工件被機器維護分隔成μ+1組，由Ji et al.(2010)可知，這時工件分組過程的計算復雜度為O(nμ)。顯然滿足維護次數約束的機器維護次數可能為 0，1，2，…，μ。因此，全部的分組過程的計算復雜度為:O(n1)+O(n2)+… +O(nμ)=O(nμ)。

接著，對于每一個工件分組，確定各個工件組內工件的排序，使目標函數∑Cj最小化。不失一般性，對于一個工件分組(n1，n2，…，nm+1)，可以把問題1轉化為如下標準的任務分派問題:

其中當工件j被安排在第i組的第r個位置時xijr=1，否則xijr=0。眾所周知，標準的任務分派問題得到最優(yōu)調度的復雜度為O(n3)。

對于每一個工件分組都得出一個最優(yōu)調度，比較所有的分組的最優(yōu)調度目標函數值，得到最小的目標函數值及其對應的調度。若所得到目標函數值小于A1，則得到滿足條件grj≤Uj的最優(yōu)目標函數值及其對應的最優(yōu)調度;否則，則不存在滿足條件的調度。此過程的計算復雜度為O(nμ)。

綜合以上分析，整個求解過程的計算復雜度為:O(nμ)× O(n3)+O(nμ)=O(nμ+3)證畢。

算法1

2.2 平行機問題

對于平行機問題pm|prj=fj(pj，r)|TL ∶prj≤Uj，令 J[l，r]及 p[l，r]、C[l，r]分別表示排在第 l臺機器第r個位置的工件及其正常加工時間、實際加工時間、完工時刻。

對于平行機問題pm|prj=fj(pj，r)|TL:prj≤Uj，考慮到 prj≤Uj，構建新的工件的實際加工時間函數:

證明:把每一臺機器上的工件看作一個工件組，列出n個工件的分成m組的各種分組情形。由研究Ji et al.(2010)可知，此時工件分組過程的計算復雜度為 O(nm－1)。

對于每一個工件分組，確定各個工件組內工件的排序，使目標函數TL最小化。不失一般性，對于一個工件分組(n1，n2，…，nm)，可以把問題 pm|prj=fj(pj，r)|TL:prj≤Uj轉化為如下標準的任務分派問題:

其中當工件j被安排在第i組的第r個位置時xijr=1，否則xijr=0。這一步任務分派問題尋優(yōu)操作的復雜度為O(n3)。

比較所有的分組的最優(yōu)調度目標函數值，得到最小的目標函數值及其對應的調度。若所得到目標函數值小于A2，則得到滿足條件prj≤Uj的最優(yōu)目標函數值及其對應的最優(yōu)調度;否則，則不存在滿足條件prj≤Uj的調度，此過程的計算復雜度為O(nm－1)。

綜合以上分析，整個求解過程的計算復雜度為:O(nm－1)× O(n3)+O(nm－1)=O(nm+2)。證畢。

根據以上證明過程，給出求解問題pm|prj=fj(pj，r)|TL:prj≤Uj的算法2:

算法2

計算出 f(j2)(pj，r)

列出n個工件分成m組所有組合情形;

記所有工件分組數目為N′;

處理任務分派問題(1 5)～(1 8);

計算出T L(k);

在工件實際加工時間關于排序位置而單調遞增的條件下，分析平行機問題pm|prj=fj(pj，r)|TL:prj≤Uj的求解復雜度。

Kuo et al.(2008)提出的帶有機器維護的單機調度問題的組平衡原則。在問題pm|prj=fj(pj，r)|TL:prj≤Uj中，一共有m臺機器可供使用。則在每一個可行的調度中，工件被分成m個工件組，問題pm|prj=fj(pj，r)|TL:prj≤Uj對應的組平衡原則可以表述如下:n個工件被分成m個工件組G1，…，Gi，…，Gm;記分組Gi(1≤i≤m)的工件個數為ni(1≤i≤ m)，則滿足[n/m]≤ ni≤[n/m]+1。

引理1 對于問題pm|prj=fj(pj，r)|TL ∶prj≤Uj，如果工件實際加工時間關于排序位置而單調遞增，必存在其最優(yōu)調度滿足分組平衡原則。

證明: 由于工件實際加工時間fj(pj，r)關于排序位置而單調遞增，運用類似于 Zhao et al.(2010)分析方法，容易證明存在問題pm|prj=fj(pj，r)|TL:prj≤Uj的最優(yōu)調度滿足分組平衡原則。證畢。

定理3 對于問題pm|prj=fj(pj，r)|TL:prj≤Uj，如果工件實際加工時間關于排序位置而單調遞增，問題求解的計算復雜度為O(n3)。

證明:由引理1，當工件實際加工時間關于排序位置而單調遞增時，其最優(yōu)調度必滿足分組平衡原則。由于考慮的平行機，各機器認為是無差異的。因此設l=n－n×[n/m](l可能為0)，令 n1=n2=… =nl= [n/m]+1，nl+1= … =nm=[n/m]。由此，得到最優(yōu)調度的工件分組，問題pm|prj=fj(pj，r)|TL:prj≤Uj可以轉化為任務分派問題(15)～(18)，其求解的計算復雜度為O(n3)。證畢。

由定理3的證明過程，給出工件實際加工時間關于排序位置而單調遞增條件下，問題pm|prj=fj(pj，r)|TL:prj≤Uj的求解算法3。

算法3

計算出 f(j2)(pj，r)

按照分組平衡原則把n個工件分成m組;

處理任務分派問題(15)～(18);

計算出最優(yōu)的總負荷TL*。

3 結論

研究了帶有工件實際加工時間上界的一般性位置依賴的單機調度和平行機調度決策問題。對于目標函數為總完工時刻且機器維護次數有上界μ的單機調度問題，分析得出求解問題的計算復雜度為O(nμ+3)，并給出了求解算法原碼。對于目標函數為機器總負荷的臺平行機的調度問題，分析得到求解問題的計算復雜度為O(nm+2)，并根據計算復雜度的分析過程，給出了求解算法原碼;當工件實際加工時間關于排序位置單調遞增時，則證明了求解研究平行機調度問題的計算復雜度可以下降到O(n3)。

程朋根，熊助國，韓麗華.2002.基于GPS技術的大型結構物健康動態(tài)監(jiān)測[J].華東地質學院學報，25(4):324-328.

周玨，程朋根，李靜.2009.基于MS4W和GPRS/GSM的車輛綜合監(jiān)控系統(tǒng)設計與實現[J].東華理工大學學報:自然科學版，32(2):177-180.

Agnetis A，Mirchandani P B，Pacciarelli D，Pacifici A.2004.Scheduling problems with two competing agents[J].Operations Research，52:229-242.

Bachman A，Janiak A.2004.Scheduling jobs with position-dependent processing times[J].Journal of the Operational Research Society，55:257-264.

Biskup D.1999.Single-machine scheduling with learning considerations[J].European Journal of Operational Research，115:173-178.

Cheng T C E，Lee W C.2010.Scheduling problems with deteriorating jobs and learning effects including proportional setup times[J].Computers＆ Industrial Engineering，58(2):326-331.

Cheng T C E，Wu C C，Lee W C.2008.Some scheduling problems with deteriorating jobs and learning effects[J].Computers and Industrial Engineering，54:972-982.

Cheng T C E，Wang G.2000.Single machine scheduling with learning effect considerations[J].Annals of Operations Research，98:273-290.

Gawiejnowicz S.2007.Scheduling deteriorating jobs subject to job or machine availability constraints[J].European Journal of Operational Research，180(1):472-478.

Graham R L，Lawler E L，Lenstra J K，et al.1979.Optimization and approximation in deterministic sequencing and scheduling:A survey[J].Annals of Discrete Mathematics，5:287-326.

Inderfurth K，Janiak A，Kovalyov M Y，Werner F.2006 Batching work and rework processes with limited deterioration of reworkables[J].Computers＆ Industrial Engineering，33:1595-1605.

Ji M，Cheng T C E.2010.Scheduling with job dependent learning effects and multiple rate-modifying activities[J].Information Processing Letters，110:460-463.

Kuo W，Yang D L.2008.Minimizing the makespan in a single machine scheduling problem with the cyclic process of an aging effect[J].Journal of the Operational Research Society，59:416-420.

Lai P J，Lee W C.2011.Single-machine scheduling with general sumof-processing-time-based and position-based learning effects[J].O-MEGA-The International Journal of Management Science，39(5):467-471.

Lee W C.2004.A note on deteriorating jobs and learning in single-machine scheduling problems[J].International Journal of Business and Economics，3:83-89.

Mosheiov G，Sidney J.2003.Scheduling with general job-dependent learning curves[J].European Journal of Operational Research，147:665-670.

Mosheiov G.2011.Proportionate flowshops with general position-dependent processing times[J].Information Processing Letters，111(4):174-177.

Mosheiov G.2012.A note:Multi-machine scheduling with general position-based deterioration to minimize total load[J].International Journal of Production Economics，135(1):523-525.

Wang J B，Xia Z Q.2006.Flow shop scheduling with deteriorating jobs under dominating machines[J].OMEGA-The International Journal of Management Science，34(4):327-336.

Wang J B.2007a.Single-machine scheduling problems with the effects of learning and deterioration[J].OMEGA-The International Journal of Management Science，35(4):397-402.

Wang，J B，Cheng T C E.2007b.Scheduling problems with the effects of deterioration and learning[J].Asia-Pacific Journal of Operational Research，24:1-17.

Yang S J，Yang D L，Cheng T C E.2010a.Single-machine due-window assignment and scheduling with job-dependent aging effects and deteriorating maintenance[J].Computers＆ Operations Research，37:1510-1514.

Yang S J，Yang D L.2010b.Minimizing the makespan on single-machine scheduling with aging effect and variable maintenance activities[J].OMEGA-The International Journal of Management Science，38:528-533.

Yin Y Q，Xu D H，Sun K B，et al.2009.Some scheduling problems with general position-dependent and time-dependent learning effects[J].Information Science，179:2416-2425.

Zhao C L，Tang H Y.2010.Single machine scheduling with general job-dependent aging effect and maintenance activities to minimize makespan.Applied Mathematical Modelling[J].34:837-841.