带有恶化和拒绝的工期指派的单机排序问题

王晓丹, 赵玉芳, 沈晓飞

(沈阳师范大学 数学与系统科学学院, 沈阳 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。

辽宁省教育厅高等学校科学研究项目(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,