Improved mixed-integer programming models for the multiprocessor scheduling problem with communication delays
Mallach, Sven
(2017)
Improved mixed-integer programming models for the multiprocessor scheduling problem with communication delays.
Published in:
Journal of Combinatorial Optimization.
pp. 1-22.
ISSN 1573-2886
This is the latest version of this item.
Abstract
We revise existing and introduce new mixed-integer programming models for the Multiprocessor scheduling problem with communication delays. The basis for both is the identification of two major modeling strategies one of which can be considered ordering-based, and the other assignment-based. We first reveal redundancies in the encoding of feasible solutions found in present formulations and discuss how they can be avoided. For the assignment-based approach, we propose new inequalities that lead to provably stronger continuous relaxations and better performance in practice. Moreover, we derive a third, novel modeling strategy and show how to more compactly linearize assignment formulations with quadratic constraints. In a comprehensive experimental comparison of representative models that reflect the state-of-the-art in terms of strength and size, we evaluate not only running times but also the obtained lower and upper bounds on the makespan for the harder instances of a large scale benchmark set.
ZAIK Number: | UNSPECIFIED |
---|---|
Depositing User: | Sven Mallach |
Date Deposited: | 07 Dec 2017 12:38 |
Last Modified: | 13 Mar 2018 09:29 |
URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/909 |
Available Versions of this Item
-
Improved Mixed-Integer Programming Models for Multiprocessor Scheduling with Communication Delays. (deposited 16 Sep 2016 13:25)
- Improved mixed-integer programming models for the multiprocessor scheduling problem with communication delays. (deposited 07 Dec 2017 12:38) [Currently Displayed]