A Load Balanced Distributed Algorithm to Solve the Permutation Flow Shop Problem Using the Grid

This paper deals with solving the permutation flow shop problem (PFSP) which is an NP-hard scheduling problem using grid computing. As the sequential resolution of this problem can be sometimes impossible on a single machine and especially for instances of large data, we are interested in this work by solving the PFSP using parallel programming. In a previous paper, we presented a parallel algorithm for solving the PFSP on the grid called GAUUB. The GAUUB algorithm uses the Branch and Bound method to find optimal solutions of the problem and distributes the tasks among all processors. In this paper, we present a new algorithm called GALB, based on a parallelization strategy ensuring better load balancing between the processors and therefore, better efficiency of the algorithm. Computational results of our new algorithm performed on the grid showed good results and significant improvements of our initial algorithm thanks to our load balancing technique.