Improved mixed-integer programming models for the multiprocessor scheduling problem with communication delays |
| |
Authors: | Sven Mallach |
| |
Affiliation: | 1.Institut für Informatik,Universit?t zu K?ln,Cologne,Germany |
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|