Subscribe Now Subscribe Today
Research Article

Scheduling Real-Time Tasks in Ditsributed Environment with Tabu Search Algorithm

Mahmood, A.
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail

Many time critical applications require predictable performance and tasks in these applications have to meet their deadlines. Hence, tasks in these applications need to be scheduled in such a manner that they not only meet their deadlines but also satisfy some performance criteria specific to the application domain. Scheduling real-time tasks with minimum jitter in a distributed computing environment is particularly important in many control applications. This problem is known to be NP-hard, even for simple cases. Therefore, heuristic approaches seem appropriate to these classes of problems. In this paper, we investigate a tabu search algorithm for nonpreemptive static scheduling of real-time tasks where tasks are periodic and have arbitrary deadlines, precedence and exclusion constraints. The proposed algorithm not only creates a feasible schedule but it also minimizes jitter for periodic tasks. The performance of the algorithm has been studied through a simulation and the results are reported in this paper.

Related Articles in ASCI
Search in Google Scholar
View Citation
Report Citation

  How to cite this article:

Mahmood, A. , 2002. Scheduling Real-Time Tasks in Ditsributed Environment with Tabu Search Algorithm. Information Technology Journal, 1: 153-159.

DOI: 10.3923/itj.2002.153.159



1:  Burns, B.I., A. Mc-Dermid and J.A. Vickers, 1996. Towards a fixed priority scheduler for an aircraft application. Proceedings of the 8th Euromicro Workshop on Real-Time Systems, June 12-14 1, L'Aquila, Italy, pp: 34-39
Direct Link  |  

2:  Burns, A., A.J. Wellings, C.M. Bailey and E. Fyfe, 1993. The olympus attitude and orbital control system: A case study in hard real-time system design and implementation. Lecture Notes Comput. Sci., 688: 19-35.
Direct Link  |  

3:  Carpenter, T., K. Driscoll, K. Hoyme and J. Carciofini, 1994. ARINC 659 scheduling: Problem definition. Proceedings of Real-Time Systems Symposium, Dec. 7-9, San Juan, Puerto Rico, pp: 165-169
Direct Link  |  

4:  Fohler, G., 1994. Flexibility in statistically scheuled hard real-time systems, technische naturwissenschaftliche, Fakultaet. Techniques University Wein.

5:  Glover, F., 1990. Tabu search: A tutorial. Interfaces, 20: 74-94.

6:  Hou, E.S., N. Ansari and H. Ren, 1994. Genetic algorithm for multiprocessing scheduleing. IEEE Trans. Parallel Distributed Syst., 5: 113-120.

7:  Hubscher, R. and F. Glover, 1996. Applying tabu search with influential diversification to multiprocessor scheduling. Comput. Commun., 5: 61-67.

8:  Kidwell, M.D. and D.J. Cook, 1994. Genetic algorithm for dynamic task scheduling. Proceedings of the IEEE 13th Annual International Phoenix Conference on Computers and Communications, April 12-15, IEEE Xplore, London, pp: 61-67

9:  Manimaran, G. and C.S.R. Murthy, 1998. An efficient dynamic scheduling algorithm for multiprocessor real-time systems. IEEE Trans. Parallel Distributed Syst., 9: 312-319.

10:  Mahmood, A., 2000. A hybrid genetic algorithm for task scheduling in multiprocessor real-time systems. Int. J. Stud. Inform. Control, 9: 207-217.

11:  Di Natale, M. and J.A. Stankovic, 2000. Scheduling distributed real-time tasks with minimum jitter. IEEE Trans. Comput., 49: 303-316.

12:  Porto, A.S.C.S. and A.C.C. Ribeiro, 1995. A tabu search approach to task scheduling on heterogeneous processors under precedence constraints. Int. J. High Speed Comput.

13:  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  |  

14:  Stankovic, J.A., K. Ramamritham and S. Cheng, 1985. Evaluation of a flexib task scheduling algorithm for distributed hard real-time systems. IEEE Trans. Comput., 34: 1130-1143.

15:  Tindell, K.W., A. Burns and A.J. Wellings, 1992. Allocating hard real-time tasks: An NP-hard problem made easy. Real Time Syst., 4: 145-165.
Direct Link  |  

16:  Xu, J. and D. Parnas, 1990. Scheduling processes with release times, deadlines, precedence and exclusion relations. IEEE Trans. Software Eng., 16: 360-369.

17:  Kim, Y.C. and Y.S. Hong, 1993. Task allocation using genetic algorithm in multiprocessor systems. Proc. IEEE Conf. Comput. Commun. 15: 258-261.

©  2022 Science Alert. All Rights Reserved