DocumentCode :
3758156
Title :
A parallel algorithm for solving the PFSP with load balancing on the grid: An empirical study
Author :
Samia Kouki;Mohamed Jemni;Talel Ladhari
Author_Institution :
Research Lab. LaTICE, ENSIT, University of Tunis Tunis, Tunisia
fYear :
2015
Firstpage :
1
Lastpage :
6
Abstract :
Solving NP-hard combinatorial optimization problems by exact search methods, such as Branch-and-Bound, may degenerate to complete enumeration. For that reason, exact approaches limits us to solve only small or moderate size problem instances, due to the exponential increase in CPU time when problem size increases. One of the most promising ways to reduce significantly the computational burden of sequential versions of Branch-and-Bound is to design parallel versions of these algorithms which employ several processors. This paper describes a parallel Branch-and-Bound algorithm called GALB for solving the classical permutation flowshop scheduling problem as well as its implementation on a Grid computing infrastructure. The experimental study of our distributed parallel algorithm gives promising results and shows clearly the benefit of the parallel paradigm to solve large-scale instances in moderate CPU time.
Keywords :
"Program processors","Load management","Benchmark testing","Algorithm design and analysis","Parallel algorithms","Optimal scheduling"
Publisher :
ieee
Conference_Titel :
Information & Communication Technology and Accessibility (ICTA), 2015 5th International Conference on
Type :
conf
DOI :
10.1109/ICTA.2015.7426935
Filename :
7426935
Link To Document :
بازگشت