A heuristic algorithm for scheduling multiclasses of tasks in multiprocessor systems

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.