A nonlinear multiprocessor scheduling problem

Abstract

The problem addressed in this research is that of assigning modules of a computer program among processors in a distributed computer network having functionally similar nodes. The assignment is to be made in such a way as to take advantage of particular efficiencies of some processors for certain modules while minimizing the costs of communication between modules that are assigned to different processors. The problem is formulated as a zero-one nonlinear programming problem. A graph model is developed which provides a state-space representation of the problem, and a shortest path labeling algorithm is given which produces an assignment. A heuristic procedure is described which is a non-backtracking branch-and-bound technique, using a local neighborhood search at each stage. Suboptimal assignments are produced, but at considerable reduction in computation time and memory requirements, since only selected portions of the search graph are explored. Finally, an iterative transformation is defined on the solution space. A fixed point theorem is proved, guaranteeing that this procedure converges to a local optimum. Because this problem is known to belong to the class of NP-complete problems, the suboptimal assignments that are generally produced by these algorithms are considered acceptable. The shortest path algorithm yields optimal solutions when the search graph exhibits certain identifiable structural properties. The algorithms are implemented in computer programs and computational results are reported.