Conference: MISTA 2013, Ghent, Belgium
Abstract: A computer program can be represented by a Directed Acyclic Graph (DAG) in order to capture the dependencies between the individual tasks that should be executed each time the program runs. This paper proposes a mathematical model of Integer Programming that can be applied in order to schedule the tasks in the presence of multiple processors serving as the execution environment. The target is to minimize the overall execution time of the DAG known as schedule length or makespan. An approach called MATH using the full model is applied to small sized problems and then a more elaborate approach called MATHL is presented where the DAG is partitioned to levels. Levels are formed according to the hops needed for each node to be reached starting from the source node. Hence sub-problems have manageable size and can be solved in a timely manner. Consecutive optimal solutions for each level result in a high quality schedule for the overall problem even for cases consisting of several hundreds of nodes. Results show that this method constantly gives very good results and it is compared favorably with other approaches to the problem that can be found in the bibliography.