Constructive and composite heuristic solutions to the P//ΣCi scheduling problem

In this paper, we study the permutation flowshop scheduling problem with the criterion of minimising the total flow time. We propose a new constructive heuristic procedure to solve the problem. This procedure is flexible in the computational effort required, as it can be adjusted to the requirements of the problem. We combine this procedure with local search methods, whose computational requirements can also be varied, to study the efficiency and effectiveness of different ways of forming composite solution methods. Computational experiments on standard benchmark problems are carried out. The results show that the new heuristic performs significantly better than previous ones and that combining constructive and search heuristics not only further improves the solution quality but also saves computation time. Discussions on the results are provided and future research is suggested. (C) 2001 Elsevier Science B.V. All rights reserved.