您好,欢迎访问三七文档
FACHBEREICH3MATHEMATIKRESOURCE-CONSTRAINEDPROJECTSCHEDULINGWITHTIMEWINDOWS:ABRANCHINGSCHEMEBASEDONDYNAMICRELEASEDATESbyANDREASFESTROLFH.M¨OHRINGFREDERIKSTORKMARCUETZNo.596/1998(revised1999)Resource-ConstrainedProjectSchedulingwithTimeWindows:ABranchingSchemeBasedonDynamicReleaseDates?AndreasFest,RolfH.M¨ohring,FrederikStork,andMarcUetzTechnischeUniversit¨atBerlin,FachbereichMathematik,Sekr.MA6–1,Straßedes17.Juni136,D-10623Berlin,Germanyffest,moehring,stork,uetzg@math.tu-berlin.deAbstractWeproposeabranch-and-boundalgorithmforresource-constrainedprojectschedulingwhereanytwoofjobscanbelinkedbyarbitraryminimalandmaximaltimelags.Thejobshavetobeschedulednon-preemptively,andwhileinprocess,theyrequireseverallimitedresources.Theobjectiveistofindafeasibleschedulewhichminimizestheprojectmakespan.Differentbranch-and-boundal-gorithmshavebeenpreviouslyproposed–eitherbasedonconstraintpropagationtechniques,orbasedontheideatobranchoverso-calledresourceconflictswhichareresolvedbyintroducingadditionalprecedenceconstraints.Ourapproachalsofollowsthelatterprinciple.Thenewideaistoresolveresourceconflictsonlylocallybyadynamicupdateofjobreleasedatesinsteadofintroducingprece-denceconstraints.Thisgivesrisetoareductionofbothcomputationtimeandmemoryrequirementsineverynodeoftheenumerationtree,however,attheex-penseofalossofinformation.Nevertheless,enrichedbypreprocessing,strongdominancerules,andaflexiblesearchstrategy,ourcomputationalresultsshowthatthealgorithmperformsbetterthanpreviousbranch-and-boundalgorithms,andiscompetitivewithaveryrecentconstraintpropagationapproachaswellastailor-madeheuristics,alsoforlarge-scaleinstances.1IntroductionResource-constrainedschedulingproblemsoccurinmanyreal-worldapplicationssuchascivilengineering,supplychainplanning,productionplanning,andmanyothers.Givenisasetofactivitiesorjobswhichhavetobescheduledinordertominimizesomeobjectivefunction.Thejobsaretypicallysubjecttobothtemporalandresourceconstraints.Temporalconstraintsaregivenbyminimalandpossiblyalsomaximaltimelagsbetweenthestarttimesofcertainjobs.Thisallowstomodelseveralpeculiaritiessuchastime-varyingresourceavailabilitiesorrequirements,so-calledtimewindowsfortheprocessingtimesofjobs,aswellasjobsynchronizingorminimaljoboverlaps.Whileinprocess,everyjobrequiresacertainamountofrenewableresources(e.g.,ma-chinesand/orpersonnel),buttheavailabilityoftheseresourcesislimited.Theobjective?ResearchsupportedbytheBundesministeriumf¨urBildung,Wissenschaft,ForschungundTechnologie(bmb+f),grantNo.03-MO7TU1-3.Correspondenceto:MarcUetz.2A.Fest,R.H.M¨ohring,F.Stork,andM.Uetzmostfrequentlyaddressedistofindatime-andresource-feasiblescheduleminimiz-ingtheprojectmakespan,whichisthetimerequiredtocompletealljobs.WerefertoSection2foradetailedaccountofthemodelandnotationusedthroughoutthepaper.FollowingtheclassificationschemeproposedbyBrucker,Drexl,M¨ohring,Neumann,andPesch(1999),themodelunderconsiderationistermedPSjtempjCmax.Severalwellknowncombinatorialoptimizationproblemscanbe(polynomially)transformedintoresource-constrainedprojectschedulingproblems,particularlyma-chineandshopschedulingproblems,butalsovertexcoloringofgraphs(Sch¨affter1997).Asaconsequence,theproblemunderconsiderationisnotonlyNP-hard,butitisevenhardtoapproximate,andalreadythefeasibilityproblemfortheproblemPSjtempjCmaxisNP-hardinthestrongsense(areductionofCLIQUEcanbefoundin(Bartusch,M¨ohring,andRadermacher1988)).Nevertheless,perhapsduetothepracticalrelevance,exactandheuristicalgorithmsforresource-constrainedprojectschedulingarerecentlyreceivingagrowingattention,particularlyfortheproblemsettingunderconsideration.Thisisreflectedbyseveralbranch-and-boundalgorithmswhichhavebeenproposedinthelastyears,e.g.,byDeReyckandHerroelen(1998)(seealso(DeReyck,Herroelen,andDemeulemeester1998)),Schwindt(1997,1998),andDorndorf,Pesch,andPhanHuy(1998).Otherap-proachesincludetailor-madeheuristics,someofwhichhavebeensummarizedinapaperbyNeumannandZimmermann(1998).Forarestrictedmodelwithoutmaximaltimelags,butwithtime-varyingresourcerequirementsofthejobs,LP-basedheuristicsaswellaslocalsearchalgorithmshavebeenproposedbyCavalcante,DeSouza,Savels-bergh,Wang,andWolsey(1998).Infact,thisrestrictedmodeloriginatesinachemicalproductionprocessatBASFAG,Germany(KallrathandWilson1997).Forthesamemodel,HeipckeandColombani(1997,1998)haveintroducedaconstraintpropaga-tionalgorithm,andaheuristicbasedonapproximationalgorithmsforsingle-machineschedulingproblemshasbeenproposedbySavelsbergh,Uma,andWein(1998).Inthispaper,wefocusonthegeneralproblemPSjtempjCmaxinvolvingarbitraryminimalandmaximaltimelags.Forthisproblem,importantordertheoreticinsightsintothestructureofoptimumsolutionshavebeenobtainedbyBartuschetal.(1988).Theyalsoproposedabranch-and-boundprocedure,however,theirimplementationisnolongeravailable.Partiallybasedonideasoftheirwork,branch-and-boundalgorithmshavebeenevaluatedmorerecentlybyDeReyckandHerroelen(1998)andSchwindt(1997,1998).Theunderlyingideaofthesealgorithmsisthattime-feasibleschedules(i.e.,notemporalconstraintisviolated)areenumeratedbysystematicallyre
本文标题:Resource-Constrained Project Scheduling with Time
链接地址:https://www.777doc.com/doc-4940629 .html