Scheduling a two-stage hybrid flowshop with separable setup and removal times

This paper considers the two-stage flowshop scheduling problem where each stage consists of several identical parallel machines and the setup and removal times of each job at each stage are separated from the processing times. A polynomial optimization algorithm is developed for the special case where the first stage contains only one machine and the number of identical parallel machines at the second stage is equal to or greater than the total number of jobs. In view of the NP-completeness of this problem, four heuristic algorithms are developed for the case where there is one machine at stage 1 and the number of identical parallel machines at the second stage is less than the total number of jobs. The proposed heuristic algorithms are empirically tested to determine their effectiveness in finding an optimal schedule.