二機流水作業(yè)帶不可用區(qū)間、工件可拒絕的調(diào)度問題

謝 謝,孔祥玉,鄭勇躍

(1.沈陽大學(xué) 裝備制造綜合自動化重點實驗室,遼寧 沈陽 110044;2.遼寧省標準化研究院,遼寧 沈陽 110004)

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

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

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

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

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

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

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

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

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

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

(1) 邊界條件:當j=1時

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

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

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

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

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

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

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

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

(1) 第一次迭代,即當k=1時,分為四大類情況.

① 考慮工件J1是接受加工還是拒絕加工.因為p11=1

=1,

所以工件J1被拒絕加工.

② 考慮工件J2是接受加工還是拒絕加工.因為p12=2

=4.

所以工件J2接受加工.

③ 考慮工件J3是接受加工還是拒絕加工.因為p13=4>T1=3,工件J3在T2后完工,有

=4.

所以工件J3拒絕加工.

④ 考慮工件J4是接受加工還是拒絕加工.因為p14=2

=3.

所以接受工件J4.

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

此時工件J2接受加工,J3拒絕加工,J4接受加工.

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

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

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

(3) 第三次迭代,即當k=3時,分為四大類情況.

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

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

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

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

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

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

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

=11,

所以接受工件J4加工.

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

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

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

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

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

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

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

證明 由于

4 結(jié) 語

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

參考文獻:

[1] 謝謝,李彥平.帶有單服務(wù)器的并行機調(diào)度問題[J].沈陽大學(xué)學(xué)報:自然科學(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.