Thèse de doctorat : génie industriel : Ecole centrale de Paris : 2009. / Titre provenant de l'écran-titre. Bibliogr. 116 réf.

Thèse (M.Inf.) -- Université du Québec à Montréal, programme offert par extension à l'Université du Québec à Chicoutimi, 2008. / La p. de t. porte en outre: Mémoire présenté à l'Université du Québec à Chicoutimi comme exigence partielle de la maîtrise en informatique offerte à l'Université du Québec à Chicoutimi en vertu d'un protocole d'entente avec l'Université du Québec à Montréal. CaQQUQ Bibliogr.: f. 79-88. Publié aussi en version électronique. CaQQUQ

Des perturbations industrielles ont amené de profondes transformations des systèmes d'ordonnancement et de planification en temps réel, dans le contexte d'un environnement manufacturier de plus en plus dynamique coomme l'humain est au cœur de ces processus. Il est nécessaire d'assurer une synergie entre les opérateurs et les machines. En plus des objectifs comme la réduction des retards et des coûts, il serait essentiel de prendre en compte les aspects tels que l'équité de la charge de travail entre les opérateurs et la répétitivité des tâches. Toutefois dans la littérature, l'intégration de ces facteurs est peu abordée. Nous proposons dans ce projet d'appliquer des méthodes qui visent à réduire l'écart de charge de travail entre les opérateurs tout en favorisant la répétitivité des tâches assignées de manière à favoriser la prise d'habitudes - deux objectifs pouvant sembler contradictoires. Dans cet esprit, nous avons en premier lieu pris le temps de bien comprendre le modèle d'ordonnancement initial utilisé par le partenaire industriel, puis nous avons fait un survol de la littérature en relation avec l'allocation des tâches aux opérateurs dans le milieu manufacturier et la prise en compte des deux aspects : l'équité de la charge de travail et la répétitivité des tâches. En deuxième lieu, nous avons proposé deux familles de méthodes pour assurer l'équité de la charge de travail sans modifier le modèle d'ordonnancement déjà en place. La première famille fait le prétraitement des données en entrée du système de planification. La deuxième famille consiste à utiliser des approches de post-traitement pour ajuster le plan d'allocation. Des méthodes combinées ont aussi été testées. Les méthodes combinées avec des données réelles ont démontré une supériorité par rapport aux autres méthodes, avec une réduction de 70% de l'écart de charge de travail entre les opérateurs sur une semaine type de travail par rapport au modèle initial. En troisième lieu, nous avons proposé de nouvelles méthodes pour maximiser la répétitivité des tâches des opérateurs. Tenant compte de la complexité du modèle initial et la volonté de cibler plusieurs objectifs à la fois (retards, équité et répétitivité), un compromis entre l'équité et la répétitivité est recherché. Une étude expérimentale utilisant des données réelles collectées chez notre partenaire industriel démontre qu'en permettant seulement une dégradation de 10% du respect de l'équité, nous pouvons atteindre un niveau acceptable de répétitivité. / Industrial disruptions are leading to profound transformations in real-time scheduling and planning systems, in the context of an increasingly dynamic manufacturing environment. Humans are at the heart of these processes, and it is essential to ensure synergy between operators and machines. Although these systems often focus on objectives such as reducing delays and costs, it would be essential to take into account aspects such as workload equity between operators and task repeatability. However, the integration of these factors remains complex. In this project, we are proposing to apply methods that aim to reduce the difference in workloads between operators, while at the same time encouraging the repeatability of assigned tasks so as to promote operators' habits - two objectives that may seem contradictory. To this end, we first took the time to fully understand the initial scheduling model used by the industrial partner, then reviewed the literature in relation to the operator in new industrial eras and the two aspects in question. Second, we proposed two families of methods to ensure workload fairness without modifying the existing scheduling model. The first family involves preprocessing the data input to the scheduling system. The second family uses post-processing approaches to adjust the allocation plan. Combined methods were also tested. The combined methods demonstrated superiority over the other methods, with a 70% reduction in the difference in workload between operators over a typical working week compared with the initial model. Finally, new methods have been proposed to maximize the repeatability of tasks. Taking into account the complexity of the initial model and the desire to target several objectives at once (delays, fairness and repeatability), a compromise between fairness and repeatability is sought. An experimental study using real data collected from our industrial partner shows that by allowing only a 10% degradation in fairness compliance, we can achieve an acceptable level of repeatability.

L'environnement industriel concurrentiel auquel font face les entreprises manufacturières les pousse à se doter d'un système de production hautement réactif capable de pallier aux incertitudes et aux fluctuations imprévisibles de la demande. La classe des systèmes manufacturiers reconfigurables (RMS pour Reconfigurable Manufacturing System en anglais) fournit une solution efficace et prometteuse à ce défi. Contrairement aux systèmes classiques comme les lignes de fabrication dédiées (DML) et les systèmes de fabrication flexibles (FMS), qui n'arrivent pas à surmonter ces challenges à cause de leurs conceptions qui limitent les options pour mieux gérer les variations de la demande et adapter la capacité du besoin du marché, les RMS présentent une bonne alternative possédant la capacité d'adapter la configuration du système manufacturier au fil du temps afin de répondre aux exigences du marché. Cela est assuré par les machines-outils reconfigurables (RMT pour Reconfigurable Machine Tools en anglais) qui sont considérées comme la composante fondamentale pour un RMS. Ce mémoire propose une nouvelle approche d'ordonnancement de la production en considérant les machines-outils reconfigurables. L'objectif est de minimiser le makespan. Un modèle linéaire mixte en nombres entiers ainsi qu'une heuristique adaptée à deux phases ont été proposés afin de résoudre le problème. Les performances des deux méthodes de résolution sont analysées et comparées pour différentes instances générées aléatoirement. Une analyse de performance des méthodes suite aux variations de certains paramètres est présentée. Finalement, un contexte dynamique (des nouvelles commandes qui surviennent au cours de la production) est considéré où la performance de l'approche heuristique surpasse celle de la méthode exacte pour les instances considérées. / The competitive manufacturing environment faced by manufacturing companies requires a highly responsive production system capable of dealing with uncertainties and unpredictable fluctuations of demand. Reconfigurable Manufacturing Systems (RMS) provide an effective and promising solution to this challenge. Unlike conventional systems such as Dedicated Manufacturing Lines (DML) and Flexible Manufacturing Systems (FMS) which fail to overcome these challenges due to their designs which do not support variations in demand and changes in capacity, RMS present a good alternative with the ability to change the system configuration over time to meet market demands. This is ensured by reconfigurable machine tools (RMT) which are considered as the fundamental component for an RMS. This thesis proposes a new approach to production scheduling for manufacturing systems with reconfigurable machine tools. The objective is to minimize the makespan. A linear mixed-integer model based on the sequence of operations as well as an adapted two-phase heuristic are proposed to solve the problem. The performances of the two resolution methods are analyzed and compared for different randomly generated instances. An analysis of the performance of the methods following variations in certain parameters is presented. Finally, a dynamic context (new orders arise during production) is considered where the heuristic outperforms the exact method.

Les applications temps réel, le plus souvent dédiées au contrôle de procédé, sont soumises à des contraintes temporelles strictes, destinées à garantir la sécurité et la cohérence du procédé contrôlé. Les applications temps réel étant des applications multi tâches, elles doivent être ordonnancées, le critère sine qua non de qualité de la stratégie d'ordonnancement étant la garantie du respect des contraintes temporelles. Ces applications sont de plus en plus souvent déployées sur des architectures multiprocesseurs. Le problème de l'ordonnancement doit donc être posé dans ce contexte, où de nombreux problèmes doivent encore être abordés. Notons tout d'abord que dans le cas multiprocesseur, il n'existe pas d'ordonnancement en ligne optimal dans le cas général, le problème de l'ordonnancement est NP-complet, et des anomalies d'ordonnancement apparaissent même lorsque l'on ne considère que des tâches indépendantes (une durée d'exécution plus courte que prévue peut provoquer une faute temporelle). Nous avons envisagé de prendre en compte la possibilité que des pannes matérielles surviennent. Nous avons étudié les mécanismes de reprise après la panne d'un processeur, dans le cas où l'application est ordonnancée par EDF, puis par un algorithme P-équitable. Ces mécanismes nécessitent de disposer d'un certain nombre de résultats généraux. Tout d'abord, nous avons étendu la définition de la P-équité à un contexte plus large que celui de la littérature, à savoir aux tâches à départs différés et à échéances contraintes, puis nous avons établi une condition suffisante d'ordonnançabilité dans ce contexte, dont nous avons étudié les performances à l'aide de simulations. Enfin, nous avons proposé un protocole efficace de gestion des flux apériodiques qui s'appuie sur une distribution P-équitable des temps creux. Cette répartition peut être obtenue soit en ordonnançant les tâches périodiques par une stratégie P-équitable quand le contexte le permet, soit via une analyse hors-ligne à base de réseaux de Petri. Nous avons proposé une technique d'extraction qui permet de forcer la répartition équitable des temps creux.

Deux techniques sont utilisées pour vérifier que des tâches temps réel respectent bien leurs échéances temporelles : les tests d'ordonnançabilité qui renvoient un résultat binaire (ordonnançable ou non) et les calculs de temps de réponse (Response Time Analysis - RTA) qui déterminent la longueur du plus long intervalle de temps entre le réveil et la terminaison d'une tâche. Ces deux approches ont une complexité pseudo-polynomiale et notons qu'aucun algorithme polynomial n'est connu. Dans ce contexte, elles ne sont pas particulièrement appropriées pour la conception intéractive des systèmes temps réel ou pour analyser des systèmes distribués à l'aide d'une analyse holistique. Dans de tels scénarios, un algorithme pseudo-polynomial est lent, puisque les calculs des temps de réponse des tâches sont exécutées à de nombreuses reprises. De plus, pour certains systèmes temps réels, tels que dans les systèmes de contrôle-commande, il est nécessaire de connaître le pire temps de réponse des tâches et non seulement la décision binaire sur l'ordonnançabilité des tâches. Dans ce contexte, il peut être acceptable d'utiliser un algorithme plus rapide qui fournit une analyse approchée au lieu d'utiliser des analyses reposant sur des calculs exacts. Comme cette approximation va introduire du pessimisme dans le processus de décision, il est souhaitable de le quantifier d'une manière à définir un compromis entre le temps de calcul et l'exigence de ressource du processeur. C'est la raison pour laquelle, dans ce travail, nous proposons des algorithmes pour calculer efficacement des bornes supérieures des pires temps de réponse et nous présentons des résultats sur leurs qualités dans le pire cas (analyse de compétitivité avec augmentation de ressource) et en moyenne (simulations).

Dans nos travaux, nous nous sommes intéressés aux politiques d'ordonnancement en-ligne, pour lesquelles l'ordre d'exécution des tâches est déterminé sur la base des tâches actives dans le système et sans connaissance a priori des tâches qui arriveront dans le futur. Cette problématique s'étend aux réseaux informatiques pour ordonnancer les messages sur le réseau informatique interconnectant les diérents calculateurs du système temps réel. La première contribution concerne le placement et ordonnancement simultanés des tâches dans un système temps réel distribué, permettant de minimiser le nombre de processeurs nécessaires pour respecter les spécications temporelles des tâches. La seconde contribution concerne les tâches à criticité multiple. L'objectif de ce modèle est de prendre en compte la notion de criticité des diérentes tâches, comme par exemple dans la norme DO-178B utilisée en aéronautique. Enn, nous nous sommes intéressés aux systèmes multiprocesseurs ordonnancés par des algorithmes d'ordonnancement semi-partitionné. Cette classe d'algorithme utilise une stratégie par partitionnement pour répartir les tâches parmi les processeurs tout en autorisant la migration des tâches qui ne peuvent pas être aectées à un processeur donné sans violation d'échéance.

Reproduction de : Thèse de doctorat : Systèmes industriels : Toulouse, INPT : 2005. / Titre provenant de l'écran-titre. Bibliogr. 183 réf.

Thèse de doctorat : Informatique : Lyon, École normale supérieure (sciences) : 2006. / Bibliogr. p. 161-175.

Thèse de doctorat : Informatique : Paris 12 : 2006. / Version électronique uniquement consultable au sein de l'Université Paris 12 (Intranet). Titre provenant de l'écran-titre. Pagination : 139 p. Bibliogr. : 86 réf.