Une méthode exacte pour le problème du jobshop cyclique robuste

Résumé : Le problème d'ordonnancement cyclique de base (BCSP) est définit par un ensemble T = {1, ..., n} de n tâches génériques. Chaque tâche i ∈ T a une durée p i et doit être exécutée une infinité de fois. On note < i, k > la k éme occurrence de la tâche i. Un ordonnancement σ est une affectation des dates de début t(i, k) pour chaque occurrence < i, k >. Un ordonnancement est dit périodique avec un temps de cycle α si t(i, k) = t(i, 0) + αk, ∀ i ∈ T , ∀ k ≥ 1. (1) Afin de simplifier la notation, nous définissions t i = t(i, 0) pour chaque tâche i dans T. D'après (1), un ordonnancement périodique peut donc être défini seulement avec les dates de début des premières occurrences (t i) i∈T ainsi que le temps de cycle α. Le différentes tâches sont liées par un ensemble de contraintes de précédence dites contraintes uniformes. Ces contraintes sont données par : t(i, k) + p i t(j, k + H ij), ∀i, j ∈ T, ∀k ≥ 0. (2) où i et j sont deux tâches génériques, et H ij un entier naturel, appelé hauteur, qui représente le décalage entre les occurrences des tâches i et j. L'objectif du problème est de trouver un ordonnancement σ opt qui satisfait les contraintes uniformes (2) et minimise le temps de cycle α. Un graphe orienté G = (V, E) peut être associé à ce problème. Un noeud du graphe G représente une tâche et un arc (i, j) est présent si une contrainte de précédence existe entre les deux tâches correspondantes. Dans ce cas, l'arc (i, j), appelé arc uniforme, est étiqueté par deux valeurs, une longueur L ij = p i et une hauteur H ij ∈ Z. Le temps de cycle minimum est donné par le poids moyen maximum du graphe G. Celui-ci est donné par α = max c∈C (i,j)∈c L ij (i,j)∈c H ij Où C est l'ensemble des circuits du graphe G. Le circuit c donnant le poids moyen maximum est appelé circuit critique. Différents algo-rithmes sur le calcul de circuits critiques peuvent être trouvés dans la littérature [3]. Le problème du jobshop cyclique peut être vu comme un problème d'ordonnancement cy-clique de base avec des contraintes de ressources. Nous considérons un ensemble M = {1, ..., m} de m machines tel que m < n. Chaque tâche i ∈ T est exécutée sans interruption sur la machine M (i). Les tâches sont organisées sous forme de job et celles appartenant au même job
Type de document :
Communication dans un congrès
ROADEF 2018, 19ème congrès de la société Française de Recherche Opérationnelle et d'Aide à la Décision , Feb 2018, Lorient, France. 2018
Liste complète des métadonnées

Littérature citée [3 références]  Voir  Masquer  Télécharger

https://hal-enac.archives-ouvertes.fr/hal-01737765
Contributeur : Laurence Porte <>
Soumis le : lundi 19 mars 2018 - 17:49:10
Dernière modification le : vendredi 23 mars 2018 - 01:21:11

Fichier

cafieri.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01737765, version 1

Citation

Idir Hamaz, Laurent Houssin, Sonia Cafieri. Une méthode exacte pour le problème du jobshop cyclique robuste. ROADEF 2018, 19ème congrès de la société Française de Recherche Opérationnelle et d'Aide à la Décision , Feb 2018, Lorient, France. 2018. 〈hal-01737765〉

Partager

Métriques

Consultations de la notice

217

Téléchargements de fichiers

17