Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

1 Management des opérations II Problèmes d’ordonnancement C. SADFI 2 Plan du co

1 Management des opérations II Problèmes d’ordonnancement C. SADFI 2 Plan du cours ► Ordonnancement de la production ► Ordonnancement de projets C. Sadfi - Management des opérations II - 3 Ordonnancement - Un problème d’ordonnancement désigne tout problème dans lequel l’objectif est l’allocation de ressources au cours du temps, de façon à réaliser un ensemble d’activités - Ordonnancer un ensemble de tâches revient à programmer leur exécution dans le temps en leur allouant les ressources requises et en fixant leur date de début, dans le respect de l’objectif fixé ! Définitions Gestion de la production Gestion de projets Ordonnancement de la production Ordonnancement de projets C. Sadfi - Management des opérations II - 4 Ordonnancement - Les problèmes d’ordonnancement en ateliers spécialisés relèvent de la problématique de la régulation à court terme de l’entreprise, et plus particulièrement de celle du contrôle et de l’utilisation de la main d’œuvre et des équipements productifs Complètent les techniques de gestion des stocks qui assurent le contrôle de matières - La théorie de l’ordonnancement est une branche de la recherche opérationnelle. Elle consiste en la recherche de modèles mathématiques et la mise au point de méthodes de résolution efficaces des problèmes proposés C. Sadfi - Management des opérations II - 5 Ordonnancement - Planification dans le temps l’exécution d’un ensemble de tâches sur un ensemble de ressources en respectant un ensemble de contraintes afin d’optimiser un ou plusieurs critères - Tâche : une opération ou un ensemble d’opérations tâche élémentaire travail (job) - Ressources : moyens pour réaliser les tâches • Ressources consommables (exemple : énergie) • Ressources renouvelables (exemples : machines, main d’œuvre) - Exemples • Informatique (tâches : opérations ; ressources : processeurs, mémoires) • Administration (tâches : cours, TD, TP ; ressources : enseignants, salles) C. Sadfi - Management des opérations II - 6 Ordonnancement - Contraintes • Potentielles : précédence — succession ; localisation temporelle - Critère : fonction objectif • Critères liés aux tâches : minimisation de la durée totale de réalisation du projet, minimisation des retards, minimisation des encours, minimisation des déchets, etc. • Disjonctives : même ressource (unique) utilisée par deux tâches (exemple : 2 malades et 1 médecin) • Cumulatives : limitation des niveaux de ressources disponibles (exemple : 5 tâches de maçonnerie et 3 maçons) • Critères liés aux ressources : minimisation d’un coût lié à l’utilisation de ressources. C. Sadfi - Management des opérations II - 7 Ordonnancement - Gamme opératoire : un ensemble ordonné ou semi-ordonné d’opérations. La gamme opératoire spécifie les ressources affectées à l’opération ! Vocabulaires - Séquencement : séquencer un ensemble d’opérations c’est déterminer l’ordre dans lequel elles passeront sur les machines - Affectation : affecter une opération à une ressource c’est préciser pour une tâche la ressource sur laquelle elle sera exécutée L’ordonnancement peut consister à chercher : un "séquencement" ; ou une "affectation" ; ou un "séquencement" et une "affectation" C. Sadfi - Management des opérations II - 8 Ordonnancement de la production C. Sadfi - Management des opérations II - 9 Ordonnancement de la production - n : nombre de travaux - m : nombre de machines - i : indice de travail - j : indice de machine - pij : durée d’exécution de l’opération i sur la machine Mj du travail Ji (processing time) - ri : date de disponibilité du travail Ji (date de début au plus tôt : release date) - di : date de fin souhaitée du travail Ji (due date) - wi : poids attribué au travail Ji ; il exprime le facteur d’importance (weight) ! Notations : données Ordonnancement de n travaux "J = {Ji / i = 1, 2, ..., n}" sur m machines "M = {Mj / j = 1, 2, ...,m}" C. Sadfi - Management des opérations II - 10 Ordonnancement de la production - si : date de début d’exécution du travail Ji (notée également par ti) - Ci : date de fin d’exécution de du travail Ji (completion time) : Ci = si + pi - Fi : durée de séjour dans le système du travail Ji (flow time) : Fi = Ci - ri - Li : écart par rapport à la fin souhaitée ou retard algébrique du travail Ji (lateness) : Li = Ci - di - Ti : retard vrai du travail du travail Ji (tardiness) : Ti = Max(Ci - di ,0) - Ui : : indicateur de retard du travail Ji : Ui = 1 si Ti >0 ; Ui = 0 sinon ! Notations : variables (inconnues) C. Sadfi - Management des opérations II - 11 Ordonnancement de la production ! Diagramme de Gantt - Le "Diagramme de Gantt", du nom de Henry L. Gantt (1917), permet de représenter les besoins en ressources en fonction du temps, par l’intermédiaire d’une liste de tâches représentées par des barres horizontales. Ce diagramme est très classique dans la gestion de projets - Dans un diagramme de Gantt, les lignes correspondent aux machines et les colonnes correspondent aux unités de temps (minutes, heures, semaines, etc.). L’exécution d’une tâche sur une machine donnée est représentée par une barre horizontale, tracée sur la ligne correspondante à la machine en question, de longueur proportionnelle à sa durée d’exécution sur la même machine C. Sadfi - Management des opérations II - 12 Ordonnancement de la production ! Diagramme de Gantt : exemple A B C D E F pi 10 4 1 1 2 6,5 - 6 pièces à usiner : - L’atelier dispose de 3 machines identiques - Exemple de diagramme de Gantt : M1 M2 M3 temps B A E D C F 14 0 C. Sadfi - Management des opérations II - 13 Ordonnancement de la production ! Relation entre les tâches : les tâches sont dites "dépendantes" si elles sont liées entre elles par des relations d’antériorité (ou précédence). Sinon, elles sont dites "indépendantes". ! Mode d’exécution des tâches : dans certains cas, une tâche peut être exécutée par morceaux. On dit alors que la "préemption" est possible (problème préemptif). Dans le cas contraire, la préemption n’est pas autorisée (problème non préemptif) : une fois commencée, une tâche doit être exécutée en entier sans interruption. Souvent, la préemption rend ces problèmes plus faciles de point de vue résolution. C. Sadfi - Management des opérations II - 14 Ordonnancement de la production ! Les machines - Une machine : chaque travail est constitué d’une seule opération - Machine parallèles : elles remplissent, a priori, toutes les mêmes fonctions. Selon leur vitesse d’exécution, on distingue : • machines identiques (P) : la vitesse d’exécution est la même pour toutes les machines Mj et pour tous les travaux Ji ; • machines uniformes (Q) : chaque machine Mj a une vitesse d’exécution propre et constante. La vitesse d’exécution est la même pour tous les travaux Ji d’une même machine Mj ; • machines indépendantes (R) : la vitesse d’exécution est différente pour chaque machine Mj et pour chaque travail Ji. C. Sadfi - Management des opérations II - 15 Ordonnancement de la production ! Les machines - Machines dédiées : elles sont spécialisées à l’exécution de certaines opérations. Dans cette catégorie, chaque travail est constitué de plusieurs opérations. En fonction du mode de passage des opérations sur les différentes machines, trois ateliers spécialisés sont différenciés : • Flow shop (F) : le cheminement des travaux est unique : les n travaux utilisent les m machines dans l’ordre 1, 2, ..., m (ligne de production) • Job shop (J) : les séquences opératoires relatives aux différents travaux peuvent être distinctes et sont propres à chaque travail • Open shop (O) : c’est un modèle d’atelier moins contraint que le flow shop et le job shop, car l’ordre d’exécution des opérations n’est pas fixé C. Sadfi - Management des opérations II - 16 Ordonnancement de la production ! Les critères d’optimisation - Les variables intervenant le plus souvent dans l’expression de la fonction économique sont : • la date Ci de fin d’exécution du travail Ji ; • les retards Li = Ci − di et Ti = max (Ci − di, 0) du travail Ji ; • l’indicateur de retard du travail Ji : Ui = 0 si Ci ≤ di, Ui = 1 sinon. - Minimiser la durée totale (ou maximiser la productivité) : la durée totale de l’ordonnancement notée Cmax (schedule lenght ou makespan) est égale à la date d’achèvement du travail le plus tardif : Cmax = max(Ci). Minimiser la durée totale, revient à minimiser Cmax c’est-à-dire min(max(Ci)). Critère retenu : Min Cmax C. Sadfi - Management des opérations II - 17 Ordonnancement de la production ! Les critères d’optimisation - Minimiser les encours : les encours sont déterminés par le temps de présence des travaux dans l’atelier : Fi = Ci - ri. Le premier critère est de minimiser la somme de ces temps (total flow time) ΣFi, ou de manière équivalente le temps moyen de présence dans l’atelier (mean flow time) uploads/Management/ mop2-ordonnacement.pdf