Remerciez-le!

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

Chapitre 2 : Les problèmes d’ordonnancement I. Introduction : Ordonnancer un en

Chapitre 2 : Les problèmes d’ordonnancement I. Introduction : Ordonnancer un ensemble de tâches, c'est programmer leur exécution en leur allouant les ressources requises et en fixant leurs dates de début. Les problèmes d'ordonnancement touchent tous les domaines de l'économie : 1. L'informatique (les tâches sont les programmes ; les ressources sont les processus, la mémoire). 2. La construction (suivi de projet). 3. L'industrie (activités des ateliers en gestion de production et problèmes de logistiques). 4. L'administration (emploi du temps). Dans un problème d'ordonnancement interviennent deux notions fondamentales : les tâches et les ressources. Une ressource est un moyen technique ou humain dont la disponibilité limitée ou non est connue à priori. Une tâche est un travail élémentaire dont la réalisation nécessite un certain nombre d'unités de temps (sa durée) et d'unités de chaque ressource. La résolution d'un problème d'ordonnancement doit concilier deux objectifs : 1. L'aspect statique consiste à générer un plan de réalisation des travaux sur la base des données prévisionnelles. 2. L'aspect dynamique consiste à prendre des décisions en temps réel, compte tenu de l'état des ressources et de l'avancement dans le temps des différentes tâches. II. Données d'un problème d'ordonnancement : 1. Les tâches et leurs caractéristiques 2. Les contraintes potentielles 3. Les ressources 4. La fonction économique (fonction objectif). II. 1. Tâches On note en général I = {1, 2, ..., n} l'ensemble des tâches et pi la durée de la tâche i si cette durée ne dépend pas des ressources qui lui sont allouées. En plus de sa durée, une tâche a d'autres caractéristiques : - ri date de disponibilité, date avant laquelle la tâche i ne peut commencer - di date échue, une tâche i doit être achevée avant sa date échue - ti date réelle de début de la tâche i, date qui sera déterminée uniquement pendant l'ordonnancement - ci date de fin réelle de la tâche i, date qui sera elle aussi calculée uniquement pendant l'ordonnancement. II. 1. 1. Liens entre tâches Les tâches sont souvent liées entre elles par des relations d'antériorité. Si ce n'est pas le cas, on dit qu'elles sont indépendantes. La contrainte d'antériorité la plus générale entre deux tâches i et j, appelée contrainte potentielle, s'écrit sous la forme tj – ti ≥ aij Quand la tâche j commence à la fin de la tâche i, dans ce cas, on dit qu'il y a succession simple. aij = pi ( pi étant la durée de la tâche i) ∀i∈ I = { 1, 2, ..., n}, ri ≤ ci ≤ di II. 1. 2. Caractéristiques des tâches Une tâche, dite morcelable ou préemptive peut être exécutée par morceaux. Dans un problème d'atelier, les tâches sont regroupées en entités appelées travaux (ou jobs). L'atelier contient m machines distinctes et chaque travail est un ensemble de m opérations élémentaires, chacune d'elle devant s'exécuter sur une machine différente (parmi les m machines). II. 1. 3. Type d'atelier On distingue trois types de problèmes d'atelier selon la nature des contraintes de précédence entre les opérations élémentaires (tâches) d'un même travail : - Si les opérations élémentaires d'un travail sont liées par un ordre total, non nécessairement identique pour tous les travaux, il s'agit d'un problème de ''job-shop''. - Si les opérations élémentaires sont indépendantes, il s'agit d'un problème de ''open- shop'' - Si les opérations élémentaires des travaux sont liées par le même ordre total, il s'agit d'un problème de ''flow-shop''. Il n'y a pas de contraintes de précédence sur des opérations élémentaires de travaux différents. Les problèmes d'ateliers sont des problèmes combinatoires extrêmement difficiles. Exemple : Soient n le nombre de tâches et m le nombre de machines, dans un problème de flow-shop, il y a (n!)m solutions réalisables. Quand on impose que les opérations élémentaires soient exécutées dans le même ordre sur chaque machine, il y a alors n! solutions. II. 2. Ressources On distingue deux types de ressources pouvant être requises pour les tâches, les ressources renouvelables et les ressources consommables. Une ressource est renouvelable si après avoir été allouée à une tâche, elle redevient disponible pour les autres (machines, processus, fichiers personnel). Une ressource est consommable si après avoir été allouée à une tâche, elle n'est plus disponible pour les tâches restant à exécuter (argent, matières premières). Une ressource qu'elle soit consommable ou renouvelable est disponible qu'à certaines périodes (temps de travail, temps de repos). II. 3. Contraintes Les ressources introduisent des contraintes disjonctives et des contraintes cumulatives : - Une contrainte disjonctive apparaîtra lorsque deux tâches devant la même machine, ne pourront pas s'exécuter simultanément. - Une contrainte cumulative apparaîtra par exemple lorsque trois processeurs sont disponibles pour l'exécution de quatre tâches. On ne pourra exécuter plus de trois de ces tâches en même temps sans que l'on puisse savoir à l'avance laquelle sera retardée. - Les contraintes de type potentiel : Ce sont les contraintes de localisation temporelle (la tâche i ne doit pas commencer avant telle date ou au contraire doit être achevée avant telle date). - Les contraintes de successions ou positionnement entre les tâches ou d'antériorité (la date j ne peut pas commencer avant que la tâche i ne soit terminée, ou simplement, parvenue à un certain degré d'achèvement. - Les contraintes de type disjonctif : elles imposent la disjonction de deux intervalles de temps relatifs par exemple à l'exécution de deux tâches i et j qui ne peuvent être réalisées simultanément. - Les contraintes de type commutatif, concernant l'évolution dans le temps du volume total des moyens humains et matériels consacrés à l'exécution des tâches (en général il est difficile d'en tenir compte). - Les contraintes du temps alloué : Les dates limites des tâches ou la durée totale d'un projet - Les contraintes du calendrier : Horaires du travail. Remarque Toutes ces contraintes peuvent être exprimées sous formes d'inégalités de potentiel. - Contrainte exprimable à l'aide d'une seule inégalité de potentiel : C'est le cas de la contrainte e succession entre deux tâches i et j (i avant j). On écrit tj – ti ≥ pi - Contrainte exprimable à l'aide de deux conjonctions d'inégalités de potentiel : C'est le cas de chevauchement par exemple : Ou cj – ti ≥ 0 et ci – tj ≥ 0 - Les contraintes de ressources : Elles sont liées à l'utilisation et la disponibilité des ressources requises par les tâches. On note : ti ci tj cj Tk(t) ={ i∈ {1, ..., n} / t∈[ti, ti + pi] } L'ensemble des tâches qui consomment la ressource k à l'instant t. On traduit la limitation de la capacité de k par : ( ) ∑ ∈ ≤ ∀ t T i k i k A a t II. 4. Fonction - objectif Il faut programmer les tâches de façon à optimiser un certain objectif qui sera, suivant les cas: - La minimisation de la durée totale (critère le plus fréquemment utilisé) - Ou le respect des dates de commandes (dates échues) - Ou la minimisation d'un coût (coût de production) D'une manière générale, trois types d'objectifs sont essentiels dans la résolution des problèmes d'ordonnancement : - L'utilisation efficace des ressources - Un délai d'exécution des tâches aussi faible que possible - Le respect des dates d'achèvement prescrites à l'avance Les variables intervenant le plus souvent dans l'expression de la fonction économique (fonction - objectif) sont : - La date ci de fin d'exécution de la tâche i, - Le retard Ti = max (0, ci - di) de la tâche i, - L'indicateur de retard Ui (Ui = 0 si ci ≤ di , Ui = 1 sinon) Les critères usuels sont : - La durée totale cmax = max(ci), - Le plus grand retard Tmax = max Ti, - Le retard moyen pondéré ∑ i iT w - Ou les stocks d'encours ∑ i iT w Le tableau suivant propose une typologie des problèmes d’ordonnancement : Caractéristiques Choix possibles (non exclusifs) Quantité de moyens (nature) Illimitée Limitée (renouvelables) Limitée (consommables) Organisation des moyens Une machine M machines parallèles Machines en série flowshop, jobshop Gammes non linéaires Contraintes de fabrication Préemption autorisée Chevauchement Temps de transit Encours limités Types de fabrication Unitaire Atelier (petite série) Masse (grande série) Continue Répétition des travaux Cyclique ou répétitif A la commande ou non répétitif Hypothèses sur la commande Statique (connue à priori) Dynamique (arrivée continue en temps réel) Critères principaux d'appréciation des solutions Minimisation de cycle de fabrication Minimisation des encours Minimisation des retards Pour un problème d'ordonnancement répétitif, le critère usuel est la maximisation de débit, c'est à dire, du nombre moyen d'itérations par unité de temps. Tous ces critères sont dits réguliers, car ils sont des fonctions décroissantes des dates de fin d'exécution des tâches. III. Critères réguliers et ensembles dominants La plus part des critères usuels (fonction - objectif) qui s'expriment en fonction des dates de fin d'exécution des tâches : C1, C2, ..., Cn, possèdent une propriété dite de régularité qui permet souvent de mettre en évidence un sous-ensemble d'ordonnancements contenant la uploads/Management/ ch3-ro.pdf