加工时间可控的单机排序问题

高 洁, 赵玉芳

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

加工时间可控的单机排序问题

高 洁, 赵玉芳

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

研究带有学习效应和恶化效应的单机排序问题。在此模型中,工件的学习效应是与工件加工位置相关的减函数,工件的恶化效应是与其开始加工时间相关的线性函数。在无资源约束的情况下,分别讨论了目标函数为最大完工时间、总完工时间及总完工时间的绝对差之和的排序问题,证明了这些问题都是多项式时间可解的。对于带有资源约束问题,若分配一定的资源,工件加工时间会减少。讨论了在线性资源分配情况下,带有学习效应、恶化效应和资源分配量的交货期排序问题,其中所有工件有一个共同的交货期。目的是确定最优交货期、资源分配及工件的加工顺序,使交货期、提前、延误和资源分配量之和最小,通过将其转化为指派问题,证明问题是多项式时间可解的。

排序; 学习效应; 恶化效应; 资源分配; 指派问题

0 引 言

近年来,带有学习效应和恶化效应的排序问题受到了广泛的关注。Lee[1]首先研究了单机带有学习和恶化效应的排序问题,分别提出实际加工时间为pir=αitra和pir=(p0+αit)ra的排序问题,其中αi0,表示工件的恶化效应;t表示工件的开始加工时间;a≤0表示工件的学习效应;r表示工件的实际加工位置;p0表示工件的基本加工时间,证明了最大完工时间和总完工时间是多项式时间可解的。Wang[2]研究了实际加工时间是与工件位置和开始加工时间有关的带有学习效应和恶化效应的模型pjr=pj(α(t)+βra),其中pj表示工件的基本加工时间,给出了最大完工时间和总完工时间的多项式时间最优算法。Wang等[3]研究了实际加工时间为pir=αi(b+ct)ra的单机排序问题,给出了最大完工时间,总完工时间和加权总完工时间的多项式时间的最优算法。Zhang[4]对加工时间是与工件加工位置相关的指数函数,给出了总完工时间的多项式时间算法。Yang等[5]研究了单机和流水作业加工时间为pir=pirb+αt的排序问题,其中b≤0,给出了最大完工时间和总完工时间的多项式时间最优算法。Gordon等[6]对加工时间与开始时间及位置相关的单机排序问题进行了综述。Yang[7]研究了在带有恶化维修情况下加工时间为pir=(pi+λt)ra的单机排序问题,证明了最大完工时间和总完工时间是多项式时间可解的。文献[8-10]研究了带有恶化的单机排序问题。交货期排序问题也是排序问题中非常重要的问题。

交货期排序问题也是排序问题中非常重要的问题,工件在其交货期前完工需被储存,将花费一定的储存费用;在其交货期后完工将引发惩罚。Panwalkar等[11]对共同交货期提前与延误惩罚函数进行研究,得到了共同交货期惩罚函数的重要结论,即工件的共同交货期为某个工件的完工时间,且按时完工的工件个数只与惩罚系数和工件的总数有关,而与工件本身无关。对于具有可控加工时间的交货期指派问题也已被广泛研究。Ventur等[12]研究了工件的释放时间是依赖资源的单机共同交货期指派问题,并给出了其拟多项式时间动态规划算法。Ng等[9]研究了工件的加工时间是资源分配量的线性非增函数,并给出共同交货期与资源分配之和的多项式时间算法。Yin等[13]研究了加工时间依赖资源的单机交货期窗口问题,给出了资源分配及工件的加工顺序,使交货期、提前、延误和资源分配之和的多项式时间算法。Yin等[14]研究了带有可控加工时间和学习效应的单机排序问题,目标函数是最小化时间表长、总的完工时间、总的完工时间的绝对差和总的压缩费用。通过将问题转化为指派问题,证明了这个问题是多项式时间可解的。郭玲和赵传立[15]研究了退化维修情况下,带有三种交货期指派和加工时间可控的单机排序问题,证明了当维修固定时,问题可转化为指派问题,得到O(n3)的多项式时间最优算法。

本文研究同时带有与工件位置相关的学习效应和与工件开始时间相关的恶化效应的单机排序问题。工件的加工实际时间是与工件基本加工时间,工件的加工位置及工件的开始加工时间相关的函数。本文首先对于无资源约束的问题,讨论了工件的学习效应是以工件加工位置为指数的减函数,工件的恶化效应是其开始加工时间的线性函数,目标函数分别为最大完工时间、总完工时间及总完工时间的绝对差之和的单机排序问题。随后,对于带有资源约束问题,讨论了在线性资源分配情况下,带有学习效应、恶化效应和资源分配的交货期排序问题,目的是确定最优交货期、资源分配及工件的加工顺序,使交货期、提前、延误和资源分配之和最小。

1 问题描述

给定n个独立的工件,记为J={J1,J2,…,Jn}。工件的实际加工时间可表示为pjr=pjar-1+bt,其中pj表示工件Jj的基本加工时间;b表示工件的恶化系数,且b0;t表示工件的开始加工时间;ar-1表示与位置相关学习效应模型,其中:0

不失一般性,对于任意一个给定的排序π,本文涉及的符号表示如下:

本文研究带有学习效应和恶化效应的单机排序问题。对于无资源约束的问题,讨论了工件的学习效应是以工件加工位置为指数的减函数,工件的恶化效应是其开始加工时间的线性函数,目标函数分别为最大完工时间、总完工时间及总完工时间的绝对差之和的单机排序问题。对于带有资源约束问题,讨论了在线性资源分配情况下,带有学习效应、恶化效应和资源分配的交货期排序问题,目的是确定最优交货期、资源分配及工件的加工顺序,使交货期、提前、延误和资源分配之和最小。

运用三参数表示法,问题分别表示为

2 相关结论

2.1最大完工时间

为了解决最大完工时间问题,首先必须知道工件的实际加工时间。不失一般性,令p[r]表示第r个位置上工件的基本加工时间,p[1]1表示第一个位置工件的实际加工时间表示,即p[1]1=p[1]ar-1+b×0=p[1];第一个工件的完工时间为C[1],C[1]=p[1]。类似地,有

第i个工件Ji的加工时间及完工时间可转化为:

引理1 在最优排序的加工过程中,任意2个工件之间没有空闲,且第1个工件的开始加工时间为零。

证明 由式(1)工件的总完工时间为C[n],

2.2总完工时间和TADC

证明

证明 TADC表示工件完工时间的绝对差之和,

2.3与资源相关的交货期排序问题

本节讨论线性资源分配情况下,带有学习效应、恶化效应和资源分配的交货期排序问题,目的是确定最优共同交货期,资源分配及工件的加工顺序,使共同交货期、提前、延误和资源分配量之和最小。

引理2[8]在共同交货期指派问题的一个最优排序π中,工件的最优交货期为第l*个工件的完工时间或0,即d*=C[l*]或d*=0(此时l*=0),其中

由式(2)可知,l*只与提前,延误惩罚的系数有关,与工件的加工时间和加工顺序无关。那么对于任意资源分配u及工件的排序π,有

由式(3)～式(6)可知带有资源分配的共同交货期指派的目标函数可转化为:

由上式工件的实际加工时间可知,问题的目标函数可转化为

证明 由式(7)可知,问题可转化为指派问题

其中

3 实 例

解p[1]1表示第1个位置工件的实际加工时间表示,即p[1]1=p[1]ar-1+b×0=p[1];第1个工件的完工时间为C[1],C[1]=p[1]。

4 结 语

在实际生产过程,工件很可能带有学习效应和恶化效应,因此在理论研究中带有重要意义。本文研究了同时带有学习效应和恶化效应的单机排序问题,给出了求解工件的最大完工时间和工件的总完工时间时间复杂性为O(nlogn)的多项式时间算法。并将工件的加工时间与线性资源分配结合在一起,目的是确定最优交货期,资源分配及工件的加工顺序,使交货期、提前、延误和资源分配之和最小,并将问题转化为指派问题,给出了带有资源的交货期指派问题时间复杂性为O(n3)的多项式时间算法。

[ 1 ]LEE W C. A note on deteriorating jobs and learning in single-machine scheduling problems[J]. Int J Business Econ, 2004,3(1):83-89.

[ 2 ]WANG Jibo. Single-machine scheduling problems with the effects of learning and deterioration[J]. Omega, 2007,35(4):397-402.

[ 3 ]WANG Jibo, CHENG T C E. Scheduling problems with the effects of deterioration and learning[J]. Asia-Pac J Oper Res, 2007,24(2):245-261.

[ 4 ]ZHANG Xingong, YAN Guangle, HUANG Wanzhen, et al. Single-machine scheduling problems with time and position dependent processing times[J]. Ann Oper Res,2011,186(1):345-356.

[ 5 ]YANG D L, KUO W C. Some scheduling problems with deteriorating jobs and learning effects[J]. Comput Ind Eng, 2010,58(1):25-28.

[ 6 ]GORDON V S, Potts C N, STRUSEVICH V A, et al. Single machine scheduling models with deterioration and learning: handling precedence constraints via priority generation[J]. J Schedul, 2008,11(5):357-370.

[ 7 ]YANG S J. Single-machine scheduling problems simultaneously with deterioration and learning effects under deteriorating multi-maintenance activities consideration[J]. Comput Ind Eng, 2012,62(1):271-275.

[ 8 ]王吉波,刘璐,许扬韬,等. 具有恶化工件的不同交货期指派问题研究[J].沈阳航空航天大学学报,2013,30(5):83-87.

[ 9 ]王吉波,刘璐. 带准备时间的任务单机学习效应排序问题[J]. 大连理工大学学报, 2013,53(6):930-936.

[10]王吉波,王建军,何平. 具有共同松弛时间的恶化型工件排序问题研究[J]. 大连理工大学学报, 2012,52(6):932-936.

[11]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.

[12]VENTURA J A, KIM D, GARRIGA F.Single machine earliness-tardiness scheduling with resourcedependent release dates[J]. Eur J Oper Res, 2002,142(1):52-69.

[13]YIN Yongqiang, 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]. J Oper Res Soc, 2013,65(1):1-13.

[14]YIN Na, WANG Xiaoyuan. Single-machine scheduling with controllable processing times and learning effect[J]. Int J Adv Manu Tech, 2011,54(5/6/7/8):743-748.

[15]郭玲,赵传立. 在退化维修下带有交货期指派和加工时间可控的单机排序问题[J]. 沈阳师范大学学报: 自然科学版, 2013,31(3):341-347.

Singlemachineschedulingproblemwithcontrollableprocessingtimes

GAOJie,ZHAOYufang

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

This paper considers some single-machine scheduling problems of jobs with learning and deteriorating effects. In the model, the actual processing time of a job is a decreasing function of its position due to learning effects. The actual processing time of a job is a linear function of its starting time due to deteriorating effects. For the problems without resource allocation, we consider the problems of the makespan, the total completion times and total absolute differences in completion times, respectively. We show that these problems are polynomially solvable under the proposed model. Processing times may be reduced by allocating resources. For the controllable processing times problem with linear resource allocation, we consider a common due-date assignment problem with learning and deteriorating effect and resource allocation on a single machine, in which all jobs have a common due-date. The objective is to determine the optimal common due-date, the optimal sequence and the optimal resource allocation to minimize a total costs based on earliness, tardiness, common due-date, and resource consumption. We show that the problem is polynomially solvable by transforming this problem into an assignment problem.

scheduling; learning effects; deterioration effects; resource allocation; assignment problem

2014-05-01。

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

高 洁(1989-),女,辽宁葫芦岛人,沈阳师范大学硕士研究生;

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

1673-5862(2014)04-0476-06

O223

: A

10.3969/ j.issn.1673-5862.2014.04.005