| Minimum makespan scheduling of Flow Shops with Multiple Processors (FSMPs) is classified as NP complete. Thus, the FSMP largely depends on strong heuristics to develop solutions to makespan scheduling instances. An FSMP consists of m stages wherein each stage has one or more processors through which n jobs are scheduled. This thesis presents a heuristic based on the lower bound proposed by Santos, Hunsucker, and Deal (1995a) in order to determine good makespan solutions in the FSMP environment. In order to evaluate the proposed heuristic, its performance is compared to makespans obtained via the use of modified flow shop heuristics. Results show that the proposed heuristic is indeed a strong heuristic for the FSMP and it provides makespans that are better than those provided by some of the already existing pure flow shop heuristics that have been adapted for the FSMP environment.;Keywords. Flow shop with multiple processors, scheduling, makespan, lower bound. |
