list scheduling in order of #-points on a single machine

《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