Homogeneous Non Idling Problems: Models and Algorithms - Université Pierre et Marie Curie Accéder directement au contenu
Chapitre D'ouvrage Année : 2013

Homogeneous Non Idling Problems: Models and Algorithms

Résumé

This paper is about multi-processor scheduling with non idling constraints, i.e. constraints which forbid interruption in the use of the processors. We first reformulate the problem, while using a notion of pyramidal shape, and next apply matching techniques in order to get a min-max feasibility characterization criterion, which allows us to derive a polynomial algorithm for the related existence problem and for the Makespan Minimization related problem. The last part of the paper is devoted to the Linear Cost Minimization of multiprocessor scheduling with non idling constraints, which we handle through linear model and a heuristic Lagrangean decomposition approach, and involves numerical experiments.

Dates et versions

hal-01366542 , version 1 (14-09-2016)

Identifiants

Citer

Alain Quilliot, Philippe Chrétienne, Bernay Benoit. Homogeneous Non Idling Problems: Models and Algorithms. Studies in Computational Intelligence , 470, Springer Verlag, pp.115-134, 2013, Recent Advances in Computational Optimization, ⟨10.1007/978-3-319-00410-5_7⟩. ⟨hal-01366542⟩
77 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More