A multi-stage parallel-processor flowshop problem with minimum flowtime

Most algorithms on flowshop scheduling assume that every stage has a single processor or machine only. With a view to achieve the practical objective of minimizing total flowtime, a branch-and-bound algorithm for obtaining a permutation schedule for the multi-state flowshop with parallel processors is presented. Computational experience with the proposed algorithm and the existing single-processor algorithms reveals that most of the parallel-processor problems are solved faster and easier. The performance of the existing procedures is also evaluated in the parallel-processor environment. Since the flowshop scheduling problem is NP-complete, a heuristic algorithm for scheduling in a two-stage parallel-processor flowshop is proposed. The heuristic solutions, were compared with the optimal solutions given by the proposed branch-and-bound method, are found to be near-optimal.