A. Mahmood
Department of Computer Science, University of Bahrain, Bahrain
ABSTRACT
Optimal scheduling of real-time tasks in multiprocessor systems is known to be computationally intractable for large task sets. Therefore, heuristic approaches seem appropriate to these classes of problems. In this paper, we propose a tabu search algorithm for nonpreemptive scheduling of periodic real-time tasks in multiprocessor systems under precedence and resource constraints. The real-time tasks are characterized by their periods, deadlines, worst-case computation times and precedence and resources constraints, we present various strategies to obtain the initial solution, neighborhood solutions and the best move. The performance of the proposed algorithm is demonstrated through a simulation study. The solution quality and execution efficiency of the proposed tabu search has also been compared with a hybrid genetic algorithm.
PDF References Citation
How to cite this article
A. Mahmood, 2003. Non-preemptive Scheduling of Real-time Tasks Under Precedence and Resource Constraints. Information Technology Journal, 2: 13-20.
DOI: 10.3923/itj.2003.13.20
URL: https://scialert.net/abstract/?doi=itj.2003.13.20
DOI: 10.3923/itj.2003.13.20
URL: https://scialert.net/abstract/?doi=itj.2003.13.20
REFERENCES
- Hansen, P., L.P.F. de Eugenio and C.R. Celso, 1992. Location and sizing of offshore platforms for oil exploration. Eur. J. Operat. Res., 58: 202-214.
Direct Link - Hubscher, R. and F. Glover, 1994. Applying tabu search with influential diversification to multiprocessor scheduling. Comput. Operat. Res., 21: 877-884.
Direct Link - Hou, E.S.H., N. Ansari and H. Ren, 1994. A genetic algorithm for multiprocessor scheduling. IEEE Trans. Parallel Distributed Syst., 5: 113-120.
Direct Link - Kim, Y.C. and Y.S. Hong, 1993. A task allocation using a genetic algorithm in multicomputersystems. Proc. Comput. Commun. Control Power Eng., 1: 258-261.
Direct Link - Ramamritham, K., J.A. Stankovic and P.F. Shiah, 1990. Efficient scheduling algorithms for real-time multiprocessor systems. IEEE Trans. Parallel Distributed Syst., 1: 184-194.
Direct Link - Streich, H., 1995. Taskpair-scheduling: An approach for dynamic real-time systems. Int. J. Mini Microcomput., 17: 77-83.
Direct Link - De Falco, I., R. Del Balio, E. Tarantino and R. Vaccaro, 1994. Parallel tabu search verses parallel evaluation strategies. Proceedings of the 1st International Conference on Massively Parallel Computing Systems, May 2-6, Ischia, Italy, pp: 564-569.
Direct Link