Earticle

초록

영어

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, we present a parallel algorithm for solving the permutation flow shop problem. Our 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. Our 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. Computational results of our parallel algorithm using well known Taillard’s benchmarks, showed encouraging results. In particular, we succeeded to solve two new instances to optimality which had never been resolved before neither in sequential nor in parallel [29].

목차

Abstract
 2. The Permutation Flow Shop Problem (PFSP)
  2.1. Presentation
  2.2. Example of the PFSP
  2.3. Complexity
  2.4 Solving the PFSP by the Branch & Bound Method
 3. Parallel B&B Algorithms
  3.1. Introduction
  3.2. State of the Art
 4. Our Gridified Algorithm Updating the Upper Bound (GAUUB)
 5. Computational Study
 6. Conclusion and Perspectives
 References

키워드

저자

• Samia kouki [ Ecole Supérieure des Sciences et Techniques de Tunis, Research Laboratory UTIC. University of Tunis, Tunisia. ]
• Mohamed Jemni [ Ecole Supérieure des Sciences et Techniques de Tunis, Research Laboratory UTIC. University of Tunis, Tunisia. ]
• Talel Ladhari [ ROI – Combinatorial Optimization Research Group, Polytechnic School of Tunisia, Princess Fatimah Al-Nijriss Research Chair for Advanced Manufacturing Technologies, Department of Industrial Engineering, College of Engineering, King Saud University ]

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  International Journal of Grid and Distributed Computing

• 간기

  격월간

• pISSN

  2005-4262

• 수록기간

  2008~2016

• 십진분류

  KDC 505 DDC 605