A composite heuristic for the no-wait flow shop scheduling

Abstract

Heuristics that explore specific characteristics of the problem are essential to find good solutions in limited computational time for many practical systems. This paper first presents a constructive heuristic, namely improved standard deviation heuristic (ISDH), by combining the standard deviation heuristic (SDH) with the procedure of effective double-job-insert-operator. Then, a composite heuristic, improved standard deviation heuristic with iteration (ISDHI), is proposed using the iteration operator to improve the solutions of the ISDH. Extensive computational experiments are carried out based on a set of well-known flow shop benchmark instances that are considered as no-wait flow shop scheduling instances. Computational results and comparisons show that the ISDHI performs significantly better than the existing ones, and the ISDHI heuristic further improves the proposed constructive heuristics for no-wait flow shop scheduling problem with total flow time criterion.