Multiprocessor Task Scheduling - Comparison of Some Heuristics and Metaheuristics
摘要
The article concentrates on the so-called multiprocessor task scheduling problem with deterministic task duration and independent tasks. Executing a task on more than one processor can be perceived as a tool for improving system dependability through hardware and software redundancyOur aim is to compare and evaluate some heuristics for solving the multiprocessor task scheduling problem with deterministic task duration. We compare three models to address this problem: the classical approach [doc], the TS (Tabu Search) algorithm, and PSO (Particle Swarm Optimization). The previous model introduced multiprocessor tasks and a higher level of dependability. The latter models consider other popular heuristics for this type of problem. The previous methodology for multiprocessor task scheduling involved the application of a modified Muntz-Coffman algorithm. In this paper, we compare the previous model with other adapted heuristics (TS, PSO). The article is an extension of the author’s previous research, considering deterministic task duration in different models. Computational experiments were conducted to compare the results obtained for each model.