A non-delayedrelax-and-cutalgorithmforschedulingproblemswithparallel machines, duedatesandsequence-dependentsetuptimes

Consider theproblemofschedulingasetofjobstobeprocessedexactlyonce,onanymachineofasetof unrelated parallelmachines,withoutpreemption.Eachjobhasaduedate,weight,and,foreachmachine, an associatedprocessingtimeandsequence-dependentsetuptime.Theobjectivefunctionconsideredis to minimizethetotalweightedtardinessofthejobs. This workproposesanon-delayedrelax-and-cutalgorithm,basedonaLagrangeanrelaxationofatime indexed formulationoftheproblem.ALagrangeanheuristicisalsodevelopedtoobtainapproximate solutions. Using theproposedmethods,itispossibletoobtainoptimalsolutionswithinreasonabletimeforsome instances withupto180jobsandsixmachines.Forthesolutionsforwhichitisnotpossibletoprove optimality, interestinggapsareobtained.