Solving the Permutation Flow Shop Problem with Makespan Criterion Using Grids
The optimization of scheduling problems is based on different criteria to optimize. One of the most important criteria is the minimization of completion time of the last task on the last machine called makespan. In this paper, the authors present a parallel algorithm for solving the permutation flow shop problem. Their algorithm is a basic parallel distributed algorithm deployed in a grid of computer (Grid'5000). The objective of this work is minimizing the total makespan of the tasks. Their algorithm uses the exact Branch and Bound method to find optimal solutions of the problem through the distribution of the tasks among the available processors.