New MIP model for multiprocessor scheduling problem with communication delays - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Optimization Letters Année : 2014

New MIP model for multiprocessor scheduling problem with communication delays

Résumé

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.
Fichier non déposé

Dates et versions

hal-01104613 , version 1 (18-01-2015)

Identifiants

Citer

Abdessamad Ait El Cadi, Rabie Ben Atitallah, Said Hanafi, Nenad Mladenovic, Abdelhakim Artiba. New MIP model for multiprocessor scheduling problem with communication delays. Optimization Letters, 2014, 11 (6), pp.1091-1107. ⟨10.1007/s11590-014-0802-2⟩. ⟨hal-01104613⟩
164 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More