简论到达时间依赖于资源分配的单机排序问题
摘 要:研究了具有线性退化及学习效应作用下的单机排序问题,对于工件的到达时间是其
资源消耗量的正的严格单调递减函数时,考虑了总资源消耗量限定情形下最大完工时间极
小化问题,给出了相应的最优算法;也考虑了满足工件最大完工时间限制的条件下极小化资
源消耗的总量问题,提出最优资源分配方案。
关键词:单机排序;学习与退化效应;资源限制;资源消耗量;最大完工时间
doi:
Single machine scheduling problems with arrive time of
jobs depending on resource allocated
ZHANG Xin-gong•1,YAN Guang-le•1,TANG Guo-chun•2,TANG Hai-bo•1
( School, University of Shanghai for Science & Technology, Shanghai
200093, China; Engineering Institute, Shanghai Second Polytechnic
University, Shanghai 201209, China)
Abstract:This paper considered the single machine scheduling problems with learning
effect and deteriorating jobs. Arrive time of jobs was a positive and strictly decrease
function about resource presented the optimal algorithms for the
problems to minimize the makespan with the total resource consumption
presented an optimal allocation scheme also for the problems to minimize the total
resource consumption with the makespan constraints.
Key words:single-machine scheduling; learning effect and deteriorated jobs; resource
constraints; total resource consumption; makespan
0 引言
在经典的排序问题中,通常假设工件的加工时间为常数。但在实际生产中,工件的加工
时间随着时间的改变而递增或递减。工件加工时间是其开工时间函数的问题,在钢铁工业
、塑料工业、军事以及医疗等方面有广泛的应用,并且也取得了较多的研究成果[1,2]。
对于单机排序问题,Browne 等人[3]研究了工件具有不同基本加工时间和退化率时极小
化最大完工时间的问题。MoshEiov[4]研究了工件具有相同基本加工时间和不同的退化率
时极小化总完工时间问题,并指出了最优排序是 V 形的。MoshEIov[5]进一步简化了该模型,
研究工件的加工时间是简单线性的情况,证明了最大完工时间、总完工时间、最大延误问
题以及延误工件的个数问题是多项式时间可解的。最近一些工业中的研究已经表明,由于
工厂反复加工许多同样或类似的产品,从而获得经验与知识,使得费用降低,这种现象被称之
为学习效应。Biskup[6]首先分析了与位置相关的具有学习效应的排序问题,考虑了极小化
共同工期偏差和极小化总完工时间的两类单机排序问题。他证明工件的加工时间为其加工
顺序中位置的递减函数时这两类问题是多项式时间可解的。Kuo 等人[7]提出工件的加工时
间是已经加工过的工件的基本加工时间之和有关的函数模型,对于目标函数为极小化总完
工时间的单机排序问题,证明最小加工时间优先规则所得的排序为最优排序。
具有退化或学习效应问题已经被广泛地讨论,但它们同时被考虑的现象却很少。而现
实生产中这种现象到处可见。Wang 等人[8]提到下面的生产实例:在生产瓷器的工艺中,一
方面根据设计利用原材料塑形,原材料是由粘土和特殊的凝结剂制成,随着时间的增加原材
料会越来越硬,这样会使得制作耗费更多的加工时间;另一方面,手工艺人在设计和制作上会
越来越熟练,这样又会提高生产力,此时同时考虑退化和学习效应是十分必要的。文献
[9~11]研究了具有学习和退化效应的单机与流水机环境下,最大完工时间、总(权)完工时间
和最大延迟问题并给出了多项式时间算法。
近二十年来,一类特殊的资源限制排序问题常常被考虑(见文献[12,13])。Janiak[14]介
绍了在单机排序下工件完工时间的最优时间控制:假设工件的到达时间没有固定,但被一些
变量所决定。特别地,Janiak 假设工件的到达时间是资源消耗量的正的严格递减的连续函
数,并且资源消耗量具有局部和总的限制。最近 Zhao 等人[15]讨论了两个排序问题:假设工
件的加工时间是开工时间的递减函数;工件的到达时间受某种资源约束。研究了时间表长
约束下的总资源分配量问题和总资源量约束下的时间表长问题, 均给出最优算法。最近
Zhu 等人[16] 研究了线性递增的退化模型,考虑到达时间受资源约束的问题。但是他们仅仅
是考虑简单的退化现象的排序模型,而将退化与学习效应结合起来考虑的问题却没有涉及,
但在实际的生产生活中这种情形经常发生。本文首次将资源限制的模型引入退化和学习的
排序模型中,并进行了初步的研究和•分析。
设 j(j=1,2,…,n)表示工件的序号,机器一次只能处理一个工件,并且中断不被允许。工件
J•j 在第 r 位置加工时的加工时间为 pj[r]=(α•j+βt)r•a。其中:a•j 为工件 J•j 的基本加工时间
;β(≥0)为退化率;t(≥0)是工件 J•j 的开工时间;学习因子用•a(≤0)表示。对序列
π={J•1,J•2,…,J•n},C•j=C•j(π)表示工件 J•j 的完工时间。Cmax=max{C•j|j=1,2,…,n}表示序列
π 中最大完工时间。
本文研究下面两个问题(用 Graham 等人[17]的三个参数•α|β|γ 表示):
1|pj[r]=(a•j+βt)r•a,r•j=f(u•j),•u•j≤U|Cmax
(1)
1|pj[r]=(a•j+βt)r•a,r•j=f(u•j),Cmax≤C|•u•j(2)
给出了算法并证明此算法得到的序列是最优序或者提出最优资源分配方案。其中
:u≤u•j≤,u•j 为工件 J•j 的资源分配量;r•j 是工件 J•j 的到达时间;f 是严格递减的正值函数。
引理 1 对于问题 1|pj[r]=(a•j+βt)r•a|Cmax,若 π={J•1,J•2,…,J•n},并且工件序列的开工时
间为 t•0,则
Cmax{t•0|J•1,J•2,…,J•n}=t•0••nj=1(1+βj•a)+••nj=1a•jj•a••ni=j+1(1+βi•a)
证明 (用归纳法)由于 π={J•1,J•2,…,J•n},则可直接计算得到
C•1=(a•1+βt•0)+t•0=(1+β)t•0+a•1,C•2=C•1+(a•2+βC•1)2•a=(1+β2•a)(1+β)t•0+(1+β2•a)a
•1+a•22•a=t•0••2j=1•(1+βj•a)+••2j=1a•jj•a••2i=j+1(1+βi•a)。假设 n=k 时成立, 考虑
n=k+1 时的情形
:Ck+1=C•k+(ak+1+βC•k)(k+1)•a=t•0•••k+1j=1(1+βj•a)+•••k+1j=1a•jj•a•••k+1i=j+1(1+βi•a)
,即命题成立。
引理 2 对于问题 1|pj[r]=(a•j+βt)r•a|Cmax,若序列 π={J•1,J•2,…,J•n},最大完工时间为
C,则序列 π 中第一个工件的开始加工时间为
t•0=C-••nj=1a•jj•a••ni=j+1(1+βi•a)••nj=1(1+βj•a)
1 极小化最大完工时间问题
对于式(1),由于本模型是在离线排序情形下进行的,求极小化最大完工时间问题仅仅需
要考虑按照工件 a•j 的非增序列的排序即可。
设序列 π={J[1],J[2],…,J[n]},J[j]表示在第 j 位置加工的工件。由于每个工件的资源分配
量均有下限,资源分配总量应满足 U≥n•u。若 u[j]=u,j=1,…,n,则有
Cmax(π,u)=f(u)••nj=1(1+βj•a)+••nj=1a[j]j•a••ni=j+1(1+βi•a)
此时工件的到达时间均为 f(u),序列最大完工时间可由 r[1]=f(u)决定。 如果增加工件
J[1]的资源分配量, 则 r[1]变小,因而最大完工时间也会变小。设工件 J[1]的资源分配量的最
大数为 u••max[1],则 u••max[1]=min{U-(n-1)u,}。设 r•*[1]=f(u••max[1]),则工件 J[1]的完工
时间为 Cmax(r•*[1]|J[1])=(1+β)r•*[1]+a[1]。
若(1+β)r•*[1]+a[1]≥f(u),则最优资源分配为
u•*[1]=u••max[1];u•*[j]=u, j=2,…,n
Cmax=f(u••max[1])••nj=1(1+βj•a)+••nj=1a[j]j•a••ni=j+1(1+βi•a)
若(1+β)r•*[1]+a[1]≥f(u),则最优资源分配为
u•*[1]=umax[1];u•*[j]=u,j=2,…,n
Cmax=f(u••max[1])••nj=1(1+βj•a)+••nj=1a[j]j•a••ni=j+1(1+βi•a)
若(1+β)r•*[1]+a[1]f(u),j=k,…,n;u•*[j]=u,j=k+1,…,n。
令 d=f(u)-C[k-1](π,u•π•*) ,由引理 2,J[1],J[2],…,J[k]的到达时间为
r[1]•*=f(u)-d-•••k-1j=1a[j]j•a•••k-1i=j+1(1+βi•a)•••k-1j=1(1+βj•a)
r[2]•*=(1+β)r•*[1]+a[1],…,
r[k]•*=r[1]•*•••k-1j=1(1+βj•a)+••••k-1j=1a[j]j•a•••k-1i=j+1(1+βi•a)=f(u)-d
J[1],J[2],…,J[n]的资源分配量为
u•*[j]=f••-1(r•*[j]),j=1,…,k-1;
u•*[j]=u,j=k+1,…,n
••kj=1u•*[j]+(n-k)u=U(3)
k 和 d 由式(3)确定。首先考虑 k,其中 r[k]=f(u),假设工件 J[j]的到达时间为 r[j],j=1,…,k,
则
r[1]=f(u)-•••k-1j=1a[j]j•a•••k-1i=j+1(1+βi•a)•••k-1j=1(1+βj•a)
r[2]=(1+β)r[1]+a[1],…
r[k]=r[1]•••k-1j=1(1+βj•a)+•••k-1j=1a[j]j•a•••k-1i=j+1(1+βi•a)=f(u)
u[j]=f••-1(r[j]),j=1,…,k-1
u[j]=u,j=k,…,n
•••k-1j=1u[j]+(n-(k-1))u≤U(4)
由此得到 k,从而 d 也可以由上述方法计算出来。基于上述分析,有
算法 1
1)把工件按照 a[j]非增顺序排列,设 u••max[1]=min{U-(n-1)u,},r[1]=f(u••max[1])。
2)若 C[1]≥f(u),则 u•*[1]=u••max[1],u•*[j]=u,j=2,…,n 停止;否则转入 3)。
3)设 k 是使下式成立的最小整数••kj=1u•*[j]+(n-(k-1))u≤U。其中
u[j]=f••-1(r[j]),且 r[j]满足式(4)。
4)资源分配:u[j]=f••-1(r[j]),j=1,…,k;u•*[j]=u,j=k+•1,…,n。其中 d 满足等式
••kj=1u•*[j]+(n-k)u=U。
基于上述分析有下面的定理成立。
定理 1 式(1)、算法 1 可以得到最优解。
如果在 O(g(n))时间内计算出 f、f••-1 和 d,则算法的复杂性为 O(max{g(n),n log n})。
下面用数值例子说明引理 1 的求解。为了方便,取 f 为线性函数,即 r•j=p-qu•j。
例如,对于式(1)|pj[r]=(a•j+βt)r•a,r•j=f(u•j),•u•j≤U|Cmax。其中
n=4,a•1=3,a•2=2,a•3=a•4=1,a=,β=1,•p=26,q=2,u=,=13,U=24。序列
π={J[1],J[2],J[3],J[4]}满足工件按照 a[j]非增顺序排列。
Cmax{0|J[1],J[2],J[3],J[4]}=, f(u)=25
u••max[1]=min{U-(n-1)u,}=13
r•*[1]=f(u••max[1])=0,Cmax(r•*[1]|J[1])=3
接下来利用式(4)求 k-1。
k-1=1,r[1]=11,u[1]=
•••k-1j=1u[j]+(n-(k-1))u≤U
k-1=2,r[1]=,u[1]=
r[2]=,u[2]=
•••k-1j=1u[j]+(n-(k-1))u≤U
k-1=3,r[1]=,u[1]=
r[2]=,u[2]=
r[3]=,u[3]=
•••k-1j=1u[j]+(n-(k-1))u≤U
因此 k-1=2,即 k=3。利用式(3)求 d:
r•*[1]=,u•*[1]=+
r•*[2]=,u•*[2]=+
r•*[3]=25-d,u•*[3]=+
根据式(3)得 d=。
最优资源为 u•*[1]=,u•*[2]=,u•*[3]=,•u•*[4]=。
最大完工时间为 C•max{r•*[1]|J[1],…,J[n]}=。
2 极小资源消耗量总和
对于式(2),给定一个序列 π={J[1],J[2],…,J[n]}和一个资源分配 u={u•1,u•2,…,u•n},工件
J[j]的到达时间为 r[j]和完工时间 C[j](π,u),计算如下:
r[j]=f(u[j]),j=1,2,…,n
C[1](π,u)=r[1]+(a[1]+βr[1])r•a
C[j](π,u)=max{r[j],C[j-1](π,u)}+
(a[j]+β max{r[j],C[j-1](π,u)})j•a=max1≤i≤j{r[i]+Cmax(r[i]|J[i],…,J[j])}
其中:C•max(r[i]|J[i],…,J[j])表示从 r[j]=f(u[j])开始加工工件 J[i],…,J[j]的最大完工时间。
对于 π 和 u,工件最大完工时•间为
Cmax(π,u)=max1≤j≤n{r[j]+Cmax(r[j]|J[j],…,J[n])}
资源消耗量为 U(π,u)=•nj=1u[j]。
设 C 为给定的工件的最大完工时间,式(2)是求 π•*和 u•*使得在满足 Cmax(π•*,u•*)≤C
条件下,资源消耗总量最小,即 U(π•*,u•*)=minπ minu{U(π,u)}。
若记 C•1=minπ{Cmax(•,)},C•2=minπ{Cmax(•,u)},由于工件的准备时间均相同,根据引理
1,C•1=f()••nj=1(1+•βj•a)
+••nj=1a[j]j•a••ni=j+1(1+βi•a)
,C•2=f(u)••nj=1(1+βj•a)
+••nj=1a[j]j•a••ni=j+1(1+βj•a),即•π,Cmax(π,)=C•1,Cmax(π,u)=C•2。
由于•π,其最大完工时间最小值均为 C•1,最大值均为 C•2,所以有
a)当 C
b)当 C>C•2 时,每个工件的资源分配量达到其下限即可,即 U(π•*,u•*)=n uC;
c)当 C•1≤C≤C•2 时,存在 π•*和 u•*,使 Cmax(π•*,u•*)=C。
显然,只有 C•1≤C≤C•2 时,讨论资源最优分配问题才有意义。对于给定的 π,记 π 的最
优资源分配为 u•*•π,即 Cmax(π,u•*•π)≤C 条件下 U(π,u•*•π)=minu{U(π,u)}。
由于 f 是严格递减的正值函数,工件的到达时间越大,资源消耗越少。在满足
Cmax(π,•)≤C 下,工件到达时间应尽可能大,因此只要考虑满足 Cmax(π,•)=C 的最优资源分
配即可,对于满足 Cmax(π,•)=C 的 π,即第一个工件的开工时间为
r•π=C-•nj=1a[j]j•a•ni=j+1(1+βi•a)•nj=1(1+βj•a)
在 π 中,工件 J[j]的达到时间 r[j]应满足:r[1]≤r•π,r[j]≤Cmax(r•π|J[1],…,Jj-1),j=2,…,n。
对于工件 J[j],若 r[j]≥•f(u),则 J[i]的资源分配量只需满足下限即可;若
r[j]
Cmax(r•π|J[1],…,Jj-1),所以对于给定的 π,u•*•π 的确定方法如下:
给定的 C,求使 Cmax(r•π|J[1],…,Jj-1)≤f(u)的最大整数 k
u•*[j]=f••-1(Cmax(r•π|J[1],…,Jj-1)),•j=1,…,k;u•*[j]=u,j=k+1,…,n(5)
由此可以得到下面的定理:
定理 2 对于式(2),按照基本加工时间 a•j 的非增顺序排列, 按照式(5) 分配资源,即可得
到满足最大完工时间限制的极小化资源消耗量总和的资源分配最优解。
证明 显然对于给定的 π,按照式(3) 分配资源为最优分配。下面证明
•π,U(π•*,u•*)≤U(π,u•*•π)。其中 π•*为工件按照基本加工时间的非增顺序排列的序列。
设某个序列 π,不满足工件按照基本加工时间非增的顺序排列,不妨设在 π 中两个相邻
工件 J[j]和 J[j+1]满足 a[j]
u[j]+u[j+1]=f••-1(r[j])+f••-1(r[j]+(a[j]+βr[j])j•a)
交换工件 J[j]和 J[j+1]的位置得到。在中,r[j+1]=•r[j]+(•a[j]+β•r[j])j•a
,•u[j]+•u[j+1]=f••-1(•r[j])+f••-1
(•r[j]+(•a[j]+•β•r[j])j•a。
由于 r[j]=r[j],•a[j]=•a[j+1],
•a[j]<•a[j+1],f••-1 是严格递减函数,有
若 j+1>k,则•u[j]+•u[j+1]=•u[j]+•u[j+1];若 j+1≤k,则••u[j]+•u[j+1]≤•u[j]+•u[j+1]。
交换工件 J[j]和 J[j+1]的位置对于其他工件的到达时间没有影响,因此有
U(,u•*)≤U(π,u•*•π)。经过若干次互换相邻工件,可使 π 转换成 π•*,而资源消耗总量不会增
加,即有 U(π•*,u•*)≤U(π,u•*•π)。
3 结束语
本文研究了具有线性退化及学习效应作用
下的单机排序问题,而在现实生产中这种模型的排序问题很多。本文考虑工件的到达
时间依赖资源分配的排序模型:工件的加工时间是与它的开工时间和其加工的位置有关的
函数,并且工件的到达时间具有一定的资源限制。这对于极小最大完工时间问题提供了最
优算法,极小化资源消耗量总和问题提出了最优资源分配方案。更复杂的机器环境和其他
目标函数是进一步感兴趣的课题。
参考文献:
[1]
ALIDAEE B,WOMER N with time-dependent proces-•sing times:review
and extensions[J].Journal of the Operational Research Society,1999,50(7):711-720.
[2]CHENG T C E,DING Q,LIN B M concise survey of scheduling with time-
dependent processing times[J].European Journal of •Operational
Research,2004,152(1):1-13.
[3]BROWNE S,YECHIALI deteriorating jobs on a single
processor[J].Operations Research,1990,38(3):495-498. [4]MOSHEiOV -shaped
policies for scheduling deteriorating jobs[J].Operations Research,1991,39(6):979-991.
[5]MOSHEIOV deteriorating jobs under simple linear
deterioration[J].Computer and Operational Research,1994,21(6):653-659.
[6]BISKUP -machines scheduling with learning considerations[J].European
Journal of Operational Research,1999,115:173-178.
[7]KUO W H,YANG D the total completion time in a single-machine
scheduling problem with a time-dependent learning effect[J].European Journal of
Operational Research,2006,174(2):1184-1190.
[8]WANG Xiu-li,CHENG T C -machine scheduling with deteriorating jobs and
learning effects to minimize the makespan[J].European Journal of Operational
Research,2007,178(1):57-70.
[9]LEE W note on deteriorating jobs and learning in single-machine scheduling
problems[J].International Journal of Business and •Economics,2004,3(1):83-89.
[10]WANG J note on scheduling problems with learning effect and deteriorating
jobs[J].International Journal of System Science,2006,37(12):823-833.
[11]张新功,李文华.具有学习与退化效应的单机排序问题[J].河南科学
,2008,26(4):398-400.
[12]BLAZEWICZ optics in scheduling theory[J].Annals of Discrete
Mathematics,1987,132:1-59.
[13]JACKSON J a production line to minimize maximum tardiness under
resource constraints[R].Los Angeles, CA:SIAM Rep University,1995.
[14]JANIAK machine sequencing with linear models of release
dates[J].Naval Research Logistics,1998,45(1):99-113.
[15]ZHAO Chuan-li,TANG scheduling machine problems with
deteriorating jobs[J].Applied Mathematic and •Computer,2005,161(3):865-874
.
[16]ZHU V C Y,SUN Lin-yan,SUN Lin-hui,et -machine sche-•duling tine-
dependent jobs with resource-dependent ready times[J].Computers & Industrial
Engineering,2010,58(1):84-87.
[17]GRAHAM R L,LAWER E L,LENSTRA J K,et and approximation in
deterministic sequencing and scheduling:a survey[J].Annals of Discrete
Mathematics,1979,5(2):287-326.
