A Grid-enabled Branch and Bound Algorithm for Solving ...

A Grid Enabled Branch And Bound Algorithm For Solving -ppt Download

  • Date:25 Jun 2020
  • Views:14
  • Downloads:0
  • Size:405.00 KB

Share Presentation : A Grid Enabled Branch And Bound Algorithm For Solving

Download and Preview : A Grid Enabled Branch And Bound Algorithm For Solving

Report CopyRight/DMCA Form For : A Grid Enabled Branch And Bound Algorithm For Solving


Transcription:

A Grid enabled Branch and BoundAlgorithm for Solving ChallengingCombinatorial OptimizationAuthors M Mezmaz N Melab andE G Talbi.
Presented by Saad Alhowaimel Table of Content Introduction The Proposed Approach Concepts and The Proposed Grid enabled Parallel B B.
Experimentation Introduction The problem is NP hard and complex The Branch and Bound reduce the computation time but notexploring time .
B B components branching Bounding selection elimination.
Parallelism on gird load balancing fault tolerance termination detection global information sharing.
The Proposed Approach Concepts and Construct a permutation tree and explore it using a DFS strategy List of active nodes Explored but not yet visited Cover all the nodes which can be potentially explored from each node.
of the list Algorithm stops once the list of active nodes becomes empty Used for exploration Interval Optimize communication.
Check pointing operations Fold operator Deduces an interval from a list of active nodes Unfold operator Deduces a list of active nodes from an interval.
The Proposed Approach Concepts and Node weight The Proposed Approach Concepts and Node Number The Proposed Approach Concepts and.
Node range The Proposed Approach Concepts and Fold Operator deduces an interval from a list of active nodes The Proposed Approach Concepts and.
Fold Operator The Proposed Approach Concepts and Unfold Operator Deduces a list of active node form an interval The Proposed Grid enabled Parallel.
Farmer Worker Approach Farmer One processor play the role of frame Keep a copy of all unexplored intervals Worker.
All other processors Each process explores anBoth worker and farmer mange the best solution found so far The Proposed Grid enabled Parallel Fault Tolerance .
The coordinator manages a possible failure of thefarmer by periodically saving in tow files INTERVALS It has a copy of all the intervals SOLUTION .
It has the global best solution The Updating process Let A B be an interval being explored in a B B process and A B its copy in INTERVALS Exploring increase A and branching decrease B .
The Proposed Grid enabled Parallel Load Balance The coordinator assign an interval to B B processusing two operator Selection operator .
select an interval from INTERVALS Partitioning operator divide an interval A B to A C and C B The holder process keeps A C and requesting process keeps C B The partitioning point C depend on the power and availability of.
the processors At the beginning C is equal to A Any interval that smaller than parameterized threshold isduplicated which speed up the search in termination phase The Proposed Grid enabled Parallel.
Termination Detection At the beginning INTERVALS has only one interval During exploration the number of B B process isequal to the number of interval while its sizecontinuously decreases .
The INTERVALS size is the sum of all the length ofits interval Any empty interval the beginning is higher thanthe end is removed automatically The algorithm stop once the INTERVALS is empty .
The Proposed Grid enabled Parallel Solution Sharing The solution sharing is done by using SOLUTION It contains the global optimal solution Each B B process manages its own local optimal.
The objective is to reflect any improvement of anylocal optimal solution in all the other B B processes A B B process initializes its local optimal solution by Immediately informs the coordinator each time its localsolution is improved.
Regularly reads SOLUTION to update its local optimal Experimentation The permutation flow shop problem One of the important problem in industrial areas the problem is.
Where The position of the machines is fixed A machine can handle only one job at a time Experimentation The experimentation on grid .
A problems of 50 jobs on 20 machines Ta0561 This instance has never been solved optimally The best known solution of Ta056 has a cost of 3681with near optimal resolution method It is made up of 1889 processors belonging to 9.
Three clusters belong to three different educationdepartments of University de Lille Six clusters belong Grid 5000 Experimentation Experiment Result .
Two runs have been performed and the optimal solution isfound with a cost equal to 3697 First experiment The upper bound set with 3681 average of processors 500 with a peak of 1245 processors .
Experiment time One month and three weeks Second experiment The upper bound set with 3680 average of processors 328 with a peak of 1195 processors Experiment time is 25 days .
More than 2 million check pointing operations About 6 billion nodes were explored a cumulative computation time of about 22 years Questions .
The Branch and Bound reduce the computation time, but not exploring time. B&B components: branching Bounding selection elimination Parallelism on gird: load balancing fault tolerance termination detection global information sharing The Proposed Approach: Concepts and Operators Construct a permutation tree and explore it using a DFS strategy ...

Related Presentations