A novelhybriddiscretedifferentialevolutionalgorithmforblockingflowshop scheduling problems

This paperproposesanovelhybriddiscretedifferentialevolution(HDDE)algorithmforsolvingblocking flow shopschedulingproblemstominimizethemaximumcompletiontime(i.e.makespan).Firstly,inthe algorithm, theindividualsarerepresentedasdiscretejobpermutations,andnewmutationandcrossover operators aredevelopedforthisrepresentation,sothatthealgorithmcandirectlyworkinthediscrete domain. Secondly,alocalsearchalgorithmbasedoninsertneighborhoodstructureisembeddedinthe algorithm tobalancetheexplorationandexploitationbyenhancingthelocalsearchingability.Inaddi- tion, aspeed-upmethodtoevaluateinsertneighborhoodisdevelopedtoimprovetheefficiencyofthe whole algorithm.Computationalsimulationsandcomparisonsbasedonthewell-knownbenchmarkin- stances ofTaillard[Benchmarksforbasicschedulingproblems.EuropeanJournalofOperationalResearch 1993;64:278–285], bytreatingthemasblockingflowshopprobleminstanceswithmakespancriterion, are provided.ItisshownthattheproposedHDDEalgorithmnotonlygeneratesbetterresultsthanthe existing tabusearch(TS)andTSwithmulti-moves(TS + M) approachesproposedbyGrabowskiand Pempera [Thepermutationflowshopproblemwithblocking.Atabusearchapproach2007;35:302–311], but alsooutperformsthehybriddifferentialevolution(HDE)algorithmdevelopedbyQianetal.[An effective hybridDE-basedalgorithmformulti-objectiveflowshopschedulingwithlimitedbuffers.Com- puters andoperationsresearch2009;36(1):209–233]intermsofsolutionquality,robustnessandsearch efficiency. Ultimately,112outof120bestknownsolutionsprovidedbyGrabowskiandPempera[The permutation flowshopproblemwithblocking.Atabusearchapproach2007;35:302–311]andRonconi [A branch-and-boundalgorithmtominimizethemakespaninaflowshopproblemwithblocking.Annals of OperationsResearch2005;138(1):53–65]arefurtherimprovedbytheproposedHDDEalgorithm.