Dynamic search tree decomposition for balancing assembly lines by parallel search

Dynamic search tree decomposition for balancing assembly lines by parallel search

0.00 Avg rating0 Votes
Article ID: iaor2004114
Country: United Kingdom
Volume: 41
Issue: 7
Start Page Number: 1413
End Page Number: 1430
Publication Date: Jan 2003
Journal: International Journal of Production Research
Authors:
Keywords: programming: mathematical
Abstract:

We consider the simple assembly line balancing problem of type 1 (SALB-1). Although several branch-and-bound algorithms have been developed for optimally solving the SALB-1, until now to the best of our knowledge no parallel approach has been presented for this classical problem. In this paper we propose a parallel algorithm or solving the SALB-1. The parallel approach is based on a competitive serial algorithm. The parallel approach benefits from the substitution of a powerful but memory-intensive dominance concept through solution characteristics. Using the master–slave principle the master dynamically generates subproblems which are, upon request, assigned to the slaves for evaluation. The subproblems depend on previously assigned and on previously evaluated subproblems. The characteristics allow each slave to decide on potential dominance without requiring information from another slave or the master. The algorithm has been coded in GNU C using the Parallel Virtual Machine to allow communication. Experimental studies have been performed on a simulated cluster of personal computers. Benchmark sets from the literature served as a testbed. The computational results are extremely promising. It seems that the SALB-1 is an ideal application of parallel search.

Reviews

Required fields are marked *. Your email address will not be published.