Mallach, Sven ORCID: 0000-0001-5335-0678 (2018). Improved mixed-integer programming models for the multiprocessor scheduling problem with communication delays. J. Comb. Optim., 36 (3). S. 871 - 896. DORDRECHT: SPRINGER. ISSN 1573-2886

Full text not available from this repository.

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.

Item Type: Journal Article
Creators:
CreatorsEmailORCIDORCID Put Code
Mallach, SvenUNSPECIFIEDorcid.org/0000-0001-5335-0678UNSPECIFIED
URN: urn:nbn:de:hbz:38-172247
DOI: 10.1007/s10878-017-0199-9
Journal or Publication Title: J. Comb. Optim.
Volume: 36
Number: 3
Page Range: S. 871 - 896
Date: 2018
Publisher: SPRINGER
Place of Publication: DORDRECHT
ISSN: 1573-2886
Language: English
Faculty: Faculty of Mathematics and Natural Sciences
Divisions: Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects: Data processing Computer science
Uncontrolled Keywords:
KeywordsLanguage
TASK GRAPHS; ALGORITHMS; SYSTEMS; ARCHITECTURES; TIMEMultiple languages
Computer Science, Interdisciplinary Applications; Mathematics, AppliedMultiple languages
Refereed: Yes
URI: http://kups.ub.uni-koeln.de/id/eprint/17224

Downloads

Downloads per month over past year

Altmetric

Export

Actions (login required)

View Item View Item