A meta-heuristic approach for solving the no-wait flow-shop problem

Abstract

No-wait flow-shop scheduling problems refer to the set of problems in which a number of jobs are available for processing on a number of machines in a flow-shop context with the added constraint that there should be no waiting time between consecutive operations of the jobs. The problem is strongly NP-hard. In this paper, the considered performance measure is the makespan. In order to explore the feasible region of the problem, a hybrid algorithm of Tabu Search and Particle Swarm Optimisation (PSO) is proposed. In the proposed approach, PSO algorithm is used in order to move from one solution to a neighbourhood solution. We first employ a new coding and decoding technique to efficiently map the discrete feasible space to the set of integer numbers. The proposed PSO will further use this coding technique to explore the solution space and move from one solution to a neighbourhood solution. Afterwards, the algorithm decodes the solutions to its respective feasible solution in the discrete feasible space and returns the new solutions to the TS. The algorithm is tested by solving a large number of problems available in the literature. Computational results show that the proposed algorithm is able to outperform competitive methods and improves some of the best-known solutions of the considered test problems.

Keywords:

• flow-shop scheduling
• no-wait
• makespan
• tabu search
• particle swarm optimisation
• factoradics

Acknowledgements

This work was supported by the NSERC Discovery grant of the second author. The grant number is 309942-332300.