Improved Mixed-Integer Programming Models for Multiprocessor Scheduling with Communication Delays

Mallach, Sven (2016) Improved Mixed-Integer Programming Models for Multiprocessor Scheduling with Communication Delays.
Technical Report , 30 p.

WarningThere is a more recent version of this item available.

Abstract

We revise existing and introduce new mixed-integer programming models for the Multiprocessor Scheduling Problem with Communication Delays. At first, we show how to provably reduce the number of product variables necessary to explicitly linearize the so-called packing formulation that contains bilinear terms. Then, we reveal that the feasible region of almost all existing formulations contains redundant solutions and formulate new constraints in order to exclude these. At the same time, by exploiting further structural properties, the models are improved concerning their size, strength, and modeling complexity. The discussion of these improvements leads to new much more compact formulations which are then experimentally compared with each other and with other formulations from the literature. We set up a realistic scenario with a preprocessing of the task graphs, delivering the gained information equally to all the tested models and evaluate not only running times but also the obtained lower and upper bounds on the makespan objective for unsolved instances of a large scale benchmark set.


Actions:
Download: [img] PDF
Download (594kB)
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: UNSPECIFIED
Depositing User: Sven Mallach
Date Deposited: 16 Sep 2016 13:25
Last Modified: 16 Sep 2016 13:25
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/902

Available Versions of this Item