Heuristics for generalized task system

Chung W. Ng, Joseph Y.T. Leung, G. Young

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

With the advance of parallel processors, Generalized Task System (GTS) has been proposed to capture the notion of parallelism within a single task Based on this model, the complexity of minimizing the total (or average) flaw time for the preemptive and non-preemptive scheduling discipline has been proved to be binary NP-hard even when there are only two processors and each task has exactly two independent subtasks. In this paper, we propose a preemptive approximation algorithm to minimize the total flow time and its worst-case and average performance analyzed.

Original languageEnglish (US)
Title of host publicationProceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA 2003
EditorsH.R. Arabnia, Y. Mun, H.R. Arabnia, Y. Mun
Pages1447-1453
Number of pages7
StatePublished - Dec 1 2003
EventProceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications - Las Vegas, NV, United States
Duration: Jun 23 2003Jun 26 2003

Publication series

NameProceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications
Volume3

Other

OtherProceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications
CountryUnited States
CityLas Vegas, NV
Period6/23/036/26/03

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Keywords

  • Approximate algorithm
  • Generalized task system
  • Parallel and identical processors
  • Preemptive scheduling
  • Total flow time

Fingerprint Dive into the research topics of 'Heuristics for generalized task system'. Together they form a unique fingerprint.

Cite this