A heuristic algorithm for scheduling multiclasses of tasks in multiprocessor systems

S. Bataineh, A. M. Al-Saideen

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

Abstract

This paper presents a low-complexity heuristic algorithm for scheduling several types of tasks in multiprocessor systems (MPS), called random and transferring tasks scheduling (RTTS) algorithm. This algorithm minimizes the maximum completion time of the computational processors and at the same time tends to minimize the response time of tasks. The author proves that the bound of the longest processing time scheduling (LPTS) algorithm is incorrect, and hence the proposed algorithm has the best bound. The algorithm is proven to converge and the results show that the convergence occurs after a short time. The algorithm can deal with divisible and indivisible paradigms of tasks. RTTS is compared with other algorithms and found to give comparable finish times and better response time. Moreover, its results are very close to optimal values.

Original languageEnglish
Pages (from-to)107-116
Number of pages10
JournalInternational Journal of Computers and Applications
Volume20
Issue number3
Publication statusPublished - 1998
Externally publishedYes

Keywords

  • Divisible tasks
  • Heuristic
  • Indivisible tasks
  • Maximum finish time
  • Multiprocessor system
  • Response time
  • Static deterministic scheduling

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design

Fingerprint

Dive into the research topics of 'A heuristic algorithm for scheduling multiclasses of tasks in multiprocessor systems'. Together they form a unique fingerprint.

Cite this