Heuristic techniques: scheduling partially ordered tasks in a multi-processor environment with tabu search and genetic algorithms

Scheduling real-time computation is an extremely important activity in real-time systems, since it is the phase in which we assign the final temporal properties of the computations. The problem of allocating the resources in real-time systems creates an additional dimension within the conventional allocation problem, that of time constraints. The scheduling problem has been extensively examined in the literature. But optimization of valid schedules is an NP-hard problem, even for simple cases. Therefore, heuristic approaches seem appropriate to these classes of problems. In this paper, we investigate scheduling problems with certain kinds of temporal constraints and how these problems can be solved with the techniques of tabu search and genetic algorithms