Scalable Distributed Branch and Bound for the Permutation Flow Shop Problem

The study of the Permutation Flow Shop Problem (PFSP) is still of great interest in the community. Reducing the execution time of some very costly instances and/or solving new unresolved instances remain a challenge. The PFSP consists on scheduling n jobs in m machines with make span criterion. Our approach to resolve this problem is based on a parallel distributed solution based on Branch and Bound method. In a previous work, we proposed a first algorithm called GAUUB that distributes the tasks among all processors while updating the new current better Upper Bound (UB). This algorithm GAUUB allowed us, in one hand, to reduce significantly the run times of several benchmark instances and on the other hand, to resolve new instances. In this work, we propose another version of this algorithm (called GALB) that improves the load balancing of tasks among the available processors. Our objective is to have all processors terminating at almost the same time and such that improving run time. In this paper, we will present detailed description of GALB as well as an exhaustive evaluation study based on the well known Tail lard´s Benchmarks and performed on the French national grid (Grid´5000).