A shifting bottleneck approach for a parallel-machine flowshop scheduling problem

This paper considers a scheduling problem of minimizing the maximum lateness for a parallel-machine flowshop with m stages, each of which consists of one or more identical parallel machines. We propose a heuristic algorithm being based on a shifting bottleneck approach which decomposes the parallel-machine flowshop problem into m parallel-machine scheduling problems to be solved one by one. Each parallel-machine problem is approximately solved by applying a property of its reversibility in the proposed heuristic. To evaluate performance of the proposed heuristic, it is numerically compared with Wittrock's algorithm for a real production line, and with Santos et al.'s global lower bound for test problem instances randomly generated. The results obtained strongly suggest that the proposed heuristic produces optimal or quite near optimal solutions within short, computational time with high probability.