New MIP model for multiprocessor scheduling problem with communication delays

Abdessamad Ait El Cadi 1 Rabie Ben Atitallah 2, 1 Saïd Hanafi 1 Nenad Mladenovic 1 Abdelhakim Artiba 1
1 LAMIH - UVHC
LAMIH - Laboratoire d'automatique et de mécanique industrielles et humaines
2 DREAMPAL - Dynamic Reconfigurable Massively Parallel Architectures and Languages
Université de Lille, Sciences et Technologies, Inria Lille - Nord Europe, CNRS - Centre National de la Recherche Scientifique
Abstract : 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.
Type de document :
Article dans une revue
Optimization Letters, Springer, 2014, pp.15. 〈10.1007/s11590-014-0802-2〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01104613
Contributeur : Pal Dream <>
Soumis le : dimanche 18 janvier 2015 - 12:35:16
Dernière modification le : jeudi 11 janvier 2018 - 06:27:11

Identifiants

Collections

Citation

Abdessamad Ait El Cadi, Rabie Ben Atitallah, Saïd Hanafi, Nenad Mladenovic, Abdelhakim Artiba. New MIP model for multiprocessor scheduling problem with communication delays. Optimization Letters, Springer, 2014, pp.15. 〈10.1007/s11590-014-0802-2〉. 〈hal-01104613〉

Partager

Métriques

Consultations de la notice

192