Research on the scheduling algorithms of flexible manufacturing systems

This paper considers hybrid flow shop scheduling with two parallel machines at a single stage, where a set of jobs needs processing on one of two machines. Job preemption is not allowed. Finding a minimum makespan schedule is strongly NP-hard. Some efficient heuristics have been proposed in the literature. According to the characteristics of flexible manufacturing systems, and using a branch-and-bound algorithm, two theorems about the principle of choice are proposed. Further, heuristic scheduling algorithms about sequencing and assigning the jobs to machines are developed for the hybrid flowshop by using the two theorems. Finally, computational experiments are described to illustrate the effectiveness of these algorithms.