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 language | English |
---|---|
Pages (from-to) | 107-116 |
Number of pages | 10 |
Journal | International Journal of Computers and Applications |
Volume | 20 |
Issue number | 3 |
Publication status | Published - 1998 |
Externally published | Yes |
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