Minimizing totalcompletiontimeonasinglemachinewithaflexible maintenanceactivity

A problemofjointlyschedulingmultiplejobsandasinglemaintenanceactivityonasinglemachine with theobjectiveofminimizingtotalcompletiontimeisconsideredinthispaper.Itisassumedthat the machineshouldbestoppedformaintenancewhichtakesaconstantdurationwithinapredefined period.Theproblemisgeneralizedfromtheonewithafixedmaintenanceinthatitrelaxesthestarting time ofthemaintenancefromafixedtimepointtoapredefinedperiod.Bothresumableand nonresumablecasesarestudied.First,threepropertiesofanoptimalsolutiontoeachofthetwocases are identified.Thenitisshownthattheproposedshortestprocessingtime(SPT)algorithmisoptimal for theresumablecase.Asforthenonresumablecase,theconditionsunderwhichtheSPTalgorithmis optimalarealsospecified.Furthermore,itisshownthatrelaxingthestartingtimeofthemaintenance cannotimprovetherelativeerrorboundoftheSPTalgorithm.Thefocusofthepaperispresented afterwards,whichistodevelopadynamicprogrammingalgorithmandabranch-and-boundalgorithm to generateanoptimalsolutionforthiscase.Experimentalresultsshowthatthesealgorithmsare effectiveandcomplementaryindealingwithdifferentinstancesoftheproblem. Statementofscopeandpurpose: In themajorityofschedulingproblemswithpreventivemaintenance, maintenanceperiodsareassumedtobeconstant.However,inrealindustrysettings,suchperiodsmay be flexible.Therefore,itisnecessarytoconsiderschedulingproblemswithflexiblemaintenance.This paper focusesonasinglemachineprobleminwhichjobprocessingandmachinemaintenancehaveto be scheduledsimultaneously.Theobjectiveistominimizetotalcompletiontimeofjobsforboth resumableandnonresumablecases.Fortheresumablecase,aSPTalgorithmproposedinthispaperis showntobeoptimal.Ontheotherhand,forthenonresumablecase,therelativeworst-caseerrorbound of theSPTalgorithmisanalyzed,andfurther,adynamicprogrammingalgorithmandabranch-and- boundalgorithmareproposedtosolvethisproblemoptimally.Finally,experimentalresultsare providedtoshowtheeffectivenessandcomplementarityoftheabovealgorithms.