AN EVALUATION OF SEQUENCING HEURISTICS IN FLOW SHOPS WITH MULTIPLE PROCESSORS

In this paper we investigate scheduling procedures which seek to minim ize the makespan in the static flow shop with multiple processors (FSM P) scheduling environment. The FSMP (or flexible flow shop) problem is characterized as the scheduling of jobs in a flow shop environment th at has, at any stage, multiple copies of a processor. A previous work is discussed in which all permutations of the job indices are used in developing a first stage queuing sequence-the remaining stages are que ued in a FIFO manner. The previous study shows, on a set of 653 FSMP p roblems with known optimal solutions, that choosing the best initial s equence with a FIFO progression produces good, often near-optimal, mak espans. While FIFO scheduling is efficient, searching through all perm utations is not. This study tries to answer the question posed in that work which suggests a focus on the development of a ''good'' initial sequence. Four previously existing pure flow shop sequencing methods a re now utilized for use in FSMP application. Herein, a pure how shop c oncerns the environment where every stage has exactly one processor. A n analysis of these methods using the same set of 653 problems is disc ussed. Since two of the methods obtain an optimal makespan in at least one-third of the cases and the other two obtain optimality in 29 and 20% of the cases, this study indicates that it is desirable to utilize the pure flow shop methods in the FSMP environment. Copyright (C) 199 6 Elsevier Science Ltd