Plan Introduction aux probl` emes d’ordonnancement 28 novembre 2005 1 de 117 In

Plan Introduction aux probl` emes d’ordonnancement 28 novembre 2005 1 de 117 Introduction aux probl` emes d’ordonnancement Mohamed Ali ALOULOU LAMSADE Universit´ e Paris Dauphine E-mail : aloulou@lamsade.dauphine.fr 28 novembre 2005 Plan Introduction aux probl` emes d’ordonnancement 28 novembre 2005 2 de 117 Plan du cours 1 D´ efinition et formulation du probl` eme d’odonnancement 2 Ordonnancement de projet : rappels et extensions 3 Ordonnancement d’ateliers : contexte et classification 4 Ordonnancement d’ateliers : m´ ethodes de r´ esolution Plan C’est quoi l’ordonnancement ? Domaines Ordonnancement en GdP Contraintes en ordonnancement Contraintes de potentiel Contraintes disjonctives Contraintes cumulatives Formulation math´ ematique Introduction aux probl` emes d’ordonnancement 28 novembre 2005 3 de 117 Partie 1 : D´ efinition et formulation du probl` eme d’odonnancement 1 C’est quoi l’ordonnancement ? 2 Quelques domaines concern´ es par la fonction ordonnancement 3 La fonction ordonnancement dans la gestion de la prodution 4 Contraintes rencontr´ ees en ordonnancement Contraintes de potentiel Contraintes disjonctives Contraintes cumulatives 5 Formulation math´ ematique Plan C’est quoi l’ordonnancement ? Domaines Ordonnancement en GdP Contraintes en ordonnancement Contraintes de potentiel Contraintes disjonctives Contraintes cumulatives Formulation math´ ematique Introduction aux probl` emes d’ordonnancement 28 novembre 2005 4 de 117 Ordonnancer ? D´ efinition Le probl` eme d’ordonnancement consiste ` a organiser dans le temps la r´ ealisation d’un ensemble de tˆ aches, compte tenu de contraintes temporelles (d´ elais, contraintes d’enchaˆ ınements, ...) et de contraintes portant sur l’utilisation et la disponibilit´ e des ressources requises. Un ensemble de tˆ aches Un environnement de ressources pour effectuer les tˆ aches Des contraintes sur les tˆ aches et les ressources Un crit` ere d’optimisation = ⇒D´ eterminer les dates d’execution des tˆ aches Plan C’est quoi l’ordonnancement ? Domaines Ordonnancement en GdP Contraintes en ordonnancement Contraintes de potentiel Contraintes disjonctives Contraintes cumulatives Formulation math´ ematique Introduction aux probl` emes d’ordonnancement 28 novembre 2005 5 de 117 Domaines concern´ es exécution des programmes optimisation de code ... gestion des ressources humaines emplois du temps ... ... Ateliers de production gestion de projets ... Ordonnancement Projets Administration Informatique Production Plan C’est quoi l’ordonnancement ? Domaines Ordonnancement en GdP Contraintes en ordonnancement Contraintes de potentiel Contraintes disjonctives Contraintes cumulatives Formulation math´ ematique Introduction aux probl` emes d’ordonnancement 28 novembre 2005 6 de 117 La gestion de la production [Giard 2003] La gestion de production a pour objet la recherche d’une organisation efficace de la production des biens et des services 3 cat´ egories pour classer les d´ ecisions en gestion de la production : les d´ ecisions strat´ egiques : politique long terme de l’entreprise les d´ ecisions tactiques : d´ ecisions ` a moyen terme planification de la production plan de transport les d´ ecisions op´ erationnelles : court terme gestion des stocks ordonnancement pilotage informatique en temps r´ eel Plan C’est quoi l’ordonnancement ? Domaines Ordonnancement en GdP Contraintes en ordonnancement Contraintes de potentiel Contraintes disjonctives Contraintes cumulatives Formulation math´ ematique Introduction aux probl` emes d’ordonnancement 28 novembre 2005 7 de 117 Contraintes rencontr´ ees en ordonnancement Diff´ erentes contraintes technologiques : une tˆ ache ne peut d´ ebuter que lorsque d’autres sont achev´ ees commerciales : certaines dates doivent ˆ etre achev´ ees pour une date fix´ ee mat´ erielles : une machine ne peut traiter qu’une machine ` a la fois de main d’oeuvre :effectif limit´ e financi` eres : budget limit´ e Plan C’est quoi l’ordonnancement ? Domaines Ordonnancement en GdP Contraintes en ordonnancement Contraintes de potentiel Contraintes disjonctives Contraintes cumulatives Formulation math´ ematique Introduction aux probl` emes d’ordonnancement 28 novembre 2005 7 de 117 Contraintes rencontr´ ees en ordonnancement Diff´ erentes contraintes technologiques : une tˆ ache ne peut d´ ebuter que lorsque d’autres sont achev´ ees commerciales : certaines dates doivent ˆ etre achev´ ees pour une date fix´ ee mat´ erielles : une machine ne peut traiter qu’une machine ` a la fois de main d’oeuvre :effectif limit´ e financi` eres : budget limit´ e Plan C’est quoi l’ordonnancement ? Domaines Ordonnancement en GdP Contraintes en ordonnancement Contraintes de potentiel Contraintes disjonctives Contraintes cumulatives Formulation math´ ematique Introduction aux probl` emes d’ordonnancement 28 novembre 2005 7 de 117 Contraintes rencontr´ ees en ordonnancement Diff´ erentes contraintes technologiques : une tˆ ache ne peut d´ ebuter que lorsque d’autres sont achev´ ees commerciales : certaines dates doivent ˆ etre achev´ ees pour une date fix´ ee mat´ erielles : une machine ne peut traiter qu’une machine ` a la fois de main d’oeuvre :effectif limit´ e financi` eres : budget limit´ e Plan C’est quoi l’ordonnancement ? Domaines Ordonnancement en GdP Contraintes en ordonnancement Contraintes de potentiel Contraintes disjonctives Contraintes cumulatives Formulation math´ ematique Introduction aux probl` emes d’ordonnancement 28 novembre 2005 7 de 117 Contraintes rencontr´ ees en ordonnancement Diff´ erentes contraintes technologiques : une tˆ ache ne peut d´ ebuter que lorsque d’autres sont achev´ ees commerciales : certaines dates doivent ˆ etre achev´ ees pour une date fix´ ee mat´ erielles : une machine ne peut traiter qu’une machine ` a la fois de main d’oeuvre :effectif limit´ e financi` eres : budget limit´ e Plan C’est quoi l’ordonnancement ? Domaines Ordonnancement en GdP Contraintes en ordonnancement Contraintes de potentiel Contraintes disjonctives Contraintes cumulatives Formulation math´ ematique Introduction aux probl` emes d’ordonnancement 28 novembre 2005 7 de 117 Contraintes rencontr´ ees en ordonnancement Diff´ erentes contraintes technologiques : une tˆ ache ne peut d´ ebuter que lorsque d’autres sont achev´ ees commerciales : certaines dates doivent ˆ etre achev´ ees pour une date fix´ ee mat´ erielles : une machine ne peut traiter qu’une machine ` a la fois de main d’oeuvre :effectif limit´ e financi` eres : budget limit´ e Plan C’est quoi l’ordonnancement ? Domaines Ordonnancement en GdP Contraintes en ordonnancement Contraintes de potentiel Contraintes disjonctives Contraintes cumulatives Formulation math´ ematique Introduction aux probl` emes d’ordonnancement 28 novembre 2005 8 de 117 Formalisation des contraintes 1 Contraintes potentielles (ou de potentiels) 2 Contraintes disjonctives 3 Contraintes cumulaives Plan C’est quoi l’ordonnancement ? Domaines Ordonnancement en GdP Contraintes en ordonnancement Contraintes de potentiel Contraintes disjonctives Contraintes cumulatives Formulation math´ ematique Introduction aux probl` emes d’ordonnancement 28 novembre 2005 9 de 117 Contraintes potentielles Notation : tj : date de d´ ebut de la tˆ ache j, pj sa dur´ ee Forme g´ en´ erale : tj −ti ≥aij Localisation temporelle : j ne peut d´ ebuter avant une certaine date (livraison de mati` ere premi` ere, conditions climatiques,...) Contrainte de d´ elai : j doit ˆ etre termin´ ee avant une certaine date Contrainte de succession succession simple succession avec attente succession avec chevauchement succesion imm´ ediate Plan C’est quoi l’ordonnancement ? Domaines Ordonnancement en GdP Contraintes en ordonnancement Contraintes de potentiel Contraintes disjonctives Contraintes cumulatives Formulation math´ ematique Introduction aux probl` emes d’ordonnancement 28 novembre 2005 9 de 117 Contraintes potentielles Notation : tj : date de d´ ebut de la tˆ ache j, pj sa dur´ ee Forme g´ en´ erale : tj −ti ≥aij Localisation temporelle : j ne peut d´ ebuter avant une certaine date (livraison de mati` ere premi` ere, conditions climatiques,...) Contrainte de d´ elai : j doit ˆ etre termin´ ee avant une certaine date Contrainte de succession succession simple succession avec attente succession avec chevauchement succesion imm´ ediate Plan C’est quoi l’ordonnancement ? Domaines Ordonnancement en GdP Contraintes en ordonnancement Contraintes de potentiel Contraintes disjonctives Contraintes cumulatives Formulation math´ ematique Introduction aux probl` emes d’ordonnancement 28 novembre 2005 9 de 117 Contraintes potentielles Notation : tj : date de d´ ebut de la tˆ ache j, pj sa dur´ ee Forme g´ en´ erale : tj −ti ≥aij Localisation temporelle : j ne peut d´ ebuter avant une certaine date (livraison de mati` ere premi` ere, conditions climatiques,...) Contrainte de d´ elai : j doit ˆ etre termin´ ee avant une certaine date Contrainte de succession succession simple succession avec attente succession avec chevauchement succesion imm´ ediate Plan C’est quoi l’ordonnancement ? Domaines Ordonnancement en GdP Contraintes en ordonnancement Contraintes de potentiel Contraintes disjonctives Contraintes cumulatives Formulation math´ ematique Introduction aux probl` emes d’ordonnancement 28 novembre 2005 9 de 117 Contraintes potentielles Notation : tj : date de d´ ebut de la tˆ ache j, pj sa dur´ ee Forme g´ en´ erale : tj −ti ≥aij Localisation temporelle : j ne peut d´ ebuter avant une certaine date (livraison de mati` ere premi` ere, conditions climatiques,...) Contrainte de d´ elai : j doit ˆ etre termin´ ee avant une certaine date Contrainte de succession succession simple succession avec attente succession avec chevauchement succesion imm´ ediate Plan C’est quoi l’ordonnancement ? Domaines Ordonnancement en GdP Contraintes en ordonnancement Contraintes de potentiel Contraintes disjonctives Contraintes cumulatives Formulation math´ ematique Introduction aux probl` emes d’ordonnancement 28 novembre 2005 10 de 117 Contraintes disjonctives Deux tˆ aches i et j sont en disjonction si elles ne peuvent ˆ etre ex´ ecut´ ees simultan´ ement = ⇒Les intervalles d’ex´ ecution des tˆ aches disjonctives sont disjoints : ]ti, ti + pi[∩]tj, uploads/Voyage/ partie-4.pdf

Documents similaires

Chapitre 3 : Optimisation 1- Introduction : L'optimisation est une branche des 0 0

Techniques d’ordonnancement d’atelier et de fournées basées sur la programmatio 0 0

• Détails
• Publié le Aoû 26, 2022
• Catégorie Travel / Voayage
• Langue French
• Taille du fichier 1.7419MB