A hybridmetaheuristicfortheprize-collectingsinglemachinescheduling problem withsequence-dependentsetuptimes

This paperinvestigatesasinglemachineschedulingproblemwithstrongindustrialbackground,named the prize-collectingsinglemachineschedulingproblemwithsequence-dependentsetuptimes.Inthis problem,thereare n candidatejobsforprocessinginasinglemachine,eachjobhasaweight(orprofit) and aprocessingtime,andduringprocessingasymmetricsequence-dependentsetuptimeexists between twoconsecutivejobs.Sincethereisamaximumavailabletimelimitationofthemachine,itis generallyimpossibletocompletetheprocessingofallthecandidatejobswithinthistimelimitation. The objectiveistofindajobprocessingsequenceofmaximaljobweights(orprofits)overasubsetofall candidatejobswhosemakespandoesnotexceedthegiventimelimitation.Thisproblemcanbe consideredasanapplicationoftheorienteeringproblem(OP)inthefieldofdiscretemanufacturing.We formulatethisproblemasamixedintegerlinearprogramming(MILP)modelandproposeahybrid metaheuristiccombiningthestructuresofscattersearchandvariableneighborhoodsearch. Computationalresultsonalargenumberofrandomlygeneratedinstanceswithdifferentstructures show thattheproposedhybridmetaheuristicoutperformsCPLEXandtwometaheuristicsproposedfor the OP.