Méthodes d’optimisation robuste pour les problèmes d’ordonnancement cyclique

Méthodes d’optimisation robuste pour les problèmes d’ordonnancement cyclique

Problème du job shop cyclique

Dans cette section, nous considérons le problème du job shop cyclique (CJSP : Cyclic Job Shop Problem) qui a été introduit dans [Hanen 1994]. La différence avec le BCSP est que le nombre de machines disponibles est inférieur au nombre de tâches génériques à exécuter. Par conséquent, certaines machines doivent être partagées par plusieurs tâches. Ainsi, le problème du job shop cyclique peut être considéré comme un BCSP avec des contraintes de ressources. Dans un CJSP, chaque occurrence d’une tâche i ∈ T = {1, …, n} doit être exécutée, sans préemption, sur une machine M(i) ∈ M = {1, …, m}. Les différentes tâches génériques sont regroupées sous forme de jobs, où chaque job j ∈ J représente une séquence de tâches qui doivent être exécutées dans un ordre précis. Afin d’éviter le chevauchement entre deux exécutions de deux tâches génériques affectées sur la même machine, pour toutes les occurrences k et l (l, k ∈ Z) de chaque paire de tâches i et j où M(i) = M(j) , les contraintes disjonctives suivantes sont introduite : t(i, k) + pi ≤ t(j, l) ou t(j, l) + pj ≤ t(i, k) k, l ∈ Z. (1.7) La contrainte (1.7) indique donc que si les tâches i et j sont exécutées sur la même machine, alors pour une occurrence k de la tache i et une occurrence l de la tâche j, il existe deux possibilités : — soit l’occurrence k de la tache i se termine avant le début de l’occurrence l de la tâche j, — soit l’occurrence k de la tache i débute après la fin de l’occurrence l de la tâche j. Dans le contexte de l’ordonnancement classique, on parle parfois d’arbitrage pour ces contraintes disjonctives [Carlier 1978]. Il a été prouvé dans [Hanen 1994] que la contrainte (1.7) peut être réécrite comme suit : tj − ti + αKij ≥ pi Kij + Kji = 1 Kij ∈ Z    ∀ i, j ∈ T : M(i) = M(j) (1.8) où Kij est une variable qui représente le décalage d’occurrence entre les exécutions des tâches i et j. Notons que, contrairement au problème du job shop classique, l’ensemble des valeurs possibles pour les variables Kij est l’ensemble des entiers Z et non pas {0, 1}. Preuve. Soit hi, ki et hj, li deux occurrences exécutées sur la même machine. Ces occurrences ne se chevauchent pas si et seulement si : ti + αk + pi ≤ tj + αl ou tj + αl + pj ≤ ti + αk Autrement dit, soit tj − ti ≥ pi − α(k − l) soit tj − ti ≤ −pj − α(k − l). Donc, les contraintes disjonctives sont satisfaites si et seulement si la valeur de la différence tj − ti ne coïncide pas avec les intervalles [−pj − αKij , pi − αKij ]. En d’autres termes, tj − ti doit être compris entre deux intervalles successifs, c’est à dire, dans ] − pj − αKij , pi − αKij [ 

 Résoudre un problème de CJSP

 Peu de méthodes exactes ont été présentées dans la littérature. Une des manières de résoudre le CJSP est de résoudre la formulation MIP (1.10), introduite dans [Hanen 1994], par des solveurs de programmation linéaire comme Cplex. Une méthode de Branch-and-Bound à été présentée dans [Hanen 1994]. Dans cet algorithme, les branchements sont effectués sur les décalages d’occurrence qui ne sont pas encore fixés. L’auteur utilise un branchement dichotomique. Plus précisément, à partir d’un noeud de l’arbre de recherche, le branchement est effectué sur un arc disjonctif Kij et deux noeuds sont générés. Dans le premier noeud, l’intervalle des valeurs possibles pour Kij est restreint à Iij = [K− ij , cij ] et le deuxième est restreint à [cij + 1, 1 − K− ji], où cij est le milieu de l’intervalle Iij . Une autre méthode de Branch-and-Bound a été présentée dans [Fink 2012]. Le branchement consiste à brancher sur une variable de décalage d’occurrence Kij ∈ D qui n’est pas encore fixée, et à générer un noeud fils pour chaque valeur possible dans l’intervalle Iij . Pour chaque noeud généré, l’algorithme affecte une valeur différente dans Iij pour Kij . Une version du job shop avec des jobs identiques a été étudiée dans [Roundy 1992]. L’auteur prouve que le problème est N P-difficile et développe un algorithme de Branch-and-Bound. Une version du job shop cyclique où un ensemble de MPS doivent être produits a été étudiée dans [Lee 1997]. Ce problème ce résout de la même manière que le CJSP. Un CJSP où l’ordre d’exécution des tâches génériques sur les machines est déjà donné a été étudié dans [Lee 2000]. L’auteur présente une approche algébrique afin de résoudre le problème. Des méthodes de résolution exactes et approchées ont été proposées pour une extension du CJSP avec des contraintes de précédence linéaires qui ont été présentées dans la Sous-section 1.2.4. Ce problème a été étudié dans [Boussemart 2002]. Les auteurs utilisent une approche de programmation par contraintes pour résoudre le problème. Un algorithme génétique a été présenté dans [Cavory 2005] pour la résolution du CJSP avec des contraintes de précédence linéaires. Une méthode approchée basée sur les réseaux de neurones, pour le CJSP avec minimisation du temps de cycle, a été présentée dans [Kechadi 2013a]. 

 Problèmes d’ordonnancement cyclique : extensions 

Dans cette thèse, nous étudions deux problèmes d’ordonnancement cyclique, le BCSP et CJSP. Ce choix est justifié par le fait de commencer par le problème le plus basique afin d’avoir plus d’intuitions sur le comportement des ordonnancements cycliques et de rajouter ensuite des contraintes afin d’arriver à résoudre des problèmes 24 Chapitre 1. Problèmes d’ordonnancement cyclique de plus en plus compliqués. Il existe plusieurs problèmes d’ordonnancement cyclique dans la littérature. Un problème d’ordonnancement cyclique avec des machines parallèles a été étudié dans [Munier 1996a]. L’auteur montre que le problème est N P-difficile et montre un cas polynomial correspondant au problème avec uniquement deux machines. Dans [Sucha 2008], un problème d’ordonnancement cyclique avec un ou plusieurs processeurs à été étudié. Les auteurs montrent que les deux problèmes sont N Pdifficiles et proposent une formulation en termes de programme linéaire en nombres entiers. Il existe aussi des extensions du RCPSP (Resource-Constrained Project Scheduling Problem) au cas cyclique. Dans ce problème, l’exécution de chaque tâche nécessite une ou plusieurs unités de ressources mais ces ressources sont limitées. Donc, il faut qu’à tout moment, les capacités de ces ressources soient respectées. Ce problème a été étudié sous différents points de vue. Notamment, en programmation linéaire en nombres entiers et programmation par contraintes. Ces études peuvent être trouvées dans [Ayala 2013, Hanzalek 2015, Bonfietti 2011, Benabid 2011b, Hanzalek 2011]. De nombreuses extensions du CJSP existent dans la littérature. Des problèmes avec des buffers limités et illimités, avec ou sans transport [Brucker 2012a, Brucker 2012b], avec ou sans blocage [Brucker 2008, Song 1998b]. Notons qu’une tâche est dite bloquante si celle-ci doit rester dans la machine en attendant que la prochaine machine se libère. Des versions cycliques du problème du flowshop ont été présentées dans la littérature. Ces travaux peuvent être trouvés dans [Graves 1983, Bożejko 2015b, Levner 1997]. De nombreux articles de la littérature ont comme application la robotique. [Kats 2002b, Chen 1998]. Une vue générale sur ces problèmes peut être trouvées dans [Levner 2007, Levner 2010]. Un problème d’ordonnancement cyclique avec des ressources cumulative et des contraintes de dates de début au plus tôt (release date) de dates de fin au plus tard (due date) a été étudié dans [de Dinechin 2014].