Multi-Objective Local Search Algorithm-Based Decomposition For Permutation Flow Shop Scheduling Problem

Multi-objective permutation flow shop scheduling problem(MOPFSSP)has been widely studied and applied to many real-world manufacturing fields.It focus on how to make use of limited time and resource and optimize several production objectives simultaneously,leading to improving companies operating efficiency and economic benefit.It has been proved to be NP-hard that cannot be precisely solved by accurate algorithms in limited time.However,swarm intelligence-based evolutionary algorithms and some local search strategies show their great advantages in terms of addressing MOPFSSP,which attracts the great attention and study of researchers at home and abroad.This paper focuses on solving the multi-objective permutation flow shop scheduling problem with and without sequence dependent setup times,denoted by MOPFSSP-SDST and MOPFSSP,respectively,considering the minimization of makespan and total flowtime.The sequence dependent setup times depend on both the current job and the next job in the sequence,such as the time of releasing resources and cleaning machine,which cannot be ignored in real-world scheduling problems.In this paper,a novel multi-objective local search framework based decomposition(MOLSD)is suggested for the two considered problems.MOLSD decomposes the multi-objective problem into certain number of single objective sub-problems using aggregation method and optimizes them simultaneously.Firstly,a problem-specific Nawaz–Enscore–Hoam(NEH)heuristic is used to initialize current population to make the population maintain the high diversity and adaptability.Secondly,a Pareto local search embedded with a heavy perturbation operator is applied to search the promising neighbors of the non-dominated solutions found so far.Thirdly,a fast non-dominated sorting is applied to divide current population into elitist individuals and ordinary individuals that would be experienced different evolution operators.When solving each sub-problem,a single insert based local search(ISLS)and an iterated local search(ILS)strategy are implemented for improving the individual.The ISLS is responsible for exploitation while the ILS is for the exploration,which can enhance the convergence of algorithm and make it better approach the Pareto optimal frontier.In order to avoiding the local optima,a doubling perturbation mechanism,heavy perturbation and light perturbation,are executed on the unimproved elitist individuals and ordinary individuals,respectively.For enhancing the algorithm robustness,a novel restarted method is applied to those individuals that cannot be improved after a number of generations.In the stage of experiment,this paper uses the benchmark data sets to evaluate the performance of proposed algorithm and compare it with several state of the art algorithms on the MOPFSSP and MOPFSSP-SDST,respectively.Firstly,the parameters of MOLSD are tested to find out the best parameter settings and then the effectiveness of some strategies used in MOLSD is evaluated.Finally,several state of the art algorithms are used to compare with MOLSD.The experimental results show that the proposed MOLSD performs best among those algorithms in terms of MOPFSSP and MOPFSSP-SDST.