Iterative Scheduling Algorithms Based
on the Subdivision of the Solution Space into Domains

A. V. Kalashnikov and V. A. Kostenko

Laboratory of Computational Complexes, Faculty of Computational Mathematics and Cybernetics,
Moscow State University, Moscow, 119991 Russia

e-mail: akm@vmik.ru

Received September 4, 2007

Abstract—Iterative multiprocessor scheduling algorithms are considered. The iterative algorithms
make it possible to solve scheduling problems for a wide class of computer architectures but are very
intricate from the computational point of view. To simplify the iterative algorithms, we propose an
approach to their construction based on the subdivision of the space of correct schedules into disjoint
domains, namely, an algorithm for constructing domains is proposed, the operations of the schedule
transformations closed within the domains are introduced, and a technique for cutting off domains is
developed. The approach developed also makes it possible to construct parallel algorithms with a low
traffic of the exchange between parallel processes.

DOI:10.3103/S0278641908030096

Pleiades Publishing home page | journal home page | top

If you have any problems with this server, contact webmaster.