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.
Paru en décembre 2004 , 15 pages