虞先玉， 游 運(yùn)， 溫榮生

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

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

關(guān)于老化和學(xué)習(xí)影響的調(diào)度研究在過(guò)去十年里受到越來(lái)越多學(xué)者們的關(guān)注。其中大多數(shù)研究假設(shè)工件實(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)研究了一類(lèi)位置依賴的學(xué)習(xí)函數(shù)模型，其中涵蓋了很多已有的相關(guān)研究成果。Lai et al.(2011)提出了一類(lèi)以已加工工件的加工時(shí)間和加工位置為變量的一般性學(xué)習(xí)函數(shù)模型。Yin et al.(2009)和Lai et al.(2011)研究的函數(shù)工件實(shí)際加工時(shí)間模型仍然部分包含有加法及乘法運(yùn)算。只有少數(shù)的研究(Mosheiov et al.，2003;Mosheiov，2011)包含沒(méi)有任何特殊結(jié)構(gòu)的工件加工時(shí)間函數(shù)模型。

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

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

1 問(wèn)題構(gòu)建和符號(hào)說(shuō)明

基本的模型和所研究問(wèn)題表述如下:

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

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

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

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

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

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

因?yàn)槠叫袡C(jī)的調(diào)度中機(jī)器是同規(guī)格的，所以同一個(gè)工件在不同機(jī)器的相同排序位置上的實(shí)際加工時(shí)間是相同的。在不引起混淆的情形下，令

同(3)式類(lèi)似，當(dāng)工件排在機(jī)器第一個(gè)位置時(shí)，其實(shí)際加工時(shí)間為:

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

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

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

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

2.1 單機(jī)問(wèn)題

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

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

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

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

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

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

算法1

2.2 平行機(jī)問(wèn)題

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

對(duì)于平行機(jī)問(wèn)題pm|prj=fj(pj，r)|TL:prj≤Uj，考慮到 prj≤Uj，構(gòu)建新的工件的實(shí)際加工時(shí)間函數(shù):

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

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

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

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

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

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

算法2

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

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

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

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

計(jì)算出T L(k);

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

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

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

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

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

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

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

算法3

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

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

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

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

3 結(jié)論

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

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

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