Scheduling hybrid flowshops to minimize maximum tardiness or maximum completion time

Abstract

The problem of scheduling independent jobs on several serial workshops consisting of identical parallel machines is studied. Each job is processed by one machine in each workshop. This workshop environment is called a hybrid Flowshop. Each job has its own due-date and the objective is to minimize maximum tardiness or maximum completion time. Given that the problem is NP-hard, a set of list algorithms is developed to solve it. To evaluate the quality of these heuristics, lower bounds on the optimal solution have been derived and compared to the value of the heuristics on 1920 problems. Our results indicate that a heuristic based on Nawaz et al. (1983) method outperformed the other approaches.