工件有工期并且可拒絕單機(jī)最小化最大提前時(shí)間的排序問題

聶 玲， 程 濤

(1.鄭州大學(xué) 數(shù)學(xué)系 河南 鄭州 450001; 2.河南工業(yè)大學(xué) 理學(xué)院 河南 鄭州 450001)

0 引 言

排序問題是一類重要的組合最優(yōu)化問題, 它廣泛應(yīng)用于管理科學(xué)、計(jì)算機(jī)科學(xué)、工農(nóng)業(yè)生產(chǎn)和交通運(yùn)輸?shù)仍S多領(lǐng)域, 一直受到國內(nèi)外學(xué)術(shù)界的重視.

在經(jīng)典排序問題中,總是要求每個(gè)工件必須被加工,并且其加工時(shí)間是預(yù)先給定不變的.然而,在現(xiàn)實(shí)生活中, 由于某些外在的因素,需要拒絕加工某些工件才能滿足限定條件,這就是可拒絕排序[1-5].當(dāng)然,拒絕加工一個(gè)工件需要付出一定的代價(jià),稱之為拒絕費(fèi)用.本文的研究工作就是設(shè)計(jì)一種策略或算法,在原始的某個(gè)和時(shí)間有關(guān)的目標(biāo)函數(shù)(最大完工時(shí)間、總完工時(shí)間、最大提前時(shí)間等) 與拒絕費(fèi)用之間達(dá)到一種協(xié)調(diào),以取得某種意義下的最優(yōu).

1 問題1|nmit|Emax

定理1對于排序問題1|nmit|Emax,STST規(guī)則得到的是最優(yōu)排序.

由定理1可知,按照STST規(guī)則所得的排序是最優(yōu)的,并且它的運(yùn)行時(shí)間為O(n2logn).

2 問題

對于排序問題1nmitEmax,已經(jīng)證明存在一個(gè)最優(yōu)排序，使得工件按照STST規(guī)則在機(jī)器上加工.因此,有引理1.

定義1設(shè)σ為性能指標(biāo)為f和g的雙指標(biāo)排序問題的一個(gè)可行排序,若不存在可行排序π使得f(π)

定義2由所有Pareto最優(yōu)點(diǎn)構(gòu)成的點(diǎn)集所生成的凸包的下沿界稱為有效邊界；有效邊界上的點(diǎn)稱為極點(diǎn)；極點(diǎn)對應(yīng)的排序稱為極序.

一般地,只要確定有效邊界,則可求出目標(biāo)函數(shù)αf+βg(α和β給定)的最小值.而此時(shí),有效邊界為分段線性的凸函數(shù),其中每一個(gè)折點(diǎn)對應(yīng)某一個(gè)Pareto最優(yōu)點(diǎn),即所有的Pareto最優(yōu)點(diǎn)或者恰位于有效邊界上,或者高于此有效邊界.

定理3設(shè)T={Jj∶Ej=E*}，則要使E*變小,只能通過刪去T中的所有工件,并且T={Jk，Jk+1，…,Jl},其中Jk，Jk+1，…，Jl為被接收工件集A中按照STST序最后加工的工件.

證明由引理1，可知被接收工件只有按照STST序加工,才能得到Emax(A)的最小值,即更序無效.

表1 工件參數(shù)表Tab.1 The parameter of jobs

表2 計(jì)算結(jié)果Tab.2 The results of calculations

算法1

Step1:令A(yù)∶=N,R∶=?；

算法2：

Step1:令A(yù)∶=N,R∶=?；

Step2：計(jì)算Emax(A)=maxJj∈A{Ej}；

Step3：記T={Jk∶Ek=Emax,Jk∈A}；

Step4：令A(yù)′∶=AT，計(jì)算Emax(A′)；

3 總結(jié)

本文首次考慮了目標(biāo)函數(shù)為極小化最大提前時(shí)間加上被拒絕工件的拒絕費(fèi)用之和的工件可拒絕的單機(jī)排序問題. 通過對此問題的Pareto最優(yōu)點(diǎn)的分析, 得到多項(xiàng)式時(shí)間可解的算法.

參考文獻(xiàn)：

[1] Brucker P，Gladky A，Hoogeveen H，et al. Scheduling a batching machine[J].Journal of Scheduling,1998,1(1): 31-54.

[2] Bartal Y，Leonardi S，Spaccamela A M，et al. Multiprocessor scheduling with rejection[J]. SIAM Journal on Discrete Mathematics，2000，13(1): 64-78.

[3] Engels D W，Karger D R，Kolliopoulos S G, et al. Techniques for scheduling with rejection[J]. Journal of Algorithms, 2003, 49(1):175-191.

[4] Hoogeveen H. Multicriteria scheduling[J]. European Journal of Operational Research，2005,167(3): 592-623.

[5] Hoogeveen J A，van de Velde S L.Scheduling with target start times[J].European Journal of Operational Research，2001, 129(1): 87-94.

[6] Graham R L, Lawer E L, Lenstra J K, et al. Optimization and approximation in deterministic sequencing and scheduling: a survey[J]. Annals of Discrete Mathematics, 1979,5: 1-15.

[7] 任立莉，李婭，李陽，工件可拒絕平行機(jī)排序[J].鄭州大學(xué)學(xué)報(bào):理學(xué)版，2010,42(3)：15-18.