简论到达时间依赖于资源分配的单机排序问题

中国论文网为大家解读本文的相关内容： 　摘 要:研究了具有线性退化及学习效应作用下的单机排序问题,对于工件的到达时间是其资源消耗量的正的严格单调递减函数时,考虑了总资源消耗量限定情形下最大完工时间极小化问题,给出了相应的最优算法;也考虑了满足工件最大完工时间限制的条件下极小化资源消耗的总量问题,提出最优资源分配方案。
　　关键词:单机排序;学习与退化效应;资源限制;资源消耗量;最大完工时间
　　　doi:.1001-3695.2010.07.014
　　
　　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
　　(ss school, university of shanghai for science & technology, shanghai 200093, china;rial 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=-0.332,β=1,p=26,q=2,u=0.5,=13,u=24。序列π={j[1],j[2],j[3],j[4]}满足工件按照a[j]非增顺序排列。
　　cmax{0|j[1],j[2],j[3],j[4]}=21.033, 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]=7.5
　　k-1j=1u[j]+(n-(k-1))u≤u
　　
　　k-1=2,r[1]=5.023,u[1]=10.489
　　r[2]=13.047,u[2]=6.477
　　k-1j=1u[j]+(n-(k-1))u≤u
　　
　　k-1=3,r[1]=2.054,u[1]=11.973
　　r[2]=7.110,u[2]=9.445
　　r[3]=14.345,u[3]=5.828
　　k-1j=1u[j]+(n-(k-1))u≤u
　　因此k-1=2,即k=3。利用式(3)求d:
　　
　　r*[1]=5.023-0.277d,u*[1]=10.489+0.139d

　r*[2]=13.047-0.577d,u*[2]=6.477+0.289d
　　r*[3]=25-d,u*[3]=0.5+0.5d
　　根据式(3)得d=6.502。
　　最优资源为u*[1]=11.393,u*[2]=8.356,u*[3]=3.751,u*[4]=0.5。
　　
　　最大完工时间为cmax{r*[1]|j[1],…,j[n]}=52.991。
　　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 ling 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 t.a concise survey of scheduling with time-dependent processing times[j].european journal of operational research,2004,152(1):1-13.
　　[3]browne s,yechiali ling deteriorating jobs on a single processor[j].operations research,1990,38(3):495-498.
[4]mosheiov g.v-shaped policies for scheduling deteriorating jobs[j].operations research,1991,39(6):979-991.
　　
　　[5]mosheiov ling 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 zing 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 c.a 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 b.a 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 ed optics in scheduling theory[j].annals of discrete mathematics,1987,132:1-59.
　　[13]jackson j ling 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 zation and approximation in deterministic sequencing and scheduling:a survey[j].annals of discrete mathematics,1979,5(2):287-326.

　　中国论文网(www.lunwen.net.cn)免费学术期刊论文发表,目录,论文查重入口,本科毕业论文怎么写,职称论文范文,论文摘要,论文文献资料,毕业论文格式,论文检测降重服务。