Bottleneck-focused scheduling for a hybrid flowshop

Abstract

This paper focuses on a scheduling problem in a hybrid flowshop in which there are serial workstations, each with identical parallel machines. The objective of the problem is to minimize total tardiness of a given set of jobs. We suggest a new type of heuristic method, called a bottleneck-focused algorithm, for the problem. In the algorithm, a schedule for a bottleneck workstation is first constructed and then schedules for other workstations are constructed based on the schedule for the bottleneck. Since the bottleneck workstation may not be the first workstation in the hybrid flowshop, ready times of operations at the bottleneck workstation depend on the schedule at its upstream workstations. In the algorithm, the ready times are iteratively updated using information of the schedule obtained in the previous iterations. To evaluate the performance of the suggested algorithm, computational experiments are performed on a real data set and randomly generated test problems. Results of the experiments show that the suggested algorithm outperforms various other heuristics.