A Hybrid Search Algorithm For Solving The Complex Flowshop Scheduling Problem

In this paper,we propose a novel heuristic algorithm,a hybrid local search algorithm,to solve the complex flowshop scheduling problem.It contains the flowshop scheduling problem with sequence dependent setup time(SDST)with the single objective of minimizing the makespan and the ordinary flowshop scheduling problem with multi-object(MOPFSSP).Quite a lot of papers demonstrate that they are NP-hard problems with a wide range of engineering and theoretical background.Firstly,a local search algorithm based on population(PLS)is used to solve the flowshop scheduling problem with sequence dependent setup time.The innovation points of this algorithm are a global search and an inserted local search.In the initial stage of the algorithm,a problem-specific NEH algorithm is applied to initialize the current population.In the algorithm,the global search based on a heavy interference operation is employed to update the whole population.At the same time,an inserted local search is employed to improve the quality of the individuals in the population with a certain probability.In order to verify the performance of the algorithm,this paper uses benchmark data to compare the proposed algorithm with other optimization algorithms.The experimental results show that the proposed algorithm has better performance and efficiency than other algorithms.Secondly,a hybrid search algorithm based on the biogeography optimization algorithm(BBO_HS)is used to solve the multi-objective basic flowshop scheduling problem.The algorithm proposed in this paper is based on the framework of biogeography optimization algorithm combined with local search algorithms,including the global search and the inserted local search.The strategy for updating the habitats is also mixed.Therefore this algorithm has a faster convergence rate and a diversity of habitats.Similarly,in order to prove the property of the algorithm,the benchmark data for the ordinary flowshop problem is adopted.The result shows that the proposed algorithm improves the quality of solutions more effectively and efficiently than other multi-objective algorithms.