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
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: |
|
||||||||
| 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: |
|
||||||||
| 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 |