Size-reductionheuristicsfortheunrelatedparallelmachines schedulingproblem

In thispaperwestudytheunrelatedparallelmachinesproblemwhere n independentjobsmustbe assignedtooneoutof m parallelmachinesandtheprocessingtimeofeachjobdiffersfrommachineto machine.Wedealwiththeobjectiveoftheminimisationofthemaximumcompletiontimeofthejobs, usuallyreferredtoasmakespanor Cmax. Thisisatypeofassignmentproblemthathasbeenfrequently studiedinthescientificliteratureduetoitsmanypotentialapplications.Weproposeasetof metaheuristicsbasedonasize-reductionoftheoriginalassignmentproblemthatproducesolutionsof very goodqualityinashortamountoftime.Theunderlyingideaistoconsideronlyafewofthebest possiblemachineassignmentsforthejobsandnotallofthem.Theresultsaresimple,yetpowerful methods.Wetesttheproposedalgorithmswithalargebenchmarkofinstancesandcomparethemwith currentstate-of-the-artmethods.Inmostcases,theproposedsize-reductionalgorithmsproduceresults that arestatisticallyproventobebetterbyasignificantmargin.