謝 謝,孔祥玉,鄭勇躍

(1.沈陽(yáng)大學(xué) 裝備制造綜合自動(dòng)化重點(diǎn)實(shí)驗(yàn)室,遼寧 沈陽(yáng) 110044;2.遼寧省標(biāo)準(zhǔn)化研究院,遼寧 沈陽(yáng) 110004)

大多數(shù)的調(diào)度問(wèn)題都是在經(jīng)典調(diào)度模型的基礎(chǔ)上進(jìn)行研究的,如文獻(xiàn)[1],工件的拒絕是不允許的.但有時(shí)會(huì)因?yàn)樵牧系南拗剖沟萌藗儾坏貌痪芙^某些工件的加工,或者一些生產(chǎn)商為了獲得更大的利潤(rùn),會(huì)選擇拒絕一些由于加工時(shí)間較長(zhǎng)而帶來(lái)整體效益減少的工件.無(wú)論出于何種原因拒絕工件的加工,支付一定的懲罰是必不可少的.針對(duì)不可用區(qū)間的約束經(jīng)常在生產(chǎn)企業(yè)出現(xiàn),產(chǎn)生的原因主要分為兩大類(lèi)型:第一種是確定性的不可用,即由于機(jī)器的維護(hù)保養(yǎng)帶來(lái)的一段確定的時(shí)間內(nèi)機(jī)器不能加工任何工件;第二種是隨機(jī)性的不可用,即由于機(jī)器意外破損導(dǎo)致的機(jī)器在一段時(shí)間內(nèi)不能加工任何工件,出現(xiàn)這種情況時(shí),調(diào)度人員不能事先預(yù)知不可用具體在哪一時(shí)段發(fā)生.無(wú)論是由于何種原因帶來(lái)的不可用,都要做好準(zhǔn)備,避免由于停工帶來(lái)的利益損失.本文將加工機(jī)器具有不可用區(qū)間、工件可拒絕的約束集成考慮,最小化可接受加工工件的最大完工時(shí)間與拒絕工件的懲罰之和.

Adiri等[2]首次研究了帶有不可用區(qū)間的單機(jī)調(diào)度問(wèn)題,分別針對(duì)具有確定性的不可用區(qū)間和隨機(jī)性的不可用區(qū)間兩種情況進(jìn)行了研究,目標(biāo)是最小化工件的完工時(shí)間和.Lee和Liman[3]與Adiri等[2]考慮了同樣的問(wèn)題,并證明了帶有確定不可用區(qū)間的該問(wèn)題是NP-難的,提出了啟發(fā)式算法并給出了緊界.Ng和Kovalyov[4]研究了二機(jī)流水作業(yè)帶有一個(gè)確定的不可用區(qū)間的問(wèn)題,分別針對(duì)不可用區(qū)間在第一臺(tái)機(jī)器上產(chǎn)生和在第二臺(tái)機(jī)器上產(chǎn)生提出了啟發(fā)式算法,并提出了全多項(xiàng)式時(shí)間近似方案(FPTAS).Lee[5]研究了帶有不可用區(qū)間的平行機(jī)調(diào)度問(wèn)題,目標(biāo)是最小化加工工件的完工時(shí)間,應(yīng)用LPT算法求解了此問(wèn)題,證明了該算法的最壞性能比為3/2,并進(jìn)一步修改了該LPT算法,證明了它的最壞性能比是4/3.Lee和Liman[6]研究了兩臺(tái)機(jī)器的平行機(jī)調(diào)度問(wèn)題,其中一臺(tái)機(jī)器上帶不可用區(qū)間,提出了動(dòng)態(tài)規(guī)劃算法并給出了問(wèn)題的最優(yōu)解.Lee[7]研究了二機(jī)流水作業(yè)帶不可用區(qū)間的調(diào)度問(wèn)題,分別針對(duì)不可用區(qū)間在第一臺(tái)機(jī)器和第二臺(tái)機(jī)器上兩種情況作出了分析,分別給出了啟發(fā)式算法和動(dòng)態(tài)規(guī)劃算法.

工件可拒絕的調(diào)度問(wèn)題是由Bartal等[8]首次提出的,主要針對(duì)混合機(jī)帶有工件加工可拒絕的調(diào)度問(wèn)題,目標(biāo)是最小化接受工件的時(shí)間表長(zhǎng)與拒絕工件的懲罰之和.Hoogeveen等[9]研究了工件加工可拒絕的平行機(jī)(同類(lèi)機(jī)、同速機(jī)、變速機(jī))調(diào)度問(wèn)題,提出了一個(gè)1.58-因子算法.Dósa和He[10]研究了機(jī)器花費(fèi)且?guī)в芯芙^工件的問(wèn)題,在他們的模型中,一開(kāi)始沒(méi)有一個(gè)確定的機(jī)器花費(fèi),只有當(dāng)購(gòu)買(mǎi)新機(jī)器時(shí)這種花費(fèi)才可以確定.

1 問(wèn)題參數(shù)及描述

2 動(dòng)態(tài)規(guī)劃算法

對(duì)于工件Jj,存在三種情況:工件Jj被拒絕;工件Jj接受加工并且在T1前加工完成;工件Jj接受加工并且在T2后加工完成.

情況1 若Jj被拒絕,則有下式成立:

情況2 若Jj接受加工且在T1前加工完成,則有下式成立:

情況3 若Jj接受加工且在T2后加工完成,則有下式成立:

綜合上述3種情況,給出如下動(dòng)態(tài)規(guī)劃算法.

(1) 邊界條件:當(dāng)j=1時(shí)

(2) 動(dòng)態(tài)規(guī)劃遞推函數(shù):當(dāng)j=2,…,n時(shí)

其中各參數(shù)滿(mǎn)足如下條件:

其中,JA是最初應(yīng)用Johnson算法排序的目標(biāo)值.

此動(dòng)態(tài)規(guī)劃算法是在所有參數(shù)的取值范圍內(nèi)求得問(wèn)題的最優(yōu)解.下面給出數(shù)值實(shí)例并應(yīng)用動(dòng)態(tài)規(guī)劃的迭代過(guò)程得到問(wèn)題的最優(yōu)解.

給定工件的個(gè)數(shù)n=4,不可用區(qū)間[T1,T2]=[3,4],各工件分別在M1和M2上的加工時(shí)間與懲罰值如表1所示.

表1 各工件分別在M1和M2上的加工時(shí)間與懲罰值Table 1 Processing time and penalty value of each workpiece on M1 and M2

表2 相應(yīng)的各參數(shù)Table 2 Corresponding parameters

按照工件的個(gè)數(shù)劃分為四個(gè)階段,k=1,2,3,4.

(1) 第一次迭代,即當(dāng)k=1時(shí),分為四大類(lèi)情況.

① 考慮工件J1是接受加工還是拒絕加工.因?yàn)閜11=1

=1,

所以工件J1被拒絕加工.

② 考慮工件J2是接受加工還是拒絕加工.因?yàn)閜12=2

=4.

所以工件J2接受加工.

③ 考慮工件J3是接受加工還是拒絕加工.因?yàn)閜13=4>T1=3,工件J3在T2后完工,有

=4.

所以工件J3拒絕加工.

④ 考慮工件J4是接受加工還是拒絕加工.因?yàn)閜14=2

=3.

所以接受工件J4.

(2) 第二次迭代,即當(dāng)k=2時(shí),在前一階段工件J1被拒絕的情況下,考慮剩余3個(gè)工件是接受加工還是拒絕加工,有

此時(shí)工件J2接受加工,J3拒絕加工,J4接受加工.

同理,在工件J2接受加工的情況下,考慮工件J1,J3,J4的加工情況,有

所以拒絕J1加工,拒絕J3加工,接受J4加工.

根據(jù)以上分析過(guò)程,依次考慮當(dāng)J3拒絕加工和J4接受加工時(shí)其余工件的加工情況.當(dāng)J3拒絕加工時(shí),其余工件的加工情況為:工件J1拒絕加工,目標(biāo)值為5;工件J2接受加工,目標(biāo)值為9;工件J4接受加工,目標(biāo)值為7.當(dāng)J4接受加工時(shí),其余工件的加工情況為:工件J1拒絕加工,其目標(biāo)值為4;工件J2接受加工,其目標(biāo)值為7;工件J3拒絕加工,其目標(biāo)值為8.

(3) 第三次迭代,即當(dāng)k=3時(shí),分為四大類(lèi)情況.

① 當(dāng)?shù)谝浑A段工件J1拒絕且第二階段工件J2被接受時(shí),有

所以拒絕工件J3,其目標(biāo)值為9;接受工件J4,其目標(biāo)值為7.

依據(jù)上述分析過(guò)程,當(dāng)?shù)诙A段工件J3拒絕加工時(shí),接受工件J2,其目標(biāo)值為9;接受工件J4,其目標(biāo)值為8.當(dāng)?shù)诙A段接受工件J4時(shí),接受工件J2,其目標(biāo)值為8;拒絕工件J3,其目標(biāo)值為8.

② 當(dāng)?shù)谝浑A段工件J2接受加工且第二階段工件J1拒絕加工時(shí),在第三階段拒絕工件J3,其目標(biāo)值為9;接受工件J4,其目標(biāo)值為7.當(dāng)?shù)谝浑A段工件J2接受加工且第二階段工件J3拒絕加工時(shí),在第三階段拒絕工件J1,其目標(biāo)值為9;接受工件J4,其目標(biāo)值為10.當(dāng)?shù)谝浑A段工件J2接受加工且第二階段接受工件J4加工時(shí),在第三階段拒絕工件J1,其目標(biāo)值為7;拒絕工件J3,其目標(biāo)值為10.

③ 當(dāng)?shù)谝浑A段工件J3拒絕加工且第二階段工件J1拒絕加工時(shí),在第三階段接受工件J2,其目標(biāo)值為9;接受工件J4,其目標(biāo)值為10.當(dāng)?shù)谝浑A段工件J3拒絕加工且第二階段接受工件J2加工時(shí),在第三階段拒絕工件J1,其目標(biāo)值為9;接受工件J4,其目標(biāo)值為10.當(dāng)?shù)谝浑A段工件J3拒絕加工且第二階段接受工件J4加工時(shí),在第三階段拒絕工件J1,其目標(biāo)值為5;接受工件J2,其目標(biāo)值為11.

④ 當(dāng)?shù)谝浑A段工件J4接受加工且第二階段工件J1拒絕加工時(shí),在第三階段接受工件J2,其目標(biāo)值為8;拒絕工件J3,其目標(biāo)值為8.當(dāng)?shù)谝浑A段工件J4接受加工且第二階段接受工件J2加工時(shí),在第三階段拒絕工件J1,其目標(biāo)值為8;接受工件J3,其目標(biāo)值為11.當(dāng)?shù)谝浑A段工件J4接受加工且第二階段拒絕工件J3加工時(shí),在第三階段拒絕工件J1,其目標(biāo)值為9;接受工件J2,其目標(biāo)值為11.

(4) 第四次迭代,即當(dāng)k=4時(shí),當(dāng)?shù)谝浑A段拒絕J1、第二階段接受J2、第三階段拒絕J3、第四階段需考慮是否加工J4時(shí),有

=11,

所以接受工件J4加工.

圖1 數(shù)值實(shí)例的動(dòng)態(tài)規(guī)劃示意圖Fig.1 Dynamic programming schematic of numerical example

綜上所述,最優(yōu)解為拒絕工件J1,J3,接受工件J2,J4,并按此順序依次在機(jī)器上加工,且最優(yōu)值為11.

由于動(dòng)態(tài)規(guī)劃算法可以在短時(shí)間內(nèi)求解小規(guī)模問(wèn)題,并得到最優(yōu)值,隨著問(wèn)題規(guī)模的增大,計(jì)算時(shí)間成指數(shù)增長(zhǎng),因此,為了克服動(dòng)態(tài)規(guī)劃算法的缺陷,本文提出了一個(gè)多項(xiàng)式時(shí)間內(nèi)可解的啟發(fā)式算法并對(duì)它的最壞性能進(jìn)行了分析.

3 啟發(fā)式算法及其性能分析

第1步 首先使用Johnson算法對(duì)所有的工件進(jìn)行調(diào)度,相應(yīng)的調(diào)度記為σ1,并計(jì)算調(diào)度目標(biāo)值為Cmax(σ1).

第3步 按照第2步的加工順序加工工件,將Jk放在第一位加工,相應(yīng)的調(diào)度記為σ3,目標(biāo)值記為Cmax(σ3).

第4步 選擇已得到的目標(biāo)值Cmax(σ1),Cmax(σ2),Cmax(σ3)中最小的,將其調(diào)度記為σH.

證明 由于

4 結(jié) 語(yǔ)

本文研究的是二機(jī)流水作業(yè)帶有不可用區(qū)間、工件可拒絕的問(wèn)題,該問(wèn)題已證明是NP-難的.首先提出了動(dòng)態(tài)規(guī)劃算法以求解小規(guī)模問(wèn)題的最優(yōu)解,隨著問(wèn)題規(guī)模的擴(kuò)大,算法的運(yùn)算時(shí)間變長(zhǎng),為了克服動(dòng)態(tài)規(guī)劃在計(jì)算時(shí)間上的缺陷,進(jìn)一步提出了一個(gè)啟發(fā)式算法以獲得近似解.通過(guò)最壞性能分析可知,算法的性能比是3.未來(lái)的研究將進(jìn)一步對(duì)具有更多相關(guān)約束的實(shí)際問(wèn)題提出多項(xiàng)式時(shí)間內(nèi)可解的近似策略,并將研究推廣到多臺(tái)機(jī)器具有類(lèi)似約束的問(wèn)題.

參考文獻(xiàn):

[1] 謝謝,李彥平.帶有單服務(wù)器的并行機(jī)調(diào)度問(wèn)題[J].沈陽(yáng)大學(xué)學(xué)報(bào):自然科學(xué)版,2012,24(4):66-69.

(Xie Xie,Li Yanping.Scheduling Parallel Machines with a Single Server[J].Journal of Shenyang University: Natural Science,2012,24(4):66-69.)

[2] Adiri I,Bruno J,Frostig E,et al.Single Machine Flow-Time Scheduling with a Single Breakdown[J].Acta Informatica,1989,26(7):679-696.

[3] Lee C Y,Liman S D.Single Machine Flow-Time Scheduling with Scheduled Maintenance[J].Acta Informatica,1992,29(4):375-382.

[4] Ng C T,Kovalyov M Y.An FPTAS for Scheduling a Two-Machine Flowshop with One Unavailability Interval[J].Naval Research Logistics,2004,51(3):307-315.

[5] Lee C Y.Parallel Machine Scheduling with Non-Simultaneous Machine Available Time[J].Discrete Applied Mathematics,1991,30(1):53-61.

[6] Lee C Y,Liman S D.Capacitated Two-Parallel Machine Scheduling to Minimize Sum of Job Completion Times[J].Discrete Applied Mathematics,1993,41(3):211-222.

[7] Lee C Y.Minimizing the Makespan in the Two-Machine Flowshop Scheduling Problem with an Availability Constraint[J].Operations Research Letters,1997,20(3):129-139.

[8] Bartal Y,Leonardi S,Spaccamela A M,et al.Multiprocessor Scheduling with Rejection[J].SIAM Journal on Discrete Mathematics,2000,13(1):64-78.

[9] Hoogeveen H,Skutella M,Woeginger G J.Preemptive Scheduling with Rejection[J].Mathematics Programming,2003,94(2/3):361-374.

[10] Dósa G,He Yong.Scheduling with Machine Cost and Rejection[J].Journal of Combinatorial Optimization,2006,12(4):337-350.