Ordonnancement, transport et logistique à l'université de technologie de Compiègne

21/10/2017
Publication REE REE 2005-1
OAI : oai:www.see.asso.fr:1301:2005-1:20572
DOI :

Résumé

Ordonnancement, transport et logistique à l'université de technologie de Compiègne

Métriques

3
3
2.26 Mo
 application/pdf
bitcache://efa9871e752f1c5e1a9e65f6b20b710f1d72e6d1

Licence

Creative Commons Aucune (Tous droits réservés)
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/1301:2005-1/20572</identifier><creators><creator><creatorName>Jacques Carlier</creatorName></creator><creator><creatorName>Aziz Moukri</creatorName></creator></creators><titles>
            <title>Ordonnancement, transport et logistique à l'université de technologie de Compiègne</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2017</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Sat 21 Oct 2017</date>
	    <date dateType="Updated">Sat 21 Oct 2017</date>
            <date dateType="Submitted">Fri 20 Jul 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">efa9871e752f1c5e1a9e65f6b20b710f1d72e6d1</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>34744</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

s s î e r LOGISTIQUE ET TRANSPORT Ordonnancement, transport m et logistique à l'université de m technologie de Compiègne Mots clés Ordonnancements disjonctifs et cumulatifs, Systèmes flexibles deproduction, Conditionnement ParJacques CARLIER, Aziz MOUKRIM Heudiasyc, UMR CNRS, Université de Technologiede Compiègne, Centre de Recherchesde Royallieu - Compiègne 1. Introduction Nous nous intéressons aux problèmes d'optimisation en logistique de transport et de production. Nous travaillons plus particulièrement sur des problèmes d'ordonnancement issus de la productique [5], de l'informatique [28, 29] et du transport [10, 11]. Au sens strict, un problème d'or- donnancement consiste à déterminer les dates d'exécution d'activités qui utilisent une ou des quantités connues d'un ensemble donné de ressources dont les capacités sont limitées. Des contraintes de précédence doivent aussi être prises en compte. L'objectif est de mettre au point des méthodes exactes ou approchées pour minimiser une fonction économique dépendant des dates d'achèvement des activités. Les problèmes traités étant très combina- toires, une étude théorique est nécessaire pour pouvoir élaborer des énumérations implicites utilisant des outils réduisant fortement la combinatoire. Nous avons eu la chance de voir les problèmes d'ordonnancement, sous l'angle de l'éditeur de logiciels (IBM, ILOG), de l'utilisateur de ces logiciels (BOUYGUES), et de l'industriel (EUROCONTROL, SAINT-GOBAIN, VEOLIA, etc.). Ces visions complémentaires ont été pour nous un atout important pour mener à bien nos projets de recherche appliquée. Notre approche consiste à développer des algorithmes de résolution de problèmes centraux. Ces algorithmes sont ensuite utilisés pour résoudre des pro- blèmes d'optimisation combinatoire du monde industriel, dont les données sont souvent entachées d'incertitudes. Nous avons donc aussi mené des études sur les notions de flexibilité et de robustesse en ordonnancement. Nous décrivons ci-dessous nos résultats sur les problèmes d'ordonnancement dont les ressources sont de type disjonctif au paragraphe 2, et cumulatif au paragraphe 3. Le paragraphe 4 est dédié à la flexibilité et à la robustesse, et le paragraphe 5 à quelques applications. 2. Problèmes d'ordonnancement à contraintes disjonctives Les méthodes PERT et potentiel-tâches résolvent le problème central de l'ordonnancement où il s'agit de planifier, en une durée minimale, des tâches soumises exclusivement à des contraintes de succession et de localisation temporelle. Dès qu'il y a des contraintes disjonctives dues à l'existence d'une ou plusieurs res- sources disponibles en un seul exemplaire, les problèmes deviennent NP-difficiles. C'est pourquoi ils font l'objet d'une recherche intensive depuis quarante ans. ESSEN TI SYNOPSIS Le laboratoire Heudiasyc (HEUristique et DIAgnostic des SYstèmesComplexes),est une unité mixte entre l'université de technologiede Compiègne(UTC)et le CNRS.Crééeen 1981,elle est hébergée au sein de l'UTC. L'une des problématiques de recherches du thème ARO (Algorithmique pour les réseaux et l'optimisation) du laboratoire Heudiasyc,concerne l'optimisation dessystèmescomplexes.AROdéveloppenotammentdessolutions algorithmiques, validéesparpreuvethéorique,simulationet expéri- mentations,pourdes problèmesliésà l'ordonnancement, autrans- port et à la logistique.Nos compétencesdansces thématiquesde recherche nous ont permis de mettre en place la filière ADEL (Aide à la décision en logistique), dans le département génie informatiquede l'UTC.Quatre membres du thème AROassurent la responsabilité pédagogique de cette filière : Jacques Carlier, AntoineJouglet, Aziz Moukrim et Dritan Nace. Heudiasyc (HEUristiqueet DIAgnostic desSYstèmes Complexes) isa « joint ·>CNRS-UTCresearch laboratory. Heudiasyc's guiding principle isto bringtogetherresearch incontrol, signal, imageand computersciencewithanemphasis onhumanfactors.Oneof its teamsARO(AlgorithmiquepourlesRéseaux et l'Optimisation) is working on algorithms for networks and optimization. We are especiallyworkingon Scheduling, Transportation and Logistics. Fourmembersofthisteamareinvolved ina newpathADEL(Aide à la DécisionEn Logistique) opento youngengineers: Jacques Carlier, AntoineJouglet,AzizMoukrimandDritanNace. REE ? Janvier 2005 Ordonnancement, transport et logistique à l'Université de technologie de Compiègne i,i P] 2 Et, pi-, Eel Em E ; E,, Em 0 ; 'i r, p r2 En En_ E_, Ezi E, E i U 0 1 1- 13 1-, , El E 0 El,2 P2] E, P22 E, il r2, P, -, Ec, 0 Ec b 3 1 1 rl% 0 r ; 1 -1 1 1 4e% r,,, 0 E113 pi E31 il 2 E32 Pl-, Ec', Figitre 1. Exeiiiple de gi-aphe PERT disjoiictif. 2.1. Problèmes de/ob-shop et f/ot-shop Nous avons proposé une méthode basée sur des arbi- trages triviaux [6] pour résoudre ces problèmes. Cette méthode avait été testée sur des problèmes d'ateliers de typeflow-shop (gamme identique pour chaque pièce), et avait permis de résoudre des exemples de taille quasi industrielle. Ensuite, nous avons repris ce travail pour l'adapter [15] aux problèmes d'ateliers de type job-shop (gamme variable dépendant de la pièce). Nous avons résolu, sur mini-ordinateur, le très célèbre problème à dix pièces et dix machines de Muth et Thompson, qui avait résisté à vingt-cinq ans d'attaque à l'aide de gros moyens de calcul. Ce résultat a permis de confirmer que notre approche était la plus performante. Nous travaillons depuis à son amélioration. Nous avons proposé en 1988 un algorithme polynomial pour trouver tous les arbitrages triviaux. Il permet d'améliorer notre méthode [16]. En 1992, nous avons introduit les notions d'opérations globales et locales qui permettent de diviser par 100 la taille des arborescences parcourues. Nous avons amélioré également la complexité de nos algorithmes pour les arbitrages triviaux passant de 0 (n 2) à 0 (nlogn) [17]. Nos algo- rithmes sont maintenant intégrés dans plusieurs codes industriels, par exemple ILOG SCHEDULE conçu par féquipe de Claude Le Pape et CHIP de Mehmet Dincbass. Une application intéressante sur laquelle nous travaillons, depuis décembre 2000, est l'optimisation de la coordination des conflits aériens, à l'aide d'une modé- lisation par graphe PERT disjonctif (voir figure 1) [10]. c 2.2. Problème à une machine L'étude du problème à une machine est fondamentale pour la résolution de problèmes d'ordonnancement à contraintes disjonctives. Pour minimiser la durée totale, nous avons mis au point une méthode arborescente [7], qui permet de traiter des données aléatoires ayant jusqu'à 10 000 tâches. Elle repose sur des propriétés théoriques de l'ordonnancement de Jackson qui garantissent l'excel- lence des évaluations par défaut et par excès. Une partie de ces résultats a été généralisée au problème à m machines qui est à la base de l'étude des problèmes cumu- latifs. Parallèlement, nous avons étudié le cas particulier à durées égales. Il s'agissait alors d'un problème ouvert. Nous avons mis au point une technique algorithmique basée sur un préordre lexicographique pour obtenir un algorithme polynomial de complexité 0 (n2logn) [8]. Le critère précédent ne correspond pas toujours, d'après ILOG, aux préoccupations des industriels, plutôt intéressés par la minimisation de la somme pondérée des dates de fin, la minimisation de la somme pondérée des retards par rapport à une certaine date, ou la maximisa- tion du nombre de tâches exécutées dans une certaine fenêtre de temps. En dehors de travaux théoriques sur des cas particuliers, peu d'études ont été menées sur de tels critères. Nous avons amorcé nos travaux de recherches sur ces problèmes à une machine par le critère de la mini- misation du nombre de tâches en retard [4]. Ensuite, nous avons étudié le cas de la somme des retards et proposé une méthode arborescente avec propagation de contraintes, ainsi que plusieurs techniques efficaces et originales [1, 21 qui permettent de réduire l'espace de recherche. 2.3. Systèmes flexibles de production Un système flexible de production avec chariots filo- guidés est un atelier automatisé (voir figure 2) composé de stations et d'un système de manutention utilisant des chariots filoguidés qui assurent le transport des jobs entre les stations, ainsi que le transport entre les stations et la station d'entrée/sortie. Des jobs de gammes connues sont ordonnancés dans l'atelier. Chaque gamme définit la liste des stations sur lesquelles la pièce doit être traitée et le REE N'l Janvier 2005 . Dossier) LOGISTIQUE ET TRANSPORT L' " " J L :Ë LlË : sans = ! ! conducteur -' M2 M3 p Chariot sans [et onducteur mi M2 M3 ,.. M2 M3 C M6 M5 M4 Station de w charement déchargeme t ri Station de chargement - déchargement Figtire 2. Exeiiiple de s,stèiiie flexible de pi-odi (ctioii. temps de traitement de la pièce sur chaque station. Chaque station se compose d'un stock d'entrée, d'un poste d'usinage et d'un stock de sortie. La solution consiste à résoudre de manière conjointe le problème d'ordonnancement des jobs en entrée et la gestion des ressources de transport. Le fait de limiter le nombre de jobs simultanément auto- risés dans un système flexible de production joue un rôle déterminant pour la performance du système, puisqu'il a une influence sur le nombre d'opérations effectivement traitées en parallèle. Cela permet d'éviter entre autres des situations d'interblocage. Pour cela, nous avons proposé une approche basée sur le couplage d'une procédure par séparation et évaluation avec un modèle de simulation à événements discrets. L'originalité de ce couplage est de permettre la prise en compte de toutes les contraintes de fonctionnement utilisant un seul chariot. L'approche proposée [26] permet d'obtenir des solutions optimales pour des problèmes de petite taille et des solutions approchées pour des problèmes de grande taille. L'évaluation et la validation de notre approche ont été réalisées avec des exemples représentatifs extraits de la littérature. 3. Problèmes d'ordonnancement cumulatifs Dans cette partie, nous décrivons brièvement nos travaux sur le problème à m machines (voir figure 3), le RCPSP (resource constrained project scheduling pro- blem) ainsi que nos contributions relatives aux problèmes de conditionnement (Bin-packing). 3.1 Problème à m machines L'étude du problème à m machines [31, 32] est fon- damentale pour aborder les problèmes d'ordonnancement à contraintes cumulatives. Nous avons proposé un algo- rithme polynomial [8] pour le cas des durées égales dont l'intérêt est essentiellement théorique. Dans [9] nous avons proposé pour le résoudre dans le cas général, la méthode des intervalles qui est une méthode arborescente fondée sur la séparation des intervalles d'exécution des tâches. Cette méthode est rendue efficace par des évaluations associées à des propriétés théoriques de l'ordonnancement de Jackson, qui généralisent les propriétés du problème à une machine. Ensuite, nous avons introduit [18] la notion de pseudo-préemption en vue d'améliorer nos évaluations. Depuis, nous avons mis au point l'algorithme JPPS correspondant. Nous avons également généralisé l'outil si fructueux des arbitrages triviaux, grâce à la pseudo- préemption [191. Dans le cadre des problèmes d'ordonnancement non préemptif sur les machines parallèles, nous nous sommes également intéressés aux ordres intervalles pour des systèmes de tâches UET (Unit Execution Time). Nous avons défini une nouvelle classe d'ordre, les ordres sur- intervalles [22, 30], contenant strictement à la fois les ordres intervalles et une sous-classe des ordres séries- parallèles. Nous avons proposé un algorithme de résolution de complexité linéaire pour cette nouvelle classe d'ordres, en considérant le cas général où le nombre de machines disponibles varie dans le temps (profils variables). REE WI Janvier 2005 Ordonnancement, transport et logistique à l'Université de technologie de Compiègne A (2) B ()) " 1) l F (3) G (2) C (3) m illo m C B F A D A D BH A 1 1 1 " - 0 1 2 3 4 5 6 7 Figure 3. Exeniple de problèiie d'ordoiiiiaiiceiîîeiit citnitilaif Ensuite, remarquant que tout ordonnancement optimal du problème traité est une extension sur-intervalle du graphe de précédence représentant les contraintes de précédence de base, nous avons développé une méthode arborescente qui détermine une telle extension. 3.2. RCPSP Dans un RCPSP, on cherche à ordonnancer un ensemble de tâches sur des machines pour lesquelles les ressources peuvent exister en plusieurs exemplaires. La disponibilité de ces ressources est fixée, et la quantité requise pour chaque tâche est supposée connue. On parle de problème cumulatif dans la mesure où il faut faire en sorte qu'à chaque instant, et pour chaque ressource, la quantité de ressources utilisées ne dépasse pas la quantité disponible. Le problème de base est le problème à m machines identiques. Nos évaluations reposent sur des relaxations linéaires de ce problème à iii machines [12]. Les solutions de ces relaxations sont précalculées pour pouvoir être tabulées. Nous avons aussi généralisé les ajustements en utilisant la notion d'énergie [3]. Les méthodes obtenues donnent aujourd'hui de très bons résultats. Les relaxations proposées amènent naturellement au concept de ressources redondantes. L'idée est d'exploiter le fait que de nombreuses tâches ne peuvent s'exécuter pendant le même intervalle de temps pour des contraintes de ressource. Nous avons donc proposé de modifier l'instance initiale en utilisant des fonctions redondantes [13, 14]. Ces fonctions peuvent être appliquées à la demande en ressource de chaque tâche de telle manière qu'aucune configuration réalisable ne puisse devenir irréalisable. On obtient ainsi une nouvelle instance pour laquelle on peut calculer de nouvelles évaluations. Le nombre de fonctions redondantes est très important, mais peu sont réellement utiles pour obtenir des bornes intéressantes. En particulier, nous nous restreignons aux fonctions redondantes maximales (MRF), fonctions qui ne sont dominées par aucune autre. Parmi ces fonctions maximales, nous avons montré que l'on pouvait en éliminer encore un grand nombre. Les différentes propriétés des MRF ont permis de mettre au point une méthode de géné- ration de l'ensemble de ces fonctions pour une quantité de ressource donnée. Pour des tailles moyennes, nous sommes en mesure de générer l'ensemble de ces fonctions. En revanche, pour une ressource de grande capacité, nous ne sommes capables de générer qu'un sous-ensemble de fonc- tions. Les résultats obtenus montrent que même lorsque nous ne disposons pas de l'ensemble des MRF, les évalua- tions obtenues sont de très bonne qualité. Les résultats sont particulièrement probants sur des instances de grande taille. 3.3. Problèmes de conditionnement Le problème de conditionnement (bin-packing) en deux dimensions consiste à minimiser le nombre de grands rectangles identiques nécessaires pour ranger un ensemble de petits rectangles. On rencontre ce problème dans l'industrie lorsque des plaques de métal, de bois, de tissu ou de verre doivent être découpées dans de grands rectangles de la matière première. Ce problème est la généralisation du problème classique de bin-packing en une dimension, il est donc NP-difficile. Ce sujet a fait l'objet d'une attention accrue ces dernières années. Des résultats très importants ont été obtenus récemment : Martello et Vigo (2002), ainsi que Fekete et Schepers (2001), ont proposé de nouvelles méthodes de résolution exacte ainsi que de nouvelles bornes inférieures, tandis que Boschetti et Mingozzi (2002) ont proposé de nouvelles bornes inférieures qui dominent toutes les autres. Nous nous sommes intéressés dans un premier temps à des méthodes de prétraitement qui ont pour objectif de REE N 1 Janvier 2005 Dossier LOGISTIQUE ET TRANSPORT Hauteur Objet 5 argeur Ressource durée Tâche 5 Demande tem ps temps Figure 4. Bin-packing et problèmes d'ordonnancement cumtilatifs. réduire la taille du problème initial. Pour cela, nous avons défini la notion de fonctions identique ment réalisables qui peuvent être appliquées sur des instances du problè- me sans modifier la valeur de la solution optimale. Parallèlement, nous avons adapté les bornes inférieures, développées pour les problèmes d'ordonnancement cumulatifs, au problème de bin-packing. La figure 4 montre la correspondance immédiate entre les deux pro- blèmes. Les évaluations obtenues ont la propriété de dominer en théorie et en pratique toutes celles de la litté- rature [23]. Dans un deuxième temps, nous avons travaillé sur le problème de réalisabilité : il s'agit de déterminer si un sous-ensemble donné d'objets peut être rangé dans un rectangle unique. Nous avons introduit deux nouvelles méthodes exactes [24] qui améliorent considérablement la méthode classique. L'algorithme le plus efficace est basé sur une méthode en deux phases. La première phase consiste à construire un modèle de solutions. Durant la deuxième phase, on détermine s'il existe une solution qui respecte ce modèle. L'intérêt est de factoriser dans un premier temps un grand nombre de solutions et de réaliser des coupes importantes dans l'arbre de recherche. Au fur et à mesure de l'exploration, nous effectuons une mise à jour des évaluations par défaut, qui permettent d'effectuer des coupes dans l'arbre de recherche. Nous travaillons parallèlement à une résolution heuristique de ce problè- me. Pour le moment, un comparatif des algorithmes exis- tants est en cours. La prochaine étape de notre travail va consister à exploiter les différents résultats que nous avons obtenus afin de proposer une méthode générale de résolution exacte du problème de bin-packing en deux dimensions. Précisons que la plupart de nos résultats sur le problème en deux dimensions sont généralisables au problème en trois dimensions. Nous pensons dans l'avenir proposer des extensions de nos méthodes à ce problème afin de diversifier leur champ d'application. 4. Flexibilité et robustesse en ordonnancement 4.1. Informatique parallèle Pour mieux tenir compte des fluctuations des coûts de communication inter-tâches en temps réel dans les archi- tectures distribuées, nous avons proposé un algorithme pour la gestion de la concurrence inter-processus au sein d'un même processeur. Dans notre modèle, une estimation d'un coût de communication est supposée soumise à une certaine perturbation due aux problèmes de contention ou de panne dans le réseau d'interconnexion. Nous avons proposé un algorithme de stabilisation temps réel [33] où nous déterminons une extension du graphe de précédence d'origine basée sur un regroupement statique des tâches. Nous avons testé notre approche sur différents jeux d'essai où les graphes sont générés aléatoirement avec différents niveaux de granularité. Nous avons obtenu de très bonnes performances par rapport à une approche où l'ordonnancement obtenu hors ligne est conservé. De même dans le cas de petites perturbations, notre approche permet d'obtenir d'excellents résultats par rapport à une approche complètement en ligne. Par ailleurs, nous avons établi l'optimalité de notre algorithme pour les graphes de type Fork et Join. Nous avons également procédé à une analyse de sensibilité [25] du problème d'ordonnancement d'arbres avec coûts de communication sur deux processeurs dans le but de minimiser le makespan (durée totale). Les tâches sont supposées unitaires et les communications inconnues avant l'exécution. Nous avons comparé les makespans des ordonnancements optimaux avec et sans REE WI Janvier 2005 N Ordonnancement, transport et logistique à l'Université de technologie de Compiegne N r *..7 -- - - - - - - - - - - - - ,L- r "' ; ' \ --\-- "' "<' " " -- . \ \ c '---- / "'' " " - --- l \ \ , -- t- ' " " " - - . \' " " - ---a ./ " -J--. « \ \,'-- - -- ' - - _ *\ t'- *--. -- J "---B/' "" - Br " " "---t AW== 4ç -'-' \,.- .--.--', "' " ".'. ---' " --- /-... " " " -'-./ //- " " ",.. - - -,..-- " .- - \. - " " ", / "',.i\..... ",,'- "" ../...-.... V \, "/ ", """y" - ----, \'\''- Figure 5.Problèmes deconflits dans le trafic aérien. coûts de communication.Ces résultatsont été utilisés pour obtenir des bornesde sensibilitédes algorithmes optimauxdansle casdestâcheset coûtsde communica- tion unitaires. 4.2. Traficaérien La gestiondu trafic aérienest actuellementassurée par descontrôleursau sol. Il estnécessaire de résoudre lesconflits dansle ciel (voir figure5) entrelesavionsen modifiant certaines trajectoires. Actuellementl'opérateur humain effectuecettetâchede contrôleen utilisant un écran radar et des communicationsvocales. Mais si l'augmentationdu trafic sepoursuit,il faudra vraisem- blablementune évolution combinantautomatisationet intervention humaine,d'où la nécessitéde nouvelles méthodesd'optimisation de la gestiondu trafic aérien pour résoudrece problème complexe. Les méthodes proposéesdans la littérature pour gérer les conflits aérienssontbasées sur l'optimisation continue.Elles ne permettent pasengénéral d'obtenirdessolutions optimales, et parfoisne peuventmêmepasdéterminerune solution réalisable. Nousnoussommes appuyés surlestechniques de l'optimisation combinatoire (ordonnancement disjonctif) pour développerde nouvellesapproches d'optimisation destrajectoires devols. Un premiermodèled'ordonnan- cementdisjonctif couplé à une méthodearborescente [10] s'estrévéléadaptéet efficace.Nousavonsproposé ensuiteuneévolutiondu modèlepourprendre encompte lesincertitudes surlesvitesses desavions.Notrenouveau modèleprocèdeà la résolutiondesconflits en utilisant uneméthodedynamiquetenantcomptedesincertitudes sur la vitessedesavions.Elle reposesur l'effet HORI- ZON permettantla prédiction d'un conflit au plus tôt pourdétournerl'avion à un coûtminimal [11]. 5. Exemples d'applications Optimisation des plans de trame du satellite EUTELSAT [20]. Le satellite européenEUTELSAT retransmet descommunications téléphoniques intra-euro- péennes depuis mars 1984 grâce à un système AMRT/CNC(accèsmultiplesà répartitiondansle temps et compression numériquedeconversation). Nousavons mis au point uneméthodepour construireles plansde trame,en définissantla compositiondespaquets, et leur ordonnancement sur les répéteursdu satellite. Cette méthodesophistiquée estopérationnelle. Elle donnedes REE ? ! Janvier 2005 . DOSSier) LOGISTIQUE ET TRANSPORT résultats optimaux pour les années 1984 à 1991, et proches de l'optimum pour les années ultérieures. Ce projet d'origine pratique a été pour nous extrêmement emichissant. Nous avons en effet utilisé la plupart des outils classiques de l'optimisation combinatoire, à savoir les graphes, les couplages dans les graphes bipartis, les méthodes arbo- rescentes, la programmation dynamique, les algorithmes de liste avec évaluations, les algorithmes gloutons, le recuit simulé... Problèmes de tournées et du voyageur de commerce [21]. Un problème important de la gestion de production est le ramassage d'articles dans des entrepôts. Nous avons résolu un problème de ce type pour VPC, entreprise de vente par correspondance, par un algorithme de com- plexité linéaire. Il nous a donné l'idée d'une méthode heu- ristique pour le problème du voyageur de commerce. Cette heuristique a de bons résultats pratiques. Nous avons aussi démontré qu'elle a des propriétés théoriques très intéressantes, dans la mesure où le graphe du voisinage CD tD est de profondeur [log'n] : c'est un (ou le) premier résultat de ce type sur les voisinages de taille exponentielle. Planification des arrêts de tranches nucléaires [27]. Le parc nucléaire français est composé en majorité de réacteurs à eau sous pression. Ces réacteurs doivent s'ar- rêter environ une fois par an pour être rechargés en com- bustible. Diverses contraintes portent sur le placement de ces arrêts ; elles sont liées à des impossibilités d'arrêter trop de réacteurs à la fois sur un même site ou bien sur l'ensemble du parc, et aux travaux de maintenance à effectuer au cours des arrêts. Le problème est donc de proposer un planning pour ces arrêts, de telle sorte que diverses contraintes soient satisfaites et que le coût global associé au planning construit soit raisonnable. Références [11 Ph. Baptiste, J. Carlier, A. Jouglet, "A Branch-and-Bound Procedure to Minimize Total Tardiness on One Machine with Arbitrary Release Oates " European Journal of Operational Research, vol. 158., n° 3, pp. 595-608, 2004. [2] Ph. Baptiste, A. Jouglet, "On Minimizing Total Tardiness in a Serial Batching Problem ". RA RO Operations Research, vol. 35, pp 107-115, 2001. [3] Ph. Baptiste, C. "Le Pape, Constraint Propagation and Decomposition Techniques for Highly Disjunctive and Highly Cumulative Project Scheduling Problem ". Constraints, vol. 5, pp 119-139, 2000. [4] Ph. Baptiste, L. Peridy, E. Pinson, "A Branch-and-Bound to Minimize the Number of Late Jobs on a Single Machine with Release Time Constraints ". European Journal of Operational Research, vol. 144, Issue 1, pp. 1-11, 2003. [5] M. Bécart, Ph. Lacomme, A. Moukrim, N. Tchernev, " Proposition de résolution exacte d'un MILP pour les sys- tèmes flexibles de production de type-job-shop avec trans- port ". MOSIM 04, 5ème Conférence francophone de modélisation et simulation, 1-3 septembre 2004. [6] J. Carlier, "Problèmes d'ordonnancement à contraintes dis- jonctives ". Thèse de 3ecycie, 110 pages, juin 1975. [7] J. Carlier, " The One Machine Problem ". European Journal of Operational Research, 42-47, 1982. [8] J. Carlier, "Problèmes d'ordonnancement à contraintes de ressources : algorithmes et complexité ". Thèse d'état, 343 pages, mai 1984. [9] J. Carlier, "Scheduling Jobs with Release Dates and Tails on Identical Machines to Minimrze Makespan ". European Journal of Operational Research, Vol. 29, 3, 298-306, June 1987. [10] J. Carlier, V. Duong, D. Nace, H.-H. Nguyen, " Using Disjunctive Scheduling for a New Sequencing Method in Multiple-Conflicts Solving ". ITSC 2003, Shan, 12-15 October. [111 J. Carlier, R. Haddad, A. Moukrim, L. Thoma-Cosyns, "Effet horizon dans la coordination des conflits aériens ". MOSIM 04, 5 ? ne Conférence francophone de modélisation et simulation, 1-3 septembre 2004. [12] J. Carlier, B. Latapie, "La méthode des intervalles appli- quée aux problèmes cumulatifs ". RAIRO, 25, n° 3, 311- 340, février 1991 [13] J.Carher. E.Néron, "A LP Based Bound for the M-Machine Problem " EJOR, 1-20, pp 363-382, January 2000. [14] J. Carlier, E. Néron, " On Linear Lower Bounds for the Resource Constrained Project Scheduling Problem ". European Journal of Operational Research, Vol 149, Issue 2, pp 314-324, 2003. 15J J. Carlier, E. Pinson, "A Branch-and-Bound Method for Solving the Job Shop Problem ". Management Science, 164-176, 1989. [16] J. Carlier, E. Pinson, " A Practical Use of Jackson's Preemptive Schedule for Solving the Job-shop problem ". Annals of Operations Research, 26, 269-287, 1990. [17] J. Carlier, E. Pinson, " Adjustments of Heads and Tails for the Job-Shop Problem ". EJO R (78), 146-161, 1994. [181 J. Carlier, E. Pinson, "Jackson's Pseudo Preemptive Schedule for the Pm/n, qrjCmax Scheduling Problem " in Annals of OR, 83 (1998), 41-58. [19] J.Car ! er, E. Pinson, "JPPS and Cumulative Scheduling Problems. Discrete Applied Mathematics ", à paraître. [20] J. Carlier, C. Prins, " Optimisation des plans de trame dans le système AMRTICNC d'EUTELSAT ". Annales des télé- commun cations, 43, 9-10, 1988, 506-521. [21] J. Carlier, P. Villon, "A New Heuristic for the Traveling Salesman Problem " RAIRO, Vol. 24, 245-253, 1990. [221 M. Chardon, A. Moukrim, " The Coffman-Graham Algorithm Optimally Solves UET Task Systems with Over-Interval Orders ". SIAM Journal on Discrete Mathematics, à paraître. [231 F Clautiaux, J. Carlier, A Moukrim, "Pretreatments and Lower Bounds for the Two-Ditnensional Oriented Bin- Packing Problem ". Ninth International Conference on Project Management and Scheduling PMS'2004, Apri 26-28. 1241 F. Clautiaux, J. Carlier, A. Moukrim, "Méthode exacte pour le problème de ù/n-pac/ng en deux dimensions ". MOSIM 04, Str'e Conférence francophone de modélisation et simulation, 1-3 septembre 2004. [25] F. Guinand, A. Moukrim, E. Sanlaville, "Sensitivity Analysis of Tree Scheduling on Two Machines with Communication Delays ". Paral e Computing, vol. 30, pp 103-120, 2004. (26] Ph. Lacomme, A. Moukrim, N. Tchernev, "Simultaneously Job Input Sequencing and Device Dispatching in a Single Device Trip-Based Automated Material Handling Systems " International Journal of Production Research, à paraïtre. [271 V. Morice, " Arrêt des tranches de centrales nucléaires ". Stage de DEA (Université de technologie de Compiègne) effectué à la direction des études et recherches d'EDF à Clamart, 2001-2002. REE WI Janvier 2005 Ordonnancement, transport et logistique à 'Université de technologie de Compiègne A. Moukrim, "On the Minimum Number of Processors for Scheduling Problems with Communication Oelays ".Annals of Operations Research, vo. 86, pp, 455-472, 1999. A. Moukrim, "Upper Bound on the Number of Processors for Scheduling with Interprocessor Communication Oelays ". Mathematical Methods of Operations Research, vol.52, n'1, pp. 99-113, 2000 A. Moukrim, "Scheduling Unitary Task Systems with Zero- One Communication Oelays for Quasi-Interval Orders " Discrete Applied Mathematics, vol. 127, pp. 461-476, 2003. A. Moukrim, A. Quilllot, "A RelationBetween Multiprocessor Scheduling and Linear Programming ".Order, vol, 14, n'3, pp. 269-278, 1997. A Moukrim, A. Quilliot,"Optimal Preemptive Scheduling on a Frxed Number of Identical Machines ". Operations Research Letters,à paraître,2004. A. Moukrim, E. Sanlaville,F. Guinand, Parallel "Machine Scheduling with Uncertain Communication Delays ". RAIRO Operations Research, vo. 37, pp 1-16, 2003. e s a u e u r s Jacques CARLIER estanc en ô ève de ENS Cachan 1 a obtenu à l'université Pierre et Marie Curie (Paris VI) son DEA d'informatique en 1973, son doctorat de 3ème cyclesur les « Problèmes d'or- donnancement à contraintes disjonctives en 1975 etson doctorat d'Etat surles« Problèmesd'ordonnancementà contraintes de res- source algorithmes etcomplexité » en 1984.De 1974 à 1985, Il a été assistant puis maïtre de conférencesà université Par s Vi Depu s 1985, il est professeur à l'université de Technologiesde Compiègne, où il est actuellement responsable de la fomaüon doctorale « Technologies de l'information et des systèmes ». Il a encadré plusde vingt thèseset publié plus de trente articles dans des revues internationales de recherche opérationnelle. Son domaine d'intérêt est optimisat on comb Patoire, et plus spécifi- quement, les problèmes d'ordonnancement et de fiabilité de réseaux. Aziz MOUKRIM a obtenu en 1995 une thèse d'université en informatique, « Générationautomatique de codes parallèles et nouvelles heuristiques d'ordonnancement pour les machines a passage de messages ».à l'universlté Blaise Pascal IClermont- Ferrandl. a préparé par lasuiteune habilitation à diriger des recherchesen 2002 à l'université de Technologiede Compiègne sur' «Ordonnancement multiprocesseurs et systèmes flexibles de production, algorithmes et simulation " De 1999 à 2004, II a été maître de conférences,pUIS professeuren informatiqueà l'UTC Il est responsable de la filière ADEL IAideà la Décision En Logistique) au département de génie informatique et co-respon- sable du thème ARO (Algorithmiquepour les Réseaux et l'Optimisation) de !'Un ! té Mxte de Recherche (UMR) CNRS- UTC, Heudiasyc II est l'auteur de nombreuses publications internationales en optimisation combinatoire dont certaines concernant les problèmes d'ordonnancement en informatique parallèle avec délaisde communication et les problèmes de logistique. REE N ") Janvier 2005