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

聶 玲， 程 濤

(1.鄭州大學 數學系 河南 鄭州 450001; 2.河南工業大學 理學院 河南 鄭州 450001)

0 引 言

排序問題是一類重要的組合最優化問題, 它廣泛應用于管理科學、計算機科學、工農業生產和交通運輸等許多領域, 一直受到國內外學術界的重視.

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

1 問題1|nmit|Emax

定理1對于排序問題1|nmit|Emax,STST規則得到的是最優排序.

由定理1可知,按照STST規則所得的排序是最優的,并且它的運行時間為O(n2logn).

2 問題

對于排序問題1nmitEmax,已經證明存在一個最優排序，使得工件按照STST規則在機器上加工.因此,有引理1.

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

定義2由所有Pareto最優點構成的點集所生成的凸包的下沿界稱為有效邊界；有效邊界上的點稱為極點；極點對應的排序稱為極序.

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

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

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

表1 工件參數表Tab.1 The parameter of jobs

表2 計算結果Tab.2 The results of calculations

算法1

Step1:令A∶=N,R∶=?；

算法2：

Step1:令A∶=N,R∶=?；

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

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

Step4：令A′∶=AT，計算Emax(A′)；

3 總結

本文首次考慮了目標函數為極小化最大提前時間加上被拒絕工件的拒絕費用之和的工件可拒絕的單機排序問題. 通過對此問題的Pareto最優點的分析, 得到多項式時間可解的算法.

參考文獻：

[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].鄭州大學學報:理學版，2010,42(3)：15-18.