A new heuristic for minimal makespan in flow shops with multiple processors and no intermediate storage

The general scheduling problem in a flow shop with multiple processors (FSMP) is characterized by the processing of n jobs through m stages with one or more processors at each stage. The assumption is generally made that there is unlimited storage available between stages. This paper changes that assumption so there is no intermediate storage (NIS) and blocking between stages. This paper is concerned with the minimization of the makespan in an FSMP with no intermediate storage (FSMP-NIS) with identical multiple processors at each stage. This research focuses on the development of a new heuristic for minimizing the makespan in an FSMP-NIS to be used in, but not limited to, this environment. Experiments are performed to test the effectiveness of the new heuristic and other comparison heuristics for small and large-sized problems. Results indicate that the new heuristic performs statistically better (over the data used) than other commonly used heuristics. (C) 2003 Elsevier B.V. All rights reserved.