Access Restriction

Author Billionnet, A. ♦ Costa, M. C. ♦ Sutter, A.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1992
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Lagrangean relaxation ♦ Branch-and-bound algorithm ♦ Interprocessor communication ♦ Quadratic 0-1 optimization ♦ Task allocation
Abstract This paper presents an efficient algorithm to solve one of the task allocation problems. Task assignment in an heterogeneous multiple processors system is investigated. The cost function is formulated in order to measure the intertask communication and processing costs in an uncapacited network. A formulation of the problem in terms of the minimization of a submodular quadratic pseudo-Boolean function with assignment constraints is then presented. The use of a branch-and-bound algorithm using a Lagrangean relaxation of these constraints is proposed. The lower bound is the value of an approximate solution to the Lagrangean dual problem. A zero-duality gap, that is, a saddle point, is characterized by checking the consistency of a pseudo-Boolean equation. A solution is found for large-scale problems (e.g., 20 processors, 50 tasks, and 200 task communications or 10 processors, 100 tasks, and 300 task communications). Excellent experimental results were obtained which are due to the weak frequency of a duality gap and the efficient characterization of the zero-gap (for practical purposes, this is achieved in linear time). Moreover, from the saddle point, it is possible to derive the optimal task assignment.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1992-07-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 39
Issue Number 3
Page Count 17
Starting Page 502
Ending Page 518

Open content in new tab

   Open content in new tab
Source: ACM Digital Library