Groupe d’études et de recherche en analyse des décisions

G-2004-99

Mathematical Programming-Based Approach to Scheduling of Communicating Tasks

, , et

We present a MILP mathematical programming formulation for static scheduling of dependent tasks onto homogeneous multiprocessor system of an arbitrary architecture with communication delays. We reduce the number of constraints by applying a Reduction Constraint reformulation to the model. We solve several small-scale instances of the reformulated problem by using CPLEX 8.1. Upper bounds are computed with the Variable Neighborhood Search meta-heuristic applied directly to the graph-based formulation of the problem, whereas lower bounds are obtained by solving linear relaxations of the MILP formulation, further tightened by using load balancing and critical path method arguments.

, 15 pages