帶有惡化和拒絕的工期指派的單機排序問題

王曉丹, 趙玉芳, 沈曉飛

(沈陽師范大學 數學與系統科學學院, 沈陽 110034)

帶有惡化和拒絕的工期指派的單機排序問題

王曉丹, 趙玉芳, 沈曉飛

(沈陽師范大學 數學與系統科學學院, 沈陽 110034)

討論帶有惡化和拒絕工件的工期指派的單機排序問題。工件的實際加工時間是其開始加工時間的線性增函數。如果工件被拒絕,則有一個懲罰費用,否則工件被加工。每個工件都要確定一個工期, 文章討論的工期指派分為CON(共同工期指派)和SLK(相同松弛工期指派)兩種情況。對于CON工期指派問題,其目的是確定最優公共工期及工件的加工順序,使工期、提前、延誤和拒絕的總費用最小。將該問題歸結為一系列指派問題,從而得到了一個復雜性為O(n4)的算法來求解此問題。對于SLK工期指派問題,目的是確定最優的松弛量及工件的加工順序,使松弛、提前、延誤和拒絕的總費用最小。將其歸結為一系列指派問題,給出了求解此問題的多項式時間的最優算法。

排序; 惡化工件; CON/SLK工期指派; 拒絕

工期指派的單機排序問題是排序問題的熱點領域。Li等[1]研究了帶有惡化工件的CON/SLK工期指派的單機排序問題。劉洋等[2]研究了具有工期限制的退化工件單機排序問題。在帶有惡化工件的工期指派問題的研究中,對于單機的情況,文獻[3-4]對工期、提前、延誤的總懲罰的問題分別給出了復雜性為O(nlogn)的最優算法;對于平行機的情況,Cheng等[5]研究了工期、提前、延誤的總懲罰問題。Shabtay[6]研究了帶有工期指派的提前、延誤、維修、工期指派和批交貨費用的排序問題。Gordon等[7]研究了加工時間與位置有關的工期指派的單機排序問題。Shabtay等[8]研究了帶有資源分配和最優工期指派的加權誤工任務數的單機排序問題。Zhang等[9]研究了帶有釋放時間和拒絕的單機排序問題。Li等[10]研究了帶有惡化和拒絕工件的平行機排序問題。Shabtay等[11]研究了帶有拒絕和位置懲罰的單機排序問題。Zhang等[12]研究了帶有拒絕的加權總完工時間的平行機排序問題。本文研究同時具有惡化、拒絕和工期指派的排序問題,這種情況在實際生產中經常出現,這個問題的研究在理論和應用上都具有一定的意義。

1 問題描述

給定一個工件集J={J1,J2,…,Jn},所有工件在0時刻可用。工件的加工時間是其開始時間的線性增函數,即工件Jj的實際加工時間為pj=aj+bt,其中aj表示工件Jj的基本加工時間,t表示其開始加工時間,b>0是與工件無關的惡化率。如果工件被拒絕,則有一個懲罰費用ej。每個工件都要確定一個工期dj。工期指派分為CON(共同工期指派)和SLK(相同松弛工期指派)兩種情況。我們的目的是確定公共工期(或松弛量)及工件的加工順序使工期(或松弛)、提前、延誤和拒絕的總費用最小。

對于任意一個給定的排序π,本文涉及的符號表示如下:

Cj表示工件Jj的完工時間;Ej表示工件Jj的提前,即Ej=max{0,dj-Cj};Tj表示工件Jj的延誤,即Tj=max{0,Cj-dj};A表示被接受的工件集;R表示被拒絕的工件集;E表示提前工件集(包含提前和按時完工的工件);T表示誤工工件集;d表示CON工期指派途徑決定的相同工期,即dj=d,j=1,2,…,n;q表示SLK工期指派途徑決定的相同松弛,即dj=pj+q,j=1,2,…,n。

本文研究帶有惡化、拒絕和CON/SLK工期指派的單機排序問題,運用三參數表示法,分別表示為

其中α、β、γ分別表示工期(松弛)、提前、延誤的單位費用,且均大于0。

為了簡便,令J[j]表示排在第j個位置的工件,p[j],a[j],C[j],E[j],T[j]被相應定義。

2 CON工期指派問題

對于本文研究的問題,由于工件的實際加工時間是其開始加工時間的線性增函數,故機器無空閑。當被接受的工件集A中的工件數固定時,運用與Panwalkar等[14]類似的方法可得如下結論:

引理1 在問題1的最優排序中,機器不允許空閑;若排序π中被接受的工件數為m,則π的最優工期為第l個工件的完工時間或0,即d*=C[l]或d*=0(此時l=0),其中

引理2 對于問題1,排序π=(J[1],J[2],…,J[n]),若被接受的工件數|A|=m,提前的工件數|E|=l,則目標函數可表示為

其中

證明 對于任意排序π=(J[1],J[2],…,J[n]),由引理1可知機器沒有空閑,且d=C[l],則有

其中

證畢。

由引理1和引理2可知,一旦接受的工件數固定,則提前的工件數為已知,此時wj與工件的加工順序無關,也就是與排序π無關。故有如下結論:

引理3 在問題1中,若被接受的工件數為m,則該問題可以歸結為指派問題。

證明 若被接受的工件集A中的工件數為m,即|A|=m,則由引理1可知,提前的工件個數為l,將提前工件集E中的工件排在前l個位置,將誤工工件集T中的工件排在中間(m-l)個位置,其余工件放在最后。根據引理2定義

為接受m個工件時,工件Jj指派到第r(r=1,2,…,n)個位置的費用。

引入變量xjr,其值只能為0或1。若工件Jj指派到第r個位置,則xjr=1,否則,xjr=0。則問題可歸結為指派問題如下:

證畢。

由以上分析,對于問題1可得如下算法:

算法1

步驟3 最優的目標值為min{F(m),0≤m≤n}。

我們來分析上述算法的計算復雜性:

定理1 運用算法1求解問題1的時間復雜性為O(n4)。

證明 在算法1中,第1步可以在O(n)時間內得到;第2步中,對于每個被接受的工件數m,需要調用一次指派問題,指派問題的復雜性為O(m3);由于m可以從0取到n,則第2步的復雜性為O(n4);第3步可在O(n)時間內得到。故該算法的時間復雜性為O(n4)。

證畢

3 SLK工期指派問題

當被接受的工件集A中的工件數固定時,運用與Adamopoulos等[15]類似的方法,得如下結論:

引理4 在問題2的最優排序中,機器不允許空閑;若排序π中被接受的工件數為m,則π的最優松弛量q=C[h-1],其中

令π=(J[1],J[2],…,J[n]),若被接受的工件數為m,則由引理4可以確定提前的工件數為h,誤工的工件數為m-h,被拒絕的工件數為n-m,且q=C[h-1]。運用與引理2類似的方法,引用Guo和Yang[13]中的引理2和引理3,可得如下結論:

引理5 對于問題2,排序π=(J[1],J[2],…,J[n]),若被接受的工件數|A|=m,提前的工件數|E|=h,則目標函數可以表示為

其中

引理6 在問題2中,若被接受的工件數為m,則該問題可以歸結為指派問題。

證明 與引理3的證明方法類似,根據引理5定義

為接受m個工件時,工件Jj指派到第r(r=1,2,…,n)個位置的費用。則問題可歸結為指派問題HP1。

證畢。

由以上分析,對于問題2可得如下算法:

算法2

步驟3 最優的目標值為min{F(m),0≤m≤n}。

關于算法2的計算復雜性,與定理1的證明類似,可得如下結論:

定理2 運用算法2求解問題2的時間復雜性為O(n4)。

4 結 論

文章討論了帶有惡化和拒絕工件的工期指派的單機排序問題。工期指派分為CON和SLK兩種情況。目的是確定公共工期(或松弛量)及工件的加工順序,使工期(或松弛)、提前、延誤和拒絕的總費用最小。對于這兩個問題,均將其歸結為一系列指派問題,從而得到復雜性為O(n4)的最優算法。另外,還可以在此基礎上繼續將模型推廣,比如多機問題的情況;也可以考慮將惡化效應,學習效應,拒絕和工期指派等結合在一起,目標函數為工期(或松弛)、提前、延誤和拒絕的總費用的排序問題。

[ 1 ]LI Shisheng, NG C T, YUAN Jinjiang. Scheduling deteriorating jobs with CON/SLK due date assignment on a single machine[J]. Int J Prod Econ, 2011,131(2):747-751.

[ 2 ]劉洋,唐恒永. 具有工期限制的退化工件單機排序問題[J]. 沈陽師范大學學報:自然科學版, 2010,28(3):331-334.

[ 3 ]KUO Wenhung, YANG Darli. A note on due-date assignment and single-machine scheduling with deteriorating jobs[J]. J Oper Res Soc, 2008,59(3):857-859.

[ 4 ]CHENG T C E, KANG L Y, NG C T. Due-date assignment and single machine scheduling with deteriorating jobs[J]. J Oper Res Soc, 2004,55:198-203.

[ 5 ]CHENG T C E, KANG L Y, NG C T. Due-date assignment and parallel-machine scheduling with deteriorating jobs[J]. J Oper Res Soc, 2007,58:1103-1108.

[ 6 ]SHABTAY D. Scheduling and due date assignment to minimize earliness, tardiness, holding, due date assignment and batch delivery costs[J]. Int J Prod Econ, 2010,123(1):235-242.

[ 7 ]GORDON V S, STRUSEVICH V A, Single machine scheduling and due date assignment with positionally dependent processing times[J]. Eur J Oper Res, 2009,198(1):57-62.

[ 8 ]SHABTAY D, STEINER G. Optimal due date assignment and resource allocation to minimize the weighted number of tardy jobs on a single machine[J]. M&SOM-Manuf Serv Op, 2007,9(3):332-350.

[ 9 ]ZHANG Liqi, LU Lingfa, YUAN Jinjiang. Single machine scheduling with release dates and rejection[J]. Eur J Oper Res, 2009,198(3):975-978.

[10]LI Shisheng, YUAN Jinjiang. Parallel-machine scheduling with deteriorating jobs and rejection[J]. Theor Comp Sci, 2010,411(40/41/42):3642-3650.

[11]SHABTAY D, NUFAR G, LIRON Y. A bicriteria approach to scheduling a single machine with job rejection and positional penalties[J]. J Comb Opt, 2012,23(4):395-424.

[12]ZHANG Shuxia, CAO Zhigang, ZHANG Yuzhong. Scheduling with rejection to minimize the total weighted completion time[J]. Oper Res, 2009,8(5):111-114.

[13]KUO Wenhung, YANG Darli. Parallel-machine scheduling with time dependent processing times[J]. Theor Comp Sci, 2008,393(1/2/3):204-210.

[14]PANWALKAR S S, SMITH M L, SEIDMANN A. Common due date assignment to minimize total penalty for the one machine scheduling problem[J]. Oper Res, 1982,30(2):391-399.

[15]ADAMOPOULOS G I, PAPPIS C P. Single machine scheduling with flow allowances[J]. J Oper Res Soc, 1996,47(10):1280-1285.

Schedulingdeterioratingandrejectionjobswithduedateassignmentonasinglemachine

WANG Xiaodan, ZHAO Yufang, SHEN Xiaofei

(School of Mathematics and Systems Science, Shenyang Normal University, Shenyang 110034, China)

The authors consider the scheduling problems with deteriorating jobs, rejection jobs and due date assignment on a single machine. The actual processing times of jobs are a linear increasing function of their start processing times. If the job is rejected, there is a rejection cost, otherwise the job is processed. Every job has a due date. In this paper, we consider two popular due date assignment methods: common due date (CON), equal slack (SLK). For the CON due date assignment method, the problem is to find an optimal due date and the processing sequence simultaneously to minimize the total costs for the common due date assignment, earliness, tardiness and rejection penalties. We reduce the problems to a set of assignment problems which can be solved inO(n4) time. For the SLK due date assignment method, the objective is to find an optimal slack and the processing sequence simultaneously to minimize the total costs for the slack due date assignment, earliness, tardiness and rejection penalties. We reduce the problems to a set of assignment problems, we have shown that the optimal solution can be obtained in polynomial time.

scheduling; deteriorating job; CONSLK due date assignment; rejection

2013-03-29。

遼寧省教育廳高等學?？茖W研究項目(2008z192)。

王曉丹(1989-),女(滿族),遼寧丹東人,沈陽師范大學碩士研究生;

: 趙玉芳(1966-),女,遼寧遼陽人,沈陽師范大學副教授,博士,碩士研究生導師。

1673-5862(2014)02-0182-05

O223

: A

10.3969/ j.issn.1673-5862.2014.02.011

Guo和Yang[13]中的引理2和引理3,