An LC branch-and-bound algorithm for the module assignment problem
Resource
Information Processing Letters 32 (2): 61-71
Journal
Information Processing Letters
Journal Volume
32
Journal Issue
2
Pages
61-71
Date Issued
1989
Date
1989
Author(s)
Abstract
Distributed processing has been a subject of recent interest due to the availability of computer networks. Over the past few years it has lead to the identification of several challenging problems. One of these is the problem of optimally distributing program modules over a distributed processing system. In this paper we present an LC (Leas Cost) branch-and-bound algorithm to find an optimal assignment that minimizes the sum of execution costs and communication costs. Experimental results show that, for over half of the randomly generated instances, the saving rates exceed 99%. Moreover, it appears that the saving rates rise as the size of the instances increases. Finally, we also introduce two reduction rules to improve the efficiency of the algorithm for some special cases. © 1989.
Subjects
Branch-and-bound algorithms; distributed processing system; module assignment problem
Other Subjects
Computer Systems, Digital--Distributed; Optimization; Branch-and-Bound Algorithms; Module Assignment Problem; Optimal Assignment; Computer Programming
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
04.pdf
Size
706.75 KB
Format
Adobe PDF
Checksum
(MD5):0a0067e43a32c7c1c95d2e4ae3f7a49e