1 FST de F FST de Fè ès A.U. 2012/2013 s A.U. 2012/2013 Les problèmes d’ordonna
1 FST de F FST de Fè ès A.U. 2012/2013 s A.U. 2012/2013 Les problèmes d’ordonnancement d’ateliers (cours) Pr. Fatima EL KHOUKHI Université Moulay Ismaîl Meknès Faculté des Lettres et des Sciences Humaines de Meknès ordon.atelier@gmail.com Master ROSSD Master ROSSD Pr. Fatima EL KHOUKHI FST de Fès A.U. 2012/2013 Organiser/Planifier Organiser/Planifier Organiser dans le temps, la réalisation d’un ensemble de tâches, en tenant compte de contraintes temporelles (ordre d’enchaînements, délais,…) et de contraintes de ressources (disponibilité des ressources requises,…). Un probl Un problè ème d me d‘ ‘Ordonnancement (A Ordonnancement (A Scheduling Scheduling Problem Problem) ) (Un problème de décision, souvent associé à un problème d’Optimisation Combinatoire) Ordonnancer Quand ? Par quels moyens ? Sous quelle modalité ? 2 Pr. Fatima EL KHOUKHI FST de Fès A.U. 2012/2013 - Les problèmes d’ordonnancement sont variés par nature. On peut les rencontrer dans tous les domaines du monde pratique qui font appel aux notions d’organisation et de planification. - En général, la plupart des secteurs sont concernés par les problèmes d’ordonnancement au sens large. Ainsi, l'ordonnancement est devenu un champ d'investigation que connait un essor important, tant par les nombreux problèmes identifiés que par l'utilisation et le développement de nombreuses techniques de résolution. - Les systèmes étudiés peuvent être de différentes natures : Systèmes industriels de production, Systèmes informatiques, Systèmes administratifs, Systèmes hospitaliers, Systèmes de transport, … Domaines d’application Pr. Fatima EL KHOUKHI FST de Fès A.U. 2012/2013 Cas Statiques/Dynamiques Cas Statiques/Dynamiques En fonction de la nature des données associées au problème étudié, deux catégories de problèmes d’ordonnancement sont à distinguer : Problèmes statiques ou déterministes : Si les tâches à ordonner sur un horizon de planification ainsi que l’état initial de composantes du problème, sont connus à priori. Problèmes dynamiques ou stochastiques : Si les décisions sont à prendre au cours de la production, et toutes les tâches à réaliser ne sont pas connues à l’avance. Deux types de décisions existent : • L’ordonnancement prédictif : Consiste à prévoir un certain nombre de décisions en fonction des données prévisionnelles et du modèle traité. • L’ordonnancement réactif : Consiste à adapter les décisions prévues théoriquement en fonction de l’état courant du système et de sa position par rapport au modèle réel. 3 Pr. Fatima EL KHOUKHI FST de Fès A.U. 2012/2013 Problèmes d’ordonnancement d’ateliers Organiser dans le temps le fonctionnement d'un atelier, pour utiliser au mieux les ressources humaines et matérielles disponibles, dans le but de produire les quantités désirées dans le temps imparti. Exploiter au mieux les moyens limités (ressources) des ateliers de production. La terminologie utilisée (job, opération, machine, gamme opératoire ou encore contraintes de précédence,…). Les ressources sont des machines qui ne peuvent réaliser qu'une opération à la fois. Chaque job à ordonnancer est un produit ou un lot de produits à fabriquer selon une gamme de fabrication (gamme opératoire). Contexte Pr. Fatima EL KHOUKHI FST de Fès A.U. 2012/2013 Une tâche (ou opération) est une entité élémentaire de travail, localisée dans le temps par une date de début et/ou de fin, dont la réalisation nécessite une durée d’exécution et qui consomme un moyen ou ressource (machine). Plusieurs tâches peuvent constituer une activité et plusieurs activités peuvent définir un processus. Un ensemble de tâches nécessaires à la réalisation d’un produit, sera désigné par « job » ou « travail ». Un ordre de passage des produits sur les ressources (ordre des opérations associées à chaque travail) est appelé «gamme opératoire» ou « séquence technologique ». Les machines peuvent disposées de zones de stockage appelés « tampons » ou « buffers storage », situés à leurs entrée (input buffers) ou à leurs sortie (output buffers), destinés pour stocker des pièces, soit: En attente d’exécution sur une machine, En attente de transfert vers une autre machine pour continuer le traitement, En fin d’exécution et en attente de transfert vers le dépôt final pour être stockées jusqu’à ce qu’elles soient livrées aux clients. Problèmes d’ordonnancement d’ateliers Terminologies 4 Pr. Fatima EL KHOUKHI FST de Fès A.U. 2012/2013 A chaque tâche, nous pouvons associer un ensemble de caractéristiques temporelles telles que : Durée d’exécution (processing time) : Période nécessaire pour l’exécution d’une tâche, appelée aussi durée opératoire. Date au plutôt ou date de disponibilité (release time ou earliest starting time) : Date avant laquelle, une tâche ne peut démarrer, sinon elle est en avance. Date au plus tard ou date d’échue (due date ou earliest completion time) : Date avant laquelle, une tâche doit être achevée, sinon elle est en retard. Date de début : Date de début réelle d’exécution d’une tâche (à calculer). Date de fin : Date de fin réelle d’exécution d’une tâche (à calculer). Problèmes d’ordonnancement d’ateliers Terminologies Pr. Fatima EL KHOUKHI FST de Fès A.U. 2012/2013 Comme tout problème d’ordonnancement, les données de base sont principalement: Les tâches à ordonnancer avec leurs contraintes d’enchaînements, leurs durées (description des processus de réalisation). Les ressources qui sont nécessaires à l’exécution. Une fonction objectif (cas mono-objectif) ou plusieurs fonctions objectifs (cas multi-objectifs) à optimiser. Un ordonnancement (une solution) est un calendrier précis des tâches à réaliser, qui met en œuvre (selon la nature du problème étudié) une partie ou l’ensemble des trois procédures fondamentales: L’affectation qui consiste à attribuer les ressources nécessaires à une tâche. Le séquencement qui précise l'ordre de passage des tâches sur chaque ressource. Le datage qui donne pour chaque tâche une date de début et une date de fin. Problèmes d’ordonnancement d’ateliers Composantes de base 5 Pr. Fatima EL KHOUKHI FST de Fès A.U. 2012/2013 Parmi les variables utilisées dans la plupart des problèmes d’ordonnancement, figurent les variables de décision pour : o Des décisions sur le temps, o Des décisions sur les ressources (variables d’affectation). Un ordonnancement désigne toute solution au problème d'ordonnancement. Un séquencement consiste à fixer un ordre relatif entre les tâches, qui peuvent être en conflit pour l’utilisation des ressources. On désigne par « séquence », toute solution à ce problème. Un ordonnancement admissible ou réalisable est un ordonnancement qui vérifie les contraintes. Un espace de recherche est l’ensemble des ordonnancements admissibles. Terminologies Pr. Fatima EL KHOUKHI FST de Fès A.U. 2012/2013 En fonction des décisions sur les tâches, trois types de solutions existent dans le domaine des problèmes d’ordonnancement: Ordonnancement actif : Si aucune tâche ne peut être exécutée plus tôt, sans violer de contrainte ou causer le retard d’une autre tâche. Ordonnancement semi-actif ou calé à gauche : Si aucune tâche ne peut être exécutée plus tôt, sans changer l’ordre d’exécution sur les ressources ou violer de contrainte. Ordonnancement sans délai ou sans retard : Si aucune opération n'est mise en attente, alors qu'une machine est disponible pour l'exécuter. Classification: actif/semi-actif et sans délai Solutions 6 Pr. Fatima EL KHOUKHI FST de Fès A.U. 2012/2013 Relations d’inclusion entre les classes d’ordonnancement Espace de recherche Semi-actifs Admissibles Actifs Sans délai Il a été démontré, que pour tout critère régulier, les ensembles des ordonnancements semi-actifs et actifs contiennent au moins une solution optimale. La recherche d'une solution optimale peut être limitée à l'ensemble des ordonnancements actifs, ce qui restreint la taille de l'espace de recherche. Pr. Fatima EL KHOUKHI FST de Fès A.U. 2012/2013 On considère le problème d’ordonnancement à une seule machine et deux tâches O1 et O2 de durées opératoires respectivement 2 (/unité de temps) et 1 (/unité de temps) et de dates de disponibilité respectives 1 et 0. Exemple d’ordonnancement semi-actif Exemple d’ordonnancement à la fois semi-actif, actif et sans-délai Exemples Classification: actif/semi-actif et sans délai 7 Pr. Fatima EL KHOUKHI FST de Fès A.U. 2012/2013 Une ressource est un moyen technique ou humain destin Une ressource est un moyen technique ou humain destiné é à à être utilis être utilisé é pour la r pour la ré éalisation d'une tâche et disponible en quantit alisation d'une tâche et disponible en quantité é limit limité ée (capacit e (capacité é suppos supposé ée limit e limité ée) e) Ressources doublement Contraintes: Si leur utilisation instantanée et leur consommation globale sont toutes deux limitées (source d’énergie, financement,…). Ressources renouvelables: Ce type de ressources reste disponible avec la même quantité, même après avoir été utilisé par une ou plusieurs tâches en quantité limitée à chaque instant, telles que, les hommes, les machines, l’espace, les équipements en général. Ressources consommables: C’est le cas contraire des ressources renouvelables, il s’agit de moyens tels que, la matière première, les budgets,…etc. De même, pour ces ressources, la consommation globale ou cumul au cours du temps est limité. Pr. Fatima EL KHOUKHI FST de Fès A.U. 2012/2013 Ressources disjonctives ou non partageables Ressources disjonctives ou non partageables: Ne peuvent ex Ne peuvent exé écuter cuter qu qu’ ’une tâche une tâche à à la fois (machines, outils, robots manipulateurs, la fois (machines, outils, robots manipulateurs,… …). ). Ressources cumulatives ou uploads/Management/ ordonnancement-d-x27-ateliers.pdf
Documents similaires
-
14
-
0
-
0
Licence et utilisation
Gratuit pour un usage personnel Attribution requise- Détails
- Publié le Oct 29, 2021
- Catégorie Management
- Langue French
- Taille du fichier 0.5540MB