虞先玉， 游 運， 溫榮生

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

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

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

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

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

1 問題構(gòu)建和符號說明

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

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

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

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

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

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

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

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

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

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

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

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

2 問題的相關(guān)性質(zhì)與求解算法

2.1 單機問題

由于prj≤Uj，構(gòu)建新的工件的實際加工時間函數(shù):

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

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

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

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

綜合以上分析，整個求解過程的計算復(fù)雜度為: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，構(gòu)建新的工件的實際加工時間函數(shù):

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

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

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

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

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

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

算法2

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

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

記所有工件分組數(shù)目為N′;

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

計算出T L(k);

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

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

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

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

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

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

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

算法3

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

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

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

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

3 結(jié)論

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

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

周玨，程朋根，李靜.2009.基于MS4W和GPRS/GSM的車輛綜合監(jiān)控系統(tǒng)設(shè)計與實現(xiàn)[J].東華理工大學(xué)學(xué)報:自然科學(xué)版，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.