
Research Article


Scheduling RealTime Tasks in Ditsributed Environment with Tabu Search Algorithm 

Mahmood, A.



ABSTRACT

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 realtime tasks with minimum jitter in a distributed computing environment is particularly important in many control applications. This problem is known to be NPhard, 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 realtime 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.






REFERENCES 
1: Burns, B.I., A. McDermid and J.A. Vickers, 1996. Towards a fixed priority scheduler for an aircraft application. Proceedings of the 8th Euromicro Workshop on RealTime Systems, June 1214 1, L'Aquila, Italy, pp: 3439 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 realtime system design and implementation. Lecture Notes Comput. Sci., 688: 1935. Direct Link 
3: Carpenter, T., K. Driscoll, K. Hoyme and J. Carciofini, 1994. ARINC 659 scheduling: Problem definition. Proceedings of RealTime Systems Symposium, Dec. 79, San Juan, Puerto Rico, pp: 165169 Direct Link 
4: Fohler, G., 1994. Flexibility in statistically scheuled hard realtime systems, technische naturwissenschaftliche, Fakultaet. Techniques University Wein.
5: Glover, F., 1990. Tabu search: A tutorial. Interfaces, 20: 7494.
6: Hou, E.S., N. Ansari and H. Ren, 1994. Genetic algorithm for multiprocessing scheduleing. IEEE Trans. Parallel Distributed Syst., 5: 113120.
7: Hubscher, R. and F. Glover, 1996. Applying tabu search with influential diversification to multiprocessor scheduling. Comput. Commun., 5: 6167.
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 1215, IEEE Xplore, London, pp: 6167
9: Manimaran, G. and C.S.R. Murthy, 1998. An efficient dynamic scheduling algorithm for multiprocessor realtime systems. IEEE Trans. Parallel Distributed Syst., 9: 312319.
10: Mahmood, A., 2000. A hybrid genetic algorithm for task scheduling in multiprocessor realtime systems. Int. J. Stud. Inform. Control, 9: 207217.
11: Di Natale, M. and J.A. Stankovic, 2000. Scheduling distributed realtime tasks with minimum jitter. IEEE Trans. Comput., 49: 303316.
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 realtime multiprocessor systems. IEEE Trans. Parallel Distributed Syst., 1: 184194. Direct Link 
14: Stankovic, J.A., K. Ramamritham and S. Cheng, 1985. Evaluation of a flexib task scheduling algorithm for distributed hard realtime systems. IEEE Trans. Comput., 34: 11301143.
15: Tindell, K.W., A. Burns and A.J. Wellings, 1992. Allocating hard realtime tasks: An NPhard problem made easy. Real Time Syst., 4: 145165. Direct Link 
16: Xu, J. and D. Parnas, 1990. Scheduling processes with release times, deadlines, precedence and exclusion relations. IEEE Trans. Software Eng., 16: 360369.
17: Kim, Y.C. and Y.S. Hong, 1993. Task allocation using genetic algorithm in multiprocessor systems. Proc. IEEE Conf. Comput. Commun. 15: 258261.



