A time-indexed formulation for single-machine sche

MemorandumCOSOR96-14,1996,EindhovenUniversityofTechnologyMemorandumCOSOR96-14,1996,EindhovenUniversityofTechnologyATime-IndexedFormulationforSingle-MachineSchedulingProblems:ColumnGenerationJ.M.vandenAkker1CenterforOperationsResearchandEconometricsCatholiqueUniversityofLouvainVoieduRomanPays34,1348Louvain-la-Neuve,BelgiumC.A.J.HurkensDepartmentofMathematicsandComputingScienceEindhovenUniversityofTechnologyP.O.Box513,5600MBEindhoven,TheNetherlandsM.W.P.SavelsberghSchoolofIndustrialandSystemsEngineeringGeorgiaInstituteofTechnologyAtlanta,GA30332-0205,U.S.A.April3,1996AbstractTime-indexedformulationsforsingle-machineschedulingproblemshavereceivedalotofattention,becausethelinearprogramrelaxationsprovidestrongbounds.Unfortunately,time-indexedformulationshaveonemajordisadvantage:theirsize.Evenforrelativelysmallinstancesthenumberofconstraintsandthenumberofvariablescanbelarge.Inthispaper,wediscusshowDantzig-Wolfedecompositiontechniquescanbeappliedtoalleviatethedicultiesassociatedwiththesizeoftime-indexedformulationsandthattheapplicationofthesetechniquesstillallowstheuseofcutgenerationtechniques.Keywords:scheduling,Dantzig-Wolfedecomposition,columngeneration.1SupportedbyHumanCapitalandMobility(HCM),grantnumberERBCHBGTC940513;asigni-cantpartoftheresearchwascarriedoutwhiletheauthorwasatEindhovenUniversityofTechnology.11IntroductionIntegerprogrammingapproachestosingle-machineschedulingproblemshavereceivedaconsiderableamountofattentioninthepastdecade.Forasurveyoftheformulationsthathavebeenproposedandinvestigated,wereferthereadertoanexcellentsurveybyQueyranneandSchulz[1994].Oneofthemorepowerfulformulations,inthesensethatitcanmodelmanydierenttypesofschedulingproblemsandthatitsLPrelaxationprovidesstrongbounds,isbasedontime-discretization[Sousa1989,SousaandWolsey1992,VandenAkker,VanHoesel,andSavelsbergh1993,VandenAkker1994,VandenAkker,Hurkens,andSavelsbergh1995,CramaandSpieksma1995].Unfortunately,thesetime-indexedformulationshaveonemajordisadvantage:theirsize.Evenforrelativelysmallinstancesthenumberofconstraintsandthenumberofvariablescanbelarge.Asaresult,solutiontimesandmemoryrequirementsmaybeprohibitive.Dantzig-Wolfedecompositionisawell-knowntechniquethatcanbeappliedtolargescalestructuredlinearprogramstoreducethememoryrequirementsandsolutiontimes.TheapplicationofDantzig-Wolfedecompositiontechniquesresultsinareformulationofthelinearprogramwithfarfewerconstraintsbutmanymorevariables.However,thevariablesarehandledimplicitlyratherthanexplicitly.Variablesareleftoutofthelinearprogrambecausetherearetoomanytohandleecientlyandmanyofthemwillbeequaltozeroinanoptimalsolutionanyway.Thentochecktheoptimalityofthesolutiontothelinearprogram,asubproblem,calledthepricingproblem,issolvedtotrytoidentifyvariablestoenterthebasis.Ifsuchvariablesarefound,thelinearprogramisreoptimized.Inthispaper,weinvestigatewhetherDantzig-Wolfedecompositiontechniques,alsoreferredtoascolumngenerationtechniques,canbeusedtoalleviatethedicultiesassociatedwiththesizeoftime-indexedformulations.ExperimentswithanLP-basedbranch-and-boundalgorithmbasedonatime-indexedformulationfortheproblemofminimizingthetotalweightedcompletiontimeonasingle-machinesubjecttoreleasedateshaveshownthattheboundsprovidedbytheLPrelaxationofthetime-indexedformulationarestrong.However,toobtainarobustalgorithm,i.e.,analgorithmthatconsistentlysolvesinstancesinareasonableamountoftime,itisnecessarytoenhancethealgorithmwithcutgeneration[VandenAkker,Hurkens,andSavelsbergh1995].Therefore,amajorpartoftheresearchdiscussedinthispaperdealswiththecomplexitiesassociatedwithcombiningapproachesbasedoncolumngenerationwithcutgeneration.Tothebestofourknowledge,thisisoneofthefewstudiesinwhichthisdicultbutimportantissueiscoveredinsomedetail.InSection2,wereviewthetime-indexedformulationforsingle-machineschedulingproblems.InSection3,wepresentandanalyzethereformulationobtainedbyapplyingDantzig-Wolfedecompositionanddiscussitsadvantagesanddisadvantages.InSection24,wedevelopacuttingplanealgorithmforalargeclassofsinglemachineschedulingproblemsbasedonthereformulationdiscussedinSection3.Weelaborateontheissuesrelatedtocombiningcolumngenerationandcutgenerationandpresentsomegeneralresultsthatarealsoapplicableinothercontexts.InSection5,wediscusssomeextensionsandpresentsomeconcludingremarks.2Atime-indexedformulationforsingle-machineschedul-ingproblemsAtime-indexedformulationisbasedontime-discretization,i.e.,timeisdividedintoperiods,whereperiodtstartsattimet1andendsattimet.TheplanninghorizonisdenotedbyT,whichmeansthatweconsiderthetime-periods1;2;:::;T.Weconsiderthefollowingtime-indexedformulationforsingle-machineschedulingproblems:minnXj=1Tpj+1Xt=1cjtxjtsubjecttoTpj+1Xt=1xjt=1(j=1;:::;n);(1)nXj=1tXs=tpj+1xjs1(t=1;:::;T);(2)xjt2f0;1g(j=1;:::;n;t=1;:::;Tpj+1);wherethebinaryvariablexjtforeachjobj(j=1;:::;n)andtimeperiodt(t=1;:::;Tpj+1)indicateswhetherjobjstartsinperiodt(xjt=1)ornot(xjt=0).Theassignmentconstraints(1)statethateachjobhastobestartedexactlyonce,andthecapacityconstraints(2)statethatthemachinecanhandleatmostonejo