G-2004-99
Mathematical Programming-Based Approach to Scheduling of Communicating Tasks
, , , and BibTeX reference
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.
Published December 2004 , 15 pages
Document
G-2004-99.pdf (200 KB)