Une méthode exacte pour le problème du jobshop cyclique robuste - ENAC - École nationale de l'aviation civile Accéder directement au contenu
Communication Dans Un Congrès Année : 2018

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
Fichier principal
Vignette du fichier
cafieri.pdf (241.85 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01737765 , version 1 (19-03-2018)

Identifiants

  • HAL Id : hal-01737765 , version 1

Citer

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⟩
230 Consultations
79 Téléchargements

Partager

Gmail Facebook X LinkedIn More