A new optimal algorithm for the permutation flow-shop problem and its parallel implementation

This paper describes a new parallel algorithm for solving n-job, m-machine flow-shop problems. The algorithm is basically a parallelization of the usual branch-and-bound method. It also takes advantage of all search method to keep high efficiency of parallel processing, when the sub-problem becomes smaller than certain size. It is shown that its implementation on both nCUBE2 and LUNA88k2 gives very good performance characteristics.