A static multiprocessor scheduling algorithm for arbitrary directed task graphs in uncertain environments

Jun Yang*, Xiaochuan Ma, Chaohuan Hou, Zheng Yao

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

4 Citations (Scopus)

Abstract

The objective of a static scheduling algorithm is to minimize the overall execution time of the program, represented by a directed task graph, by assigning the nodes to the processors. However, sometimes it is very difficult to estimate the execution time of several parts of a program and the communication delays under different circumstances. In this paper, an uncertain intelligent scheduling algorithm based on an expected value model and a genetic algorithm is presented to solve the multiprocessor scheduling problem in which the computation time and the communication time are given by stochastic variables. In simulation examples, it shows that the algorithm performs better than other algorithms in uncertain environments.

Original languageEnglish
Title of host publicationAlgorithms and Architectures for Parallel Processing - 8th International Conference, ICA3PP 2008, Proceedings
Number of pages12
PublisherSpringer
Publication date2008
Pages18-29
ISBN (Print)9783540695004
DOIs
Publication statusPublished - 2008
Externally publishedYes
Event8th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2008 - , Cyprus
Duration: 9 Jun 200811 Jun 2008

Conference

Conference8th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2008
Country/TerritoryCyprus
Period09/06/200811/06/2008
SeriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5022 LNCS
ISSN0302-9743

Keywords

  • Genetic algorithm
  • Parallel processing
  • Scheduling
  • Stochastic programming

Cite this