Title: A genetic algorithm for scheduling tasks in a real-time distributed system

Authors:Monnier, Y; Beauvais, JP; Deplanche, AM

Source:24TH EUROMICRO CONFERENCE - PROCEEDING, VOLS 1 AND 2    Book Series: EUROMICRO CONFERENCE - PROCEEDINGS    Pages: 708-714    Published: 1998

Abstract:

Real-Time systems must often handle several independent periodic macro-tasks, each one represented by a general tasks graph, including communications and precedence constraints. The implementation of such applications on a distributed system communicating via a bus, requires tasks assignment and scheduling, as well as the taking into account of the communication delays. As periodicity implies macro-tasks deadlines, the problem of finding a feasible schedule is critical. This paper addresses this NP-hard problem resolution, by using a genetic algorithm, under offline and non-preemptive scheduling assumptions. This algorithm performances are evaluated on a large simulation set, and compared to classical list-bused algorithms, a simulated annealing algorithm and a specific clustering algorithm.

DOI: http://doi.ieeecomputersociety.org/10.1109/EURMIC.1998.708092