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.


Actions:
Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
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