Abstract
A new approach to develop parallel and distributed scheduling algorithms for multiprocessor systems is proposed. Its main innovation lies in evolving a decomposition of the global optimization criteria. For this purpose a program graph is interpreted as a multi-agent system. A game-theoretic model of interaction between agents is applied. Competetive coevolutionary genetic algorithm, termed loosely coupled genetic algorithm, is used to implement the multi-agent system. To make the algorithm trully distributed, decomposition of the global optimization criterion into local criteria is proposed. This decomposition is evolved with genetic programming. Results of succesive experimental study of the proposed algorithm are presented.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
I. Ahmad (Ed.). Special Issue on Resource Management in Parallel and Distributed Systems with Dynamic Scheduling: Dynamic Scheduling, Concurrency: Practice and Experience, 7(7), 1995
I. Ahmad and Y. Kwok, A Parallel Approach for Multiprocessing Scheduling. 9th Int. Parallel Processing Symposium, Santa Barbara, CA, April 25–28, 1995
V. C. Barbosa, An Introduction to Distributed Algorithms, The MIT Press, 1996
J. Błażewicz, M. Dror and J. Węglarz, Mathematical Programming Formulations for Machine Scheduling: A Survey, European Journal of Operational Research 51, pp. 283–300, 1991
A. P. Fraser, Genetic Programming in C++. A manual in progress for gpc++, a public domain genetic programming system, Technical Report 040, University of Salford, Cybernetics Research Institute, 1994
D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, Reading, MA, 1989
J. R. Koza, Genetic Programming, MIT Press, 1992
F. Seredynski, Competitive Coevolutionary Multi-Agent Systems: The Application to Mapping and Scheduling Problems, Journal of Parallel and Distributed Computing, 47, 1997, 39–57.
F. Seredynski, Discovery with Genetic Algorithm Scheduling Strategies for Cellular Automata, in Parallel Problem Solving from Nature-PPSNV, A. E. Eiben, T. Back, M. Schoenauer and H.-P. Schwefel (Eds.), Lecture Notes in Computer Science 1498, Springer, 1998, 643–652.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1999 Springer-Verlag
About this paper
Cite this paper
Seredyński, F., Koronacki, J., Janikow, C.Z. (1999). Distributed scheduling with decomposed optimization criterion: Genetic programming approach. In: Rolim, J., et al. Parallel and Distributed Processing. IPPS 1999. Lecture Notes in Computer Science, vol 1586. Springer, Berlin, Heidelberg . https://doi.org/10.1007/BFb0097900
Download citation
DOI: https://doi.org/10.1007/BFb0097900
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65831-3
Online ISBN: 978-3-540-48932-0
eBook Packages: Springer Book Archive