王曉丹, 趙玉芳, 沈曉飛

(沈陽(yáng)師范大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院, 沈陽(yáng) 110034)

帶有惡化和拒絕的工期指派的單機(jī)排序問(wèn)題

王曉丹, 趙玉芳, 沈曉飛

(沈陽(yáng)師范大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院, 沈陽(yáng) 110034)

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

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

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

1 問(wèn)題描述

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

對(duì)于任意一個(gè)給定的排序π,本文涉及的符號(hào)表示如下:

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

本文研究帶有惡化、拒絕和CON/SLK工期指派的單機(jī)排序問(wèn)題,運(yùn)用三參數(shù)表示法,分別表示為

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

為了簡(jiǎn)便,令J[j]表示排在第j個(gè)位置的工件,p[j],a[j],C[j],E[j],T[j]被相應(yīng)定義。

2 CON工期指派問(wèn)題

對(duì)于本文研究的問(wèn)題,由于工件的實(shí)際加工時(shí)間是其開(kāi)始加工時(shí)間的線性增函數(shù),故機(jī)器無(wú)空閑。當(dāng)被接受的工件集A中的工件數(shù)固定時(shí),運(yùn)用與Panwalkar等[14]類似的方法可得如下結(jié)論:

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

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

其中

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

其中

證畢。

由引理1和引理2可知,一旦接受的工件數(shù)固定,則提前的工件數(shù)為已知,此時(shí)wj與工件的加工順序無(wú)關(guān),也就是與排序π無(wú)關(guān)。故有如下結(jié)論:

引理3 在問(wèn)題1中,若被接受的工件數(shù)為m,則該問(wèn)題可以歸結(jié)為指派問(wèn)題。

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

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

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

證畢。

由以上分析,對(duì)于問(wèn)題1可得如下算法:

算法1

步驟3 最優(yōu)的目標(biāo)值為min{F(m),0≤m≤n}。

我們來(lái)分析上述算法的計(jì)算復(fù)雜性:

定理1 運(yùn)用算法1求解問(wèn)題1的時(shí)間復(fù)雜性為O(n4)。

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

證畢

3 SLK工期指派問(wèn)題

當(dāng)被接受的工件集A中的工件數(shù)固定時(shí),運(yùn)用與Adamopoulos等[15]類似的方法,得如下結(jié)論:

引理4 在問(wèn)題2的最優(yōu)排序中,機(jī)器不允許空閑;若排序π中被接受的工件數(shù)為m,則π的最優(yōu)松弛量q=C[h-1],其中

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

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

其中

引理6 在問(wèn)題2中,若被接受的工件數(shù)為m,則該問(wèn)題可以歸結(jié)為指派問(wèn)題。

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

為接受m個(gè)工件時(shí),工件Jj指派到第r(r=1,2,…,n)個(gè)位置的費(fèi)用。則問(wèn)題可歸結(jié)為指派問(wèn)題HP1。

證畢。

由以上分析,對(duì)于問(wèn)題2可得如下算法:

算法2

步驟3 最優(yōu)的目標(biāo)值為min{F(m),0≤m≤n}。

關(guān)于算法2的計(jì)算復(fù)雜性,與定理1的證明類似,可得如下結(jié)論:

定理2 運(yùn)用算法2求解問(wèn)題2的時(shí)間復(fù)雜性為O(n4)。

4 結(jié) 論

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

[ 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ī)排序問(wèn)題[J]. 沈陽(yáng)師范大學(xué)學(xué)報(bào):自然科學(xué)版, 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。

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

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

: 趙玉芳(1966-),女,遼寧遼陽(yáng)人,沈陽(yáng)師范大學(xué)副教授,博士,碩士研究生導(dǎo)師。

1673-5862(2014)02-0182-05

O223

: A

10.3969/ j.issn.1673-5862.2014.02.011

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