A genetic scheduling algorithm for distributed heterogeneous computer systems

Authors

  • T.S. Shapovalov
  • V.V. Peresvetov

Keywords:

scheduling
genetic algorithm
distributed heterogeneous computer systems

Abstract

The scheduling problem for distributed heterogeneous computer systems is considered. A genetic algorithm to solve this problem is proposed with consideration of problem-specific information. Some results of numerical experiments are discussed.

New computational technologies

Downloads

Published

2009-07-15

Issue

Vol. 10 (2009): Issue 1.

Section

Section 2. Programming

Author Biographies

T.S. Shapovalov

Computing Center of FEB RAS
• Researcher

V.V. Peresvetov

Computing Center of FEB RAS
• Senior Researcher

References

  1. Коффман Э.Г. Теория расписаний и вычислительные машины. М.: Наука, 1984.
  2. Энциклопедия кибернетики / Отв. ред. В. М. Глушков. 2. Киев: Главная редакция УСЭ, 1974.
  3. Land A.H., Doig A.G. An autmatic method of solving discrete programming problems // Econometrica. 1960. N 28. 497-520.
  4. Lawler E.L., Wood D.E. Branch and bound methods: a survey // Operations Research. 1966. N 14(4). 699-719.
  5. Johnson T.J. R. An alorithm for the resource-constraned project scheduling problem. Doctoral Thesis. Massachusetts Institute of Technology. Cambridge, 1967.
  6. Müller-Merbach H. Ein Verfahren zur Planung des optimalen Betriebsmitteleinsatzes bei der Terminierung von Gross projeckten // Zeitschrift für Wirtschaftliche Fertigung. 1967. N 62. 83-88.
  7. Panwalker S., Iskander W. A survey of scheduling rules // Operations Research. 1977. N 25(1). 45-61.
  8. Davis E.W., Patterson J.H. A comparison of heuristic and optimum solutions in resource-constrained project scheduling // Management Science. 1975. N 21(8). 944-955.
  9. Davis E.W., Heidorn G.E. An algorithm for optimal project scheduling under multiple resource constraints // Management Science. 1971. N 17(12). 803-817.
  10. Hildum D. Flexibility in a knowledge-based system for solving dynamic resource-constrained scheduling problems. Umass CMPSCI Technical Report N 94. University of Massachusetts. Amherst, 1994.
  11. Boctor F.F. Some efficient multi-heuristic procedures for resource-constrained project scheduling // European Journal of Operational Research. 1990. N 49(1). 3-13.
  12. Harvey W.D., Ginsberg M.L. Limited discrepancy search // Proc. of the 14th International Joint Conference on Artificial Intelligence. Montreal: Morgan Kaufmann, 1995. 607-615.
  13. Sampson S.E., Weiss E.N. Local search techniques for the generalized resource-constrained project scheduling problem // Naval Research Logistics. 1993. N 40(5). 665-675.
  14. Patterson J.H. A comparison of exact approaches for solving the multiple constrained resource project scheduling problem // Management Science. 1984. N 30(7). 854-867.
  15. Fox M.S., Smith S.F. ISIS - a knowledge-based system for factory scheduling // Expert Systems. 1984. N 1(1). 25-49.
  16. Smith S.F., Ow P. The use of multiple problem decompositions in time constrained planning tasks // Proc. of the 9th International Joint Conference on Artificial Intelligence. Vol. 2. Calif.: Morgan Kaufmann, 1985. 1013-1015.
  17. Sadeh N. Look-ahead techniques for micro-opportunistic job shop scheduling. PhD Thesis. School of Computer Science, Carnegie Mellon University. Pittsburgh, 1991.
  18. Davis L. Job shop scheduling with genetic algorithms // Proc. of the International Conference on Genetic Algorithms and their Applications. Pittsburgh: Lawrence Erlbaum Associates, 1985. 136-140.
  19. Bagchi S., Uckum S., et al. Exploring problem-specific recombination operators for job shop scheduling // Proc. of the 4th International Conference on Genetic Algorithms. San Mateo: Morgan Kaufmann, 1991. 10-17.
  20. Syswerda G. The application of genetic algorithms to resource scheduling // Proc. of the 4th International Conference on Genetic Algorithms. San Mateo: Morgan Kaufmann, 1990. 502-508.
  21. Hilliard M.R., Liepins G.E., et al. Machine learning applications to job shop scheduling // Proc. of the AAAI-SIGMAN Workshop on Production Planning and Scheduling. New York: ACM, 1988. 728-737.
  22. Pugliese F., Talia D., Yahyapour R. Modeling and supporting grid scheduling // Journal of Grid Computing. 2008. N 6/2. 195-213.
  23. Dovgan A., Özgüner F. Genetic algorithm based scheduling of meta-tasks with stochastic execution times in heterogeneous computing systems // Cluster Computing. 2004. N 7. 177-190.
  24. Buyya R. Economic-based distributed resource management and scheduling for grid computing. Ph. D. Thesis. School of Computer Science and Software Engineering. Monash University. Melbourne, 2002.
  25. Derbal Y. Entropic grid scheduling // Journal of Grid Computing. 2006. N 4(4). 373-394.
  26. Junwei C., Spooner D., Turner J.D., Jarvis S., Kerbyson D.J., Saini S., Nudd G. An agent-based resource management system for grid computing // Proc. of the 2nd IEEE/ACM International Symposium on Cluster Computing and the Grid. Washington: IEEE Computer Society, 2002. 350-350.
  27. Braun T.D., Siegel H.J., Beck N., Boloni L.L., Maheswaran M., Reuther A.I., Robertson J.P., Theys M.D., Yao B., Hensgen D., Freund R.F. A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems // Journal of Parallel and Distributed Computing. 2001. N 61(6). 810-837.
  28. Топорков В.В. Модели распределенных вычислений. М.: Физматлит, 2004.
  29. Bailey D., Barszcz E., Barton J., et al. The NAS parallel benchmarks. Technical Report N RNR-94-007. Washington, 1994.
  30. Hart W.E. Adaptive global optimization with local search. Ph. D. Thesis. University of California. San Diego, 1994.
  31. Пересветов В.В., Сапронов А.Ю., Тарасов А.Г., Шаповалов Т.С. Удаленный доступ к вычислительному кластеру ВЦ ДВО РАН // Вычислительные технологии. 2006. 11. 2006. 45-51.
  32. Пересветов В.В., Сапронов А.Ю., Тарасов А.Г. Вычислительный кластер бездисковых рабочих станций. Препринт № 83 ВЦ ДВО РАН. Хабаровск, 2005.
  33. Щерба С.И., Пересветов В.В. Сравнительный анализ эффективности программного обеспечения для вычислительных кластеров // Тр. Межрегиональной научно-практической конференции «Информационные и коммуникационные технологии в образовании и научной деятельности» (г. Хабаровск, 21-23 мая 2008). Хабаровск: Изд-во Тихоокеанского гос. ун-та, 2008. 363-369.