具有指数学习效应和恶化效应的可拒绝单机排序问题

赵玉芳, 李明泽

(沈阳师范大学 数学与系统科学学院, 沈阳 110034)

具有指数学习效应和恶化效应的可拒绝单机排序问题

赵玉芳, 李明泽

(沈阳师范大学 数学与系统科学学院, 沈阳 110034)

讨论了带有工期窗口的单机排序问题。规定每个被接受的工件都有1个待定的交货期窗口,且所有工件的交货期窗口大小相同。工件的实际加工时间为与其开始时间和位置有关的指数函数。1个工件或者被拒绝,或者被接受。被拒绝就要支付拒绝的费用;被接受就会产生相应的提前、延误惩罚以及最大加工时间的惩罚。研究了2个问题,都需要确定工件的最优排序和窗口的开始时间,第1个问题的目标函数是与窗口的开始时间、窗口的大小、提前时间、延误时间、最大完工时间以及拒绝费用有关的函数。第2个问题的目标函数是与窗口的开始时间、窗口的大小、提前和延误的工件数、最大完工时间以及拒绝费用有关的函数。该问题在多项式时间可解,给出了问题的多项式时间算法。

排序; 单机; 指数学习效应; 交货期窗口; 拒绝

0 引 言

在经典排序理论中,工件的实际加工时间通常没有考虑与工件实际加工位置的关系。然而,在实践过程中,许多工件的加工时间都会随着诸多因素,如:技术工人熟练程度的提高,机器磨合度的增加等而减小,这就是所熟知的学习效应。Biskup[1]首先提出了加工工件具有学习效应的排序问题。Moshevio[2]等扩大了研究范围,考虑了在实际环境中,机器或者工人的学习过程应该是比较缓慢的因素,解释了在生产加工过程中一些工件的学习效应比其他工件学习效应快的可能性。Biskup[3]对加工工件具有学习效应的排排序总是给出了全面的综述。另一种情况是工件的加工时间与其开工时间有关。Cheng等[4]对这一问题的研究给出了综述。有些研究则考虑同时具有学习和恶化两种效应的问题。Lee[5]研究了同时具有学习和恶化效应的排序问题。Yang[6]考虑了具有学习和恶化效应的单机排序问题。Cheng等[7]研究了工件的加工时间为pjr=(aj+bjt)·αr-1的排序问题。这一方面的其他研究还有[8-9]。

近年,有关交货期的排序问题也是备受关注,交货期的问题是指:若某个工件在交货期内完工,则不产生任何惩罚费用,如果工件在窗口之前或者之后完工,则会产生提前或者延误的费用。Saring等[10]研究了具有工期窗口的单机线性排序问题。Zhao等[11]研究了带有学习效应和退化效应的工期窗口排序问题,目标函数是极小化提前、延误、工期和拒绝的惩罚,对不同的问题给出不同的多项式算法。

可拒绝问题指的是:在工件的实际加工过程中,某些工件因为外界和自身的因素可能被拒绝加工,并支付相应的惩罚费用。金亭等[12]研究了带有学习效应和退化效应的可拒绝排序问题,确定被接受工件的最优排序,极小化总费用,证明该问题是多项式时间可解的。Gao等研究了带有拒绝的单机和同型机排序问题,目标为最小化时间表长与惩罚费用之和。

Mosheiov等[14]研究了工件具有多窗口的单机排序问题,目标是确定接受工件集的最优排序,从而极小化2个费用函数。Mosheiov等[15]研究了单机、带有工期窗口,并且带有维修活动的排序问题,目标是极小化与窗口的开始时间、窗口的大小、提前、延误以及拒绝有关的总费用函数。Wang等[16]讨论了单机并且带有学习效应和恶化效应的排序问题,目标函数是极小化最大完工时间。Yin等[17]研究了具有交货期窗口的单机排序问题,并且加工时间可控。Shabtay[18]研究了带有工期指派和资源约束的单机排序问题。文献[19-22]给出了其他相关研究工作。

本文研究带有指数学习效应和恶化效应的可拒绝排序问题。将指数学习效应和恶化效应与多窗口相结合,分别研究了2个总费用函数。第1个函数是与窗口的开始时间、窗口的大小、提前、延误、最大完工时间以及拒绝费用有关的函数;第2个函数是与提前、延误的工件数、窗口的开始时间、窗口的大小、最大完工时间以及拒绝费用有关的函数。证明了该问题在多项式时间可解,并针对2个问题给出多项式时间算法。

1 问题描述

研究单机问题,工件集J={J1,J2,…,Jn}包含n个相互独立的工件。所有工件不允许中断,并且在0时刻均可加工。工件Jj的基本加工时间为pj,其开始时间为t。若Jj排在第r个位置,那么工件Jj的实际加工时间可以表示为

(1)

其中:α为学习指数;bj≥0 为工件的恶化率。

如果工件Jj误工,那么βj就表示误工的惩罚费用。反之被接受,接受工件的总费用包括提前、延误、交货期窗口的开始时间、交货期窗口的大小和工件的最大完工时间的总和。将工件集J划分为接受工件集和拒绝工件集2个不相交的子集,分别用A和R来表示。

因此这2类问题的目标函数分别为

(2)

(3)

其中α,β,γ,δ,θ分别代表提前时间、延误时间、交货期窗口的开始时间、交货期窗口的大小和完工时间的单位费用。

用三参数表示法,本文研究的问题可以记为

问题1:

(4)

问题2:

(5)

2 主要结果

下面将从工件被完全接受以及存在工件被拒绝2个方面讨论。

1) 对于工件全部被接受的特殊情况,即π*=(J[1],J[2],…,J[n]),有如下性质:

性质3 在最优排序π=(J1,J2,…,Jn)中,存在某个k和 l,使得

证明 假设存在1个最优排序S,不具备如上性质。因此设

与Δ1、Δ2有关的目标函数可以化为如下形式:

根据以上性质1～性质4,对于任意给定的排序π=(J[1],J[2],…,J[n])。当Δ1、Δ2趋近于0时,可得

因此,可将目标函数化简如下:

其中,

(11)

(12)

其中Wj=ψjαj-1,j=1,2,…,n

即

根据以上计算过程,给出解法如下:

算法:

步骤 2 根据公式Wj=ψrαr-1,r=1,2,…,n,计算位置权,将工件按照位置权非增的顺序排序,即W1≥W2≥…≥Wn;

步骤3 将工件按照基本加工时间递增的顺序排序,即p[1]≤p[2]≤…≤p[n];

步骤4 将Wj与p[j]逆序相乘,即可得到问题1的最优值。

2) 对于工件中被接受工件个数为h的情况

因为h=0是平凡问题,所以设1≤h

针对问题1,当1≤h

针对接受工件数h

(a)Jj被拒绝

那么在前j-1个工件中,恰好有m个工件被接受,因此,目标函数值为

(b)Jj被接受

那么在前j-1个工件中,恰好有m-1个工件被接受,因此,目标函数值为

由此可得递推公式如下:

因为被接受的工件数为h,故已考虑的被接受的m个工件同剩下的未考虑的(n-j)个工件之和应不少于h,即m≥h-(n-j)。故max(0,h-(n-j))≤m≤min(j,h)。

在以上2种分类的基础上,给出动态规划算法DP如下:

边界条件:

递推式:

对于已经给定的h,目标函数值可以表示如下:

目标函数的最优值F*可以表示如下:

其中:j≤n;m≤h≤n。故上述动态规划算法DP中,j≤n,m≤h≤n,所以动态规划算法DP在O(n2)时间内可解。对于h=1,2,…,n,分别运行算法1,比较所得结果,从中选取最小值,即为问题的最优解。

定理1 问题

存在计算复杂性是O(n3)的最优算法。

3 问题2的讨论

性质5 对于问题(2),存在最优排序π=(J1,J2,…,Jn)满足如下性质:

1) 第1个工件在0时刻开始加工,所有工件都连续加工,且机器无空闲。

3)q(1)的最优值等于C[k*-1],q(2)的最优值,等于C[l*-1],其中:k*≤l*≤n;k*=max{n(δ-γ)/α,0}。

性质6 给定1个排序π=(J1,J2,…,Jn),针对问题(2)其目标函数可以表示为

令

若h

设yrj∈{0,1},若工件Jj排在第r个位置上,则yrj=1,反之yrj=0,化成指派问题如下:

综上所述,对于给定的h,计算所有可能的目标函数值,该指派问题在O(n3)时间内可解。

定理2 问题

存在算法复杂度为O(n5)的最优算法。

4 结 论

本文讨论了带有普通流的交货期窗口问题,工件同时具有指数学习效应和恶化效应并且可拒绝。问题1的目标函数是确定工件的最优排序以及工期窗口的开始时间,极小化与窗口的开始时间、窗口的大小、提前、延误、总加工时间以及拒绝惩罚总费用有关的函数。首先,证明了该问题在多项式内可解;接着,证明了这种计算方法可以拓展到带有拒绝的问题上去,并给出了动态规划算法。问题2的目标函数是与提前、延误的工件数、窗口的开始时间、窗口的大小、总加工时间以及拒绝费用有关的函数。证明了该问题在时间O(n5)内得到最优解。对于其他同时具有指数学习效应和退化效应的带有工期窗口的拒绝模型也是非常有价值的,还有待进一步研究。

[ 1 ]BISKUP D. Single-machine scheduling with learning consideration[J]. European Journal of Operational Research, 1999,115(1):173-178.

[ 2 ]MOSHEIOV G, SIDNEY J B. Scheduling with general job-dependent learning curves[J]. European Journal of Research, 2003,147(3):665-670.

[ 3 ]BISKUP D. A state-of-the-art review on scheduling with learning effects[J]. European Journal of Operational Research, 2008,188:315-329.

[ 4 ]CHENG TCE,DING Q, LIN BM T. A concise survey of scheduling with time-dependent processing times[J]. Eur J Oper Res, 2004,152(1):1-13.

[ 5 ]LEE W C,LAI P J. Scheduling problems with general effects of deterioration and learning[J]. Inform Sci, 2011,181:1164-1170.

[ 6 ]YANG S J,Group scheduling problems with simultaneous considerations of learning and deterioration effects on a single machine[J]. Appl Math Model, 2011,35:4008-4016.

[ 7 ]CHENG Mingbao, SUN Shijie.The single-machine scheduling problems with deteriorating jobs and learning effect[J]. Zhejiang Univ SCIENCE A, 2006,7(4):597-601.

[ 8 ]WU Y B, WANG M Z, WANG J B.Some single-machine scheduling with both learning and deterioration effects[J]. Appl Math Model, 2011,35:3731-3736.

[ 9 ]YANG S J,YANG D L. Minimizing the total completion time in single-machine scheduling with aging/deteriorating effects and deteriorating maintenance activities[J]. Comput Math Appl, 2010,60:2161-2169.

[10]MOSHEIOV G, SARIG A. Scheduling with a common due-window: Polynomially solvable case[J]. Information Sciences, 2010,180:1492-1505.

[11]ZHAO Chuanli, TANG Hengyong. Due-window assignment for a single machine scheduling with both deterioration and positional effects[J]. Asia-Pacific Journal of Operational Research,2015,32(3):1550014.

[12]金亭,赵传立. 带有学习效应和退化效应的可拒绝单机排序问题[J].沈阳师范大学学报(自然科学版), 2015,33(3):358-364.

[13]GAO Q, LU X W. Scheduling on single machine and identical machines with rejection[J]. Operations Research Transactions, 2014,18(4):1-10.

[14]MOSHEIOV G, ORON D. Job-dependent due-window assignment based on a common flow allowance[J]. Foundations of Computing and Decision Sciences, 2010,35(3):185-195.

[15]MOSHEIOV G, SARIG A. Scheduling a maintenance activity and due-window assignment on a single machine[J].Computers & Operations Research, 2009,36(9):2541-2545.

[16]WANG Xiuli, CHENG T C E. Single-machine scheduling with deteriorating jobs and learning effects to minimize the makespan[J]. European Journal of Operational Research, 2007,178(1):57-70.

[17]YIN Yunqiang, CHENG T C E, WU C C, et al. Single-machine due window assignment and scheduling with a common flow allowance and controllable job processing time[J]. Journal of the Operational Research Society, 2014,65(1):1-13.

[18]SHABTAY D, STEINER G. The single-machine earliness-tardiness scheduling problem with due date assignment and resource-dependent processing times[J]. Ann Oper Res, 2008,159(1):25-40.

[19]YANG Shengwu,WAN Long,YIN Na. Research on single machine SLK/DIF due window assignment problem with learning effect and deteriorating jobs[J]. Applied Mathematical Modelling, 2015,39(15):4593-4598.

[20]LI Gang, LUO Meiling, ZHANG Wenjie, et al. Single-machine due-window assignment scheduling based on common flow allowance, learning effect and resource allocation[J]. International Journal of Production Research, 2015,53(4):1228-1241.

[21]WANG Jibo, WANG Mingzheng. Single-machine due-window assignment and scheduling with learning effect and resource-dependent processing times[J]. Asia-Pacific Journal of Operational Research, 2014,31(5):145003.

[22]WANG Jibo, HUANG Xue, WANG Xiaoyuan,et al. Learning effect and deteriorating jobs in the single machine scheduling problems[J]. Applied Mathematical Modelling, 2009,33(10):3848-3853.

Single-machine scheduling problems with rejection and both learning effect and deteriorating jobs

ZHAOYufang,LIMingze

(College of Mathematic and Systems science, Shenyang Normal University, Shenyang 110034, China)

This paper studies the single machine scheduling and due-window assignment problems with learning effect and deteriorating jobs. We assume that the jobs have multiple due windows. And all the due windows have the same size. The processing time of job are defined as functions of their start times and position in a sequence. A job will be rejected, or be accepted. The job which is refused have to pay the cost of the rejected. Jobs completed within the window incur no penalties, other jobs incur either earliness or tardiness penalties. The window location and size, along with the associated job schedule are to be determined to minimizes a certain cost function. The first function is made up of costs associated with the window location, window size, earliness, and tardiness and the makespan costs. The second function is made up of costs associated with the window location, window size, the number of earliness and tardiness jobs and makespan costs. We introduce a polynomial time algorithm for the problem.

scheduling; single machine; learning effect; due-window assignment; rejected

2016-10-12。

辽宁省教育厅科学研究一般项目(L2014433)。

赵玉芳(1966-),女,辽宁辽阳人,沈阳师范大学副教授,博士。

1673-5862(2017)01-0047-08

O223

A

10.3969/ j.issn.1673-5862.2017.01.009

运筹学与控制论