Authors: Ait El Cadi, Abdessamad
Ben Atitallah, Rabie
Hanafi, Saïd
Mladenović, Nenad 
Artiba, Abdelhakim
Title: New MIP model for multiprocessor scheduling problem with communication delays
Journal: Optimization Letters
Volume: 11
Issue: 6
First page: 1091
Last page: 1107
Issue Date: 1-Aug-2017
Rank: M21
ISSN: 1862-4472
DOI: 10.1007/s11590-014-0802-2
In this paper we consider scheduling tasks on a multiprocessor system, taking into account communication delays. We propose a new Mixed Integer Program (MIP) formulation that drastically reduces both the number of variables and the number of constraints, when compared to the best mathematical programming formulations from the literature. In addition, we propose pre-processing procedures that generates cuts and bounds on all variables, reducing the solution space of the problem as well. Cuts are obtained by using forward and backward critical path method from project management field, while the upper bound is derived from the new greedy heuristic. Computational experience shows advantages of our approach.
Keywords: Communication delay | CPLEX | Mixed integer program | Multiprocessors | Task scheduling
Publisher: Springer Link

Show full item record


checked on May 16, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.