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

《简论到达时间依赖于资源分配的单机排序问题》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、简论到达时间依赖于资源分配的单机排序问题　摘要:研究了具有线性退化及学习效应作用下的单机排序问题,对于工件的到达时间是其资源消耗量的正的严格单调递减函数时,考虑了总资源消耗量限定情形下最大完工时间极小化问题,给出了相应的最优算法;也考虑了满足工件最大完工时间限制的条件下极小化资源消耗的总量问题,提出最优资源分配方案。　　关键词:单机排序;学习与退化效应;资源限制;资源消耗量;最大完工时间　　　doi:10.3969/j.issn.1001-3695.2010.07.014　　　　Singlemachineschedulingp

2、roblemseof　　jobsdependingonresourceallocated　　ZHANGXin-gong1,YANGuang-le1,TANGGuo-chun2,TANGHai-bo1　　(1.BusinessSchool,UniversityofShanghaiforScienceTechnology,Shanghai200093,China;2.ManagerialEngineeringInstitute,ShanghaiSecondPolytechnicUniversity,Shanghai2012

3、09,China)　　　　Abstract:Thispaperconsideredthesinglemachineschedulingproblemseofjobsption.Itpresentedtheoptimalalgorithmsfortheproblemstominimizethemakespanptionconstraints.Itpresentedanoptimalallocationschemealsofortheproblemstominimizethetotalresourceconsumptionakes

4、panconstraints.　　Keyachinescheduling;learningeffectanddeterioratedjobs;resourceconstraints;totalresourceconsumption;makespan　　0引言　　在经典的排序问题中,通常假设工件的加工时间为常数。但在实际生产中,工件的加工时间随着时间的改变而递增或递减。工件加工时间是其开工时间函数的问题,在钢铁工业、塑料工业、军事以及医疗等方面有广泛的应用,并且也取得了较多的研究成果[1,2]。　　对于单机排序问题,Broax=

5、max{Cj

6、j=1,2,…,n}表示序列π中最大完工时间。　本文研究下面两个问题(用Graham等人[17]的三个参数α

7、β

8、γ表示):　　1

9、pj[r]=(aj+βt)ra,rj=f(uj),uj≤U

10、Cmax　　(1)　　1

11、pj[r]=(aj+βt)ra,rj=f(uj),Cmax≤C

12、uj(2)　　　　给出了算法并证明此算法得到的序列是最优序或者提出最优资源分配方案。其中:u≤uj≤,uj为工件Jj的资源分配量;rj是工件Jj的到达时间;f是严格递减的正值函数。　　引理1对于问题

13、1

14、pj[r]=(aj+βt)ra

15、Cmax,若π={J1,J2,…,Jn},并且工件序列的开工时间为t0,则　　Cmax{t0

16、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

17、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

18、pj[r]=(aj+βt)ra

19、Cmax,若序列π={J1,J2,…,Jn},最大完工时间为C,则序列π中第一个工件的开始加工时间为　　　　t0=C-nj=1ajjani=

20、j+1(1+βia)nj=1(1+βja)　　1极小化最大完工时间问题　　对于式(1),由于本模型是在离线排序情形下进行的,求极小化最大完工时间问题仅仅需要考虑按照工件aj的非增序列的排序即可。　　设序列π={J[1],J[2],…,J[n]},J[j]表示在第j位