Variante des problèmes d’ordonnancement

Selon la nature des variables et des contraintes mises en jeu, plusieurs variantes des problèmes d’ordonnancement sont proposées dans la littérature. On distingue deux grandes familles de problèmes d’ordonnancement, les problèmes d’ordonnancement de projet et les problèmes d’ordonnancement d’ateliers.

Il s’agit d’un problème très général qui recouvre un grand nombre de situation d’ordonnancement et constitue une très vaste littérature [03]. Les questions les plus fréquentes dans un problème d’ordonnancement de projet, concernent la détermination de la durée totale du projet et la mise en évidence des marges temporelles exploitables pour minimiser le coût d’utilisation des ressources. L’ordonnancement de projet demeure central en ordonnancement car il permet de présenter des concepts fondamentaux et des algorithmes de base pour le traitement des contraintes temporelles.

Une deuxième famille essentielle des problèmes d’ordonnancement, [03] ce sont les problèmes d’ateliers où on doit exploiter au mieux des moyens limités (des machines) pour réaliser un ensemble très varié de produits. La complexité réside alors non pas dans le processus de fabrication, qui est prédéterminé (par exemple sous forme de gammes opératoires), mais plutôt dans la combinatoire qui naît de la prise en compte de la limitation des ressources existences. Indifféremment des problèmes d’ordonnancement prévisionnels, qui prévoient des modalités d’exécution d’un ensemble de tâches par un ensemble de ressources sur un horizon fini ou infini (après avoir effectué des hypothèses préalables sur l’évaluation de la situation du système au cours du temps). On parle des problèmes d’ordonnancement d’ateliers à temps réel, quand il s’agit, d’adapter en permanence les modalités d’exécution d’un ensemble de taches par un ensemble de ressources à la situation réelle du système considéré. En plus des problèmes d’ordonnancement de projet et d’ateliers, on cite une famille de problèmes d’ordonnancements issus du monde pratique, à savoir les problèmes d’ordonnancement cycliques. Il s’agit d’organiser les activités de production en cherchant à répéter un cycle de base relativement bien optimisé, illustrant ainsi la notion même d’ordonnancement cyclique. Un ordonnancement cyclique est ensuite construit par calcul des dates sur la période de référence et répétition cyclique de l’ordonnancement ainsi obtenu. Ces problèmes sont très présents dans le milieu industriel.

Gestion du personnelle

Les ressources humaines sont parmi les ressources les plus cruciales et les plus coûteuses pour la majorité des organisations [03]. Par conséquent, il est capital que chaque entreprise élabore une stratégie efficace de planification de ces ressources. Dans cette perspective, un ordonnancement efficace du personnel permet de générer des réductions des coûts, d’améliorer la qualité des services ou des produits offerts et de maximiser la satisfaction des employées. Les problèmes d’ordonnancement du personnel sont des cas particuliers du problème d’allocation des ressources. Ils peuvent se présenter selon plusieurs configurations ou modèles en fonction des particularités du milieu organisationnel et de la durée de la période de planification. Généralement, ces problèmes portent sur la détermination du nombre d’employés requis pour répondre à une demande en produits ou en services, sur leurs affectations à des tâches précises le long d’intervalles de temps de durée variable, ou encore sur la détermination du lieu de travail pour chaque employé. Ainsi définis, les problèmes d’ordonnancement du personnel peuvent être observés dans plusieurs types d’entreprises manufacturières ou de services. Ce sont des problèmes récurrents dans des domaines tels que : le transport; la santé ; l’enseignement; la production manufacturière; les centres d’appel; la restauration ou les services de protection et d’urgence. Dans les travaux recensés, on rencontre trois catégories de problèmes d’ordonnancement du personnel : le problème de planification des jours de repos, le problème d’élaboration des quarts de travail et le problème d’élaboration des patrons de travail.

Description du RCPSP

La réalisation d’un projet consiste en l’exécution, par des ressources, d’un ensemble d’activités (ou taches) de durées données et liées entre elles par des contraintes de précédence [04]. Dans sa forme classique, une instance du RCPSP est la donnée d’un ensemble A de n activités d’un projet et d’un ensemble R de m ressources. Les activités du projet sont non-interruptibles (ou non-préemptives).

Ainsi, une activité i termine son exécution à l’instant Si+pi, où Si est la date de début d’exécution de i et pi, sa durée. Les activités sont liées par des contraintes de précédence simples, de la forme i j, interdisant de débuter l’exécution de la seconde activité j avant la fin de la première i. On modélise couramment le projet par un graphe values, orienté et sans circuit G V;E; p, le graphe potentiel-taches, formé du graphe associé à la relation formée par les contraintes de précédence, auquel sont ajoutées deux activités fictives de durées nulles, représentant respectivement, le début et la fin du projet : 0 pour le début du projet dont on commence l’exécution à l’instant de référence S0 = 0, et Sn+1 succédant à toutes les activités du projet. L’objectif du RCPSP est de réaliser l’ensemble du projet en un temps minimale, autrement dit de déterminer un ordonnancement 0 1 1 ; ; ..; n S S S S de durée Sn+1 minimale , à la fois en respectant les contraintes de précédences , c’est-à-dire les inégalités de potentiels j i i S S p ,pour tout couple d’activité (i, j) E, et en résolvant à tout instant t les conflits dans l’utilisation de chaque ressource k ; Un tel ordonnancement est dit optimale, tandis qu’un vecteur S vérifiant les contraintes de précédences et les contraintes de ressources sans nécessairement minimiser Sn+1, est appelé ordonnancement réalisable. A partir des données du problème, d’autres valeurs, qui seront utilisées tout au long de ce document, peuvent être initialisées à la toute première étape du processus d’ordonnancement :

Principe de la méthode PERT Pour établir les données de l’ordonnancement des tâches, la méthode PERT procèdent en trois phases :

La première phase consiste à effectuer un parcours (propagation avant aussi appelée forward recursion) du réseau représentant le projet dans le sens des contraintes de précédence pour déterminer les dates au plus tôt des tâches. Il s’agit en fait de déterminer la première tâche du graphe (celle qui n’a pas de prédécesseur) à laquelle on affecte la date au plus tôt à laquelle elle peut commencer, puis d’appliquer un algorithme de calcul de plus long chemin entre cette tâche et toutes les autres tâches du problème. Dès lors les dates de début au plus tôt de chacune des tâches sont établies. Ce sont en effet les dates qui correspondent à la date au plus tôt de la première tâche plus la longueur du plus long chemin entre la première tâche et la tâche en question. Dès cette phase terminée, on connaît la durée minimale du projet dans sa globalité puisque cette durée est la différence entre la date de fin de la dernière des tâches et la date de début de la première.

La seconde phase (propagation arrière appelée backward recursion) est similaire à la première. Cependant comme ce sont les dates de début ou de fin au plus tard qui désirées, on commence par la dernière tâche du projet. Étant donné que l’objectif est de minimiser la durée du projet, on ne veut pas changer la date de fin du projet, donc on pose l’égalité entre la date de fin au plus tard de la dernière des tâches et sa date de fin au plus tôt. Il suffit ensuite de rechercher les chemins les plus longs entre la dernière tâche et toutes les autres pour obtenir pour chaque tâche sa date de fin au plus tard : elle est égale à la date de fin au plus tard de la dernière tâche moins la longueur du plus long chemin de la dernière tâche à la tâche en question.

Finalement, la troisième phase consiste à déterminer les marges des tâches et les chemins critiques. La marge d’une tâche est égale à la différence entre sa date de début au plus tard et sa date de début au plus tôt. Les chemins critiques d’un projet sont les chemins du début du projet à sa fin qui ne sont constitués que de tâches critiques, c’est-à-dire de tâches dont la marge est nulle. Ces tâches critiques sont en fait les tâches qu’on ne peut retarder sans augmenter la durée du projet.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela rapport gratuit propose le téléchargement des modèles gratuits de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

I.INTRODUCTION
II.Les problèmes d’ordonnancement
II.1- Introduction
II.2- Données d’un problème d’ordonnancement
II.2.1 –Tâches
II.2.1.1-liens entre les taches
II.2.2– Ressources
II.2.3–Contraintes
II.2.4– Fonction objectif
III -Variante des problèmes d’ordonnancement
III.1– Ordonnancement de projet
III.2– Ordonnancement d’atelier
III.3– Gestion du personnelle
IV- Problème d’ordonnancement de projet
IV.1-Définition de projet
IV.2-Avec contraintes de ressources (RCPSP
IV.3-Sans contraintes de ressources
V- Méthodes de résolution des problèmes d’ordonnancement
V.1- Introduction
V.2- Méthodes de résolution exacte
V.2.1- Le diagramme de GANTT
V.2.2-Méthode PERT
V.2.3- Méthode de potentiel métra
V.2.4-Conclusion
V.3- Méthode de résolution approchée
V.3.1- Heuristique : Les algorithmes gloutons
V.3.2- Méta-heuristique
V.3.2.1- Algorithmes génétiques
1-schéma de fonctionnement
2-Algorithme
V.3.2.2- Recuit Simulé
V.3.2.3 – la recherche taboue
1- Principe
2- Algorithme d’utilisation
3- Diverses améliorations
V.3.3-Comparaison des méthodes
Conclusion