欢迎来到天天文库
浏览记录
ID:33878607
大小:462.48 KB
页数:44页
时间:2019-02-28
《list scheduling in order of #-points on a single machine》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、ListSchedulinginOrderofα-PointsonaSingleMachineMartinSkutellaInstitutf¨urMathematik,TechnischeUniversit¨atBerlinStraßedes17.Juni136,10623Berlin,Germanyskutella@math.tu-berlin.dehttp://www.math.tu-berlin.de/~skutella/Abstract.Manyapproximationresultsforsinglemachineschedulingproblemsrelyon
2、theconversionofpreemptiveschedulesinto(preemp-tiveornon-preemptive)solutions.Theinitialpreemptivescheduleisusuallyanoptimalsolutiontoacombinatorialrelaxationoralinearprogrammingrelaxationoftheschedulingproblemunderconsideration.Itthereforeprovidesalowerboundontheoptimalobjectivefunctionva
3、lue.However,italsocontainsstructuralinformationwhichisusefulfortheconstructionofprovablygoodfeasibleschedules.Inthiscontext,listschedulinginorderofso-called‘α-points’hasevolvedasanimpor-tantandsuccessfultool.Wegiveasurveyandauniformpresentationofseveralapproximationresultsforsinglemachine
4、schedulingwithtotalweightedcompletiontimeobjectivefromthelastyearswhichrelyontheconceptofα-points.1IntroductionWeconsiderthefollowingsinglemachineschedulingproblem.ThereisasetofnjobsJ={1,...,n}thatmustbeprocessedonasinglemachine.Eachjobjhasanon-negativeintegralprocessingtimepj,thatis,itmu
5、stbeprocessedduringpjtimeunits.Themachinecanprocessatmostonejobatatime.Eachjobjhasanon-negativeintegralreleasedaterjbeforewhichitcannotbeprocessed.Inpreemptiveschedules,ajobmayrepeatedlybeinterruptedandcontinuedlater.Innon-preemptiveschedules,ajobmustbeprocessedinanuninterruptedfash-ion.T
6、heremaybeprecedenceconstraintsbetweenjobs.Ifj≺kforj,k∈J,itisrequiredthatjiscompletedbeforekcanstart.WedenotethecompletiontimeofjobjbyCjandseektominimizethetotalweightedcompletiontime:Anon-negativeweightwjisassociatedwitheachjobjandthegoalistomini-Pmizej∈JwjCj.Inordertokeepthepresentations
7、imple,wewillalmostalwaysassumethattheprocessingtimespjarepositiveintegersandthatwj>0,foralljobsj∈J.However,allresultscanbecarriedovertothecasewithzeroprocessingtimesandweights.Inscheduling,itisquiteconvenienttorefertotherespectiveproblemsusingthestandardclassificatio
此文档下载收益归作者所有