Skip to Main content Skip to Navigation
Conference papers

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
Document type :
Conference papers
Complete list of metadatas

Cited literature [3 references]  Display  Hide  Download

https://hal-enac.archives-ouvertes.fr/hal-01737765
Contributor : Laurence Porte <>
Submitted on : Monday, March 19, 2018 - 5:49:10 PM
Last modification on : Tuesday, February 11, 2020 - 1:55:46 PM
Document(s) archivé(s) le : Tuesday, September 11, 2018 - 8:36:35 AM

File

cafieri.pdf
Files produced by the author(s)

Identifiers

  • 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. ⟨hal-01737765⟩

Share

Metrics

Record views

327

Files downloads

57