Stochastic scheduling of a meta-task in heterogeneous distributed computing

Doğan A., Özgüner F.

International Conference on Parallel Processing Workshops, ICPPW 2001, Valencia, İspanya, 3 - 07 Eylül 2001, cilt.2001-January, ss.369-374 identifier identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Cilt numarası: 2001-January
  • Doi Numarası: 10.1109/icppw.2001.951974
  • Basıldığı Şehir: Valencia
  • Basıldığı Ülke: İspanya
  • Sayfa Sayıları: ss.369-374
  • Anahtar Kelimeler: Biological cells, Computational modeling, Distributed computing, Genetic algorithms, Heuristic algorithms, Processor scheduling, Random variables, Scheduling algorithm, Stochastic processes, Stochastic systems
  • Anadolu Üniversitesi Adresli: Hayır

Özet

© 2001 IEEE.The fact that the scheduling problem is NP-complete has motivated the development of many heuristic scheduling algorithms. These heuristic algorithms often neglect the stochastic nature of tasks' execution times. Contrary to existing heuristics, in this study, tasks' execution times are treated as random variables and the stochastic scheduling problem is formulated accordingly. Using this formulation, it is theoretically shown that current deterministic scheduling algorithms may perform poorly in a real computing environment. In order to support the theoretical foundations, a genetic algorithm based scheduling algorithm is devised to make scheduling decisions either stochastically or deterministically by changing only the fitness function of chromosomes. The simulation studies conducted show that deploying a stochastic scheduling algorithm instead of a deterministic one can improve the performance of meta-tasks in a heterogeneous distributed computing system.