Machine Scheduling Performance with Maintenance an

MachineSchedulingPerformancewithMaintenanceandFailureY.Guo4,A.Lim¹,B.Rodrigues²,S.Yu³¹DepartmentofIELM,HongKongUniversityofScienceandTechnology,ClearWaterBay,Kowloon,HongKong²SchoolofBusiness,SingaporeManagementUniversity,50StamfordRoad,Singapore178899³SchoolofComputing,NationalUniversityofSingapore,3ScienceDrive2,Singapore1175434DepartmentofComputerScience,CornellUniversity,Ithaca,NewYork,USA14853AbstractInmanufacturingcontrol,machineschedulingresearchhasmostlydealtwithproblemseitherwithoutmaintenanceorwithdeterministicmaintenancewhennofailurecanoccur.Thiscanbeunrealisticinpracticalsettings.Inthiswork,anexperimentalmodelisdevelopedtoevaluatetheeffectofcorrectiveandpreventivemaintenanceschemesonschedulingperformanceinthepresencemachinefailurewheretheschedulingobjectiveistominimizescheduleduration.Weshowthatneitherschemeisclearlysuperior,butthattheapplicabilityofeachdependsonseveralsystemparametersaswellastheschedulingenvironmentitself.Further,weshowthatparametervaluescanbechosenforwhichpreventivemaintenancedoesbetterthancorrectivemaintenance.Theresultsprovidedinthisstudycanbeusefultopractitionersandtosystemormachineadministratorsinmanufacturingandelsewhere.KeyWords:machinescheduling,experiments,manufacturingcontrol,maintenance11.IntroductionInmachineschedulingcontrol,goodboundsareavailablefortheproblemofminimizingscheduledurations,orthemakespan.Graham[8]providedaworst-caseboundfortheapproximationalgorithm,LongestProcessingTime,andCoffman,GareyandJohnson[6]providedanimprovedboundusingtheheuristic,MULTIFIT.Bycombiningthese,LeeandMassey[13]wereabletoobtainaneventighterbound.Thesestudies,however,assumedthecontinuousavailabilityofmachines,whichmaynotbejustifiedinrealisticapplicationswheremachinescanbecomeunavailableduetodeterministicorrandomreasons.Itwasnotuntilthelate1980’sthatresearchwascarriedoutonmachineschedulingwithavailabilityconstraints.Inastudy,Lee[15]consideredtheproblemofparallelmachineschedulingwithnon-simultaneousavailabletime.Inanotherwork,Lee[14]discussedvariousperformancemeasuresandmachineenvironmentswithsingleunavailability.Foreachvariantoftheproblem,asolutionwasprovidedusingapolynomialalgorithm,oritwasshownthattheproblemisNP-hard.Turkcan[24]analyzedtheavailabilityconstraintsforboththedeterministicandstochasticcases.Qi,ChenandTu[21]conductedastudyonschedulingthemaintenanceonasingle-machine.ThereaderisreferredtoTurkcan[24]foradetailedliteraturereviewofmachineschedulingwithavailabilityconstraints.Otherworkonschedulingwithmaintenanceisavailable,butwithdifferentschedulingenvironmentsand/orobjectives.LeeandLiman[16]studiedsingle-machineflow-timeschedulingwithmaintenancewhileKaspiandMontreuil[12]attemptedtominimizethetotalweightedcompletiontimeintwo2machineswithmaintenance.Schmidt[23]discussedgeneralschedulingproblemswithavailabilityconstraints,takingintoaccountdifferentreleaseandduedates.Thesestudiesaddressedtheproblemofmaintenance,butinalimitedway.Theyeitherconsideredonlyonedeterministicmaintenance(oravailability)constraintormaintenancewithoutmachinefailures.Theresults,however,areinadequateforsolvingrealproblems.Inindustrialsystems,machinescanfailduetoheatingorlackoflubrication,forexample;incomputersystems,theInternetisatypicalexampleofsysteminstabilityandbreakdownsduetobothhardwareandsoftwareproblems.Insuchcases,maintenanceneedstobecarriedout,eitherperiodicallyorafterfailure.Yet,evenwithmaintenance,failuresarenotcompletelyeliminated.Further,theoverallperformance,ratherthantheworst-caseperformance,isofgreaterrelevancetotheusersandadministratorsofthesesystems.Inthiswork,weaddressthisneedandstudytheaverageorexpectedperformanceofmachineschedulingwithbothmaintenanceandfailures.Sincemaintenanceaswellasfailureareeverydayoccurrencesinindustry,thisstudyisparticularlyrelevanttopractitionersandsystemsadministrators.1.1ScopeandPreliminariesWefirstdiscusstheschedulingenvironment,andtherulesandmaintenanceschemesusedinthisstudy.Forbasicnotationsanddefinitions,see,forexample,Pinedo[20]Schedulingenvironment:Thisstudyfocusesontwoareas:one,onsingle-machinescheduling,andtheotheronmultiple(andidentical)machinescheduling.Alljobsare3releasedatzerotime.Theobjectiveistominimizethemakespan.Inshort,theschedulingenvironmentsstudiedaredescribedas1||CmaxandPm||Cmax.Schedulingrules:Inviewofthesimplestructureintheproblem,weusetwoschedulingrules,namelyLongestProcessingTimefirst(LPT)andServiceInRandomOrder(SIRO),bothofwhicharelistschedulingrules.LPTsortsalljobsintoalistinnon-increasingorder;SIROgeneratesalistofrandompermutationofalljobs,andiftheinputjobsarealreadyinrandomorder,thenthereisnoneedtogenerateanotherrandompermutation.Eachtimeamachineisfreed,thejobatthebeginningofthelistisassignedtothemachine.Maintenanceschemes:Wefirstdefinean“interruption”tobeastoppageofamachineeitherduetomachinefailureortomaintenance.Therearetwomaintenanceschemesingeneral:correctivemaintenance(CM)andpreventivemaintenance(PM).CMexecutesmaintenanceonlyaftereachfailure.Itisassumed(regardlessofthemaintenancescheme)thatthetimespentonmaintenanceafterfailureis