Scheduling UET-UCT Series-Parallel Graphs on Two Processors - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport Année : 1995

Scheduling UET-UCT Series-Parallel Graphs on Two Processors

Résumé

The scheduling of task graphs on two identical processors is considered. It is assumed that tasks have unit-execution-time, and arcs are associated with unit-communication-time delays. The problem is to assign the tasks to the two processors and schedule their execution in order to minimize the makespan. A quadratic algorithm is proposed to compute an optimal schedule for a class of series-parallel graphs, which includes in particular in-forests and out-forests.
Fichier principal
Vignette du fichier
RR-2566.pdf (305.29 Ko) Télécharger le fichier

Dates et versions

inria-00074115 , version 1 (24-05-2006)

Identifiants

  • HAL Id : inria-00074115 , version 1

Citer

Lucian Finta, Zhen Liu, Ioannis Milis, Evripidis Bampis. Scheduling UET-UCT Series-Parallel Graphs on Two Processors. RR-2566, INRIA. 1995. ⟨inria-00074115⟩
79 Consultations
134 Téléchargements

Partager

Gmail Facebook X LinkedIn More