Ce mémoire traite de la résolution de problèmes d’ordonnancement à l’aide de la programmation par contraintes. Il s’intéresse principalement aux contraintes globales et particulièrement à la contrainte cumulative. Il passe en revue les règles permettant de la filtrer et les principaux algorithmes qui les appliquent. Il explique le Edge-Finder de Vilím et son arbre cumulatif. Il propose un algorithme plus performant et plus général pour appliquer les règles découlant du raisonnement énergétique. Le mémoire traite du cas particulier où toutes les tâches sont de durée identique. Pour modéliser efficacement ce type de problèmes, on y conçoit la contrainte multi-inter-distance. L’algorithme d’ordonnancement de López-Ortiz et Quimper est adapté pour réaliser un algorithme qui applique la cohérence de bornes. La contrainte multi-inter-distance s’avère efficace à résoudre le problème de séquençage des atterrissages d’avions du banc d’essai d’Artiouchine et Baptiste. / This thesis discusses how to solve scheduling problems using constraint programming. We study global constraints and particularly the Cumulative constraint. We survey its main filtering rules and their state-of-the-art filtering algorithms. We explain the Vilím’s Edge-Finder and its cumulative tree.We introduce a more efficient and more general algorithm that enforces the filtering rules from the energetic reasoning. We study the special case where all tasks have identical processing times. To efficiently model such problems, we introduce the Multi-Inter-Distance constraint. The scheduling algorithm by López-Ortiz and Quimper is adapted to produce a filtering algorithm enforcing bounds consistency. The constraint Multi-Inter-Distance is proved efficient to solve the runway scheduling problem on the benchmark by Artiouchine and Baptiste.

Titre de l'écran-titre (visionné le 21 mars 2024) / L'ordonnancement en milieu agroalimentaire est complexe. En effet, les planificateurs doivent prendre en compte de nombreuses contraintes comme les allergènes, la disponibilité des ingrédients et de la main-d'oeuvre. Ceci devient rapidement une tâche complexe, surtout quand les horaires de production doivent être refaits à la moindre perturbation (nouvelle commande, retard dans l'arrivée des matières premières, etc.). C'est pourquoi il est naturel de faciliter la tâche de ceux-ci grâce à des outils d'aide à la décision comme des modèles d'optimisation. Les problèmes d'ordonnancement de la production sont étudiés depuis longtemps dans la littérature scientifique. Plus récemment, Ku et Beck ont démontré le potentiel du paradigme de la programmation par contraintes sur le problème d'ordonnancement d'atelier (Job-shop Scheduling Problem). Ceci et le fait que très peu d'articles combinent l'utilisation de la programmation par contraintes aux problèmes d'ordonnancement dans le milieu agroalimentaire ont motivé ces travaux de recherche. Dans ce mémoire, l'utilisation de la programmation par contraintes sur des problèmes d'ordonnancement tirés de l'entreprise Biscuits Leclerc a été étudiée. Également, d'autres techniques d'optimisation comme la recherche locale à voisinage large ont été utilisées. Les contributions de la recherche sont autant au niveau scientifique en remplissant un trou existant dans la littérature qu'au niveau industriel en résolvant un problème auquel fait face Biscuits Leclerc quotidiennement. / The scheduling in the food industry is complex. Indeed, planners must take into account many constraints such as the presence of allergens, the availability of ingredients, and employees. This quickly becomes a complex task, especially when production schedules have to be redone at the slightest disruption (new orders, delays in the arrival of raw materials, etc.). This is why it is natural to make their task easier with the help of decision support tools such as optimization models. Production scheduling problems have been studied for a long time in the scientific literature. More recently, Ku and Beck demonstrated the potential of the constraint programming paradigm on the Job-shop Scheduling Problem. This and the fact that very few articles combine the use of constraint programming with scheduling problems in the food industry have motivated the current research work. In this master thesis, the use of constraint programming on scheduling problems taken from the company Biscuits Leclerc have been studied. Also, other optimization techniques such as Large Neighborhood Search were used. The contributions of the research are as much at the scientific level by filling an existing gap in the literature as at the industrial level by solving a problem that Biscuits Leclerc faces in their everyday life.

Nowadays, computer systems are everywhere. From simple portable devices such as watches and MP3 players to large stationary installations that control nuclear power plants, computer systems are now present in all aspects of our modern and every-day life. In about only 70 years, they have completely perturbed our way of life and they reached a so high degree of sophistication that they will be soon capable of driving our cars and cleaning our houses without any human intervention. As computer systems gain in responsibilities, it becomes essential that they provide both safety and reliability. Indeed, a failure in systems such as the anti-lock braking system (ABS) in cars could threaten human lives and generate catastrophic and irreversible consequences. Hence, for many years, researchers have addressed these emerging problems of system safety and reliability which come along with this fulgurant evolution. This thesis provides a general overview of embedded real-time computer systems, i.e., a particular kind of computer system whose number grows daily. We provide the reader with some preliminary knowledge and a good understanding of the concepts that underlie this emerging technology. We focus especially on the theoretical problems related to the real-time issue and briefly summarizes the main solutions, together with their advantages and drawbacks. This brings the reader through all the conceptual layers constituting a computer system, from the software level---the logical part---that specifies both the system behavior and requirements to the hardware level---the physical part---that actually performs the expected treatments and reacts to the environment. In the meanwhile, we introduce the theoretical models that allow researchers for theoretical analyses which ensure that all the system requirements are fulfilled. Finally, we address the energy consumption problem in embedded systems. We describe the various factors of power dissipation in modern technologies and we introduce different solutions to reduce this consumption./Cette thèse se focalise sur un type de systèmes informatiques bien précis appelés “systèmes embarqués temps réel”. Un système est dit “embarqué” lorsqu’il est développé afin de servir un but bien précis. Un téléphone portable est un parfait exemple de système embarqué étant donné que toutes ses fonctionnalités sont rigoureusement définies avant même sa conception. Au contraire, un ordinateur personnel n’est généralement pas considéré comme un système embarqué, les concepteurs ne sachant pas à l’avance à quelles fins il sera utilisé. Une grande partie de ces systèmes embarqués ont des contraintes temporelles très fortes, ce qui les distingue encore plus des ordinateurs grand public. A titre d’exemple, lorsqu’un conducteur de voiture freine brusquement, l’ordinateur de bord déclenche l’application ABS et il est primordial que cette application soit traitée endéans une courte échéance. Autrement dit, cette fonctionnalité ABS doit être traitée prioritairement par rapport aux autres fonctionnalités du véhicule. Ce type de système embarqué est alors dit “temps réel”, dû à ces notions de temps et de priorités entre les applications. La problèmatique posée par les systèmes temps réel est la suivante. Comment déterminer, à tout moment, un ordre d’exécution des différentes fonctionnalités de telle sorte qu’elles soient toutes exécutées entièrement endéans leur échéance ? De plus, avec l’apparition récente des systèmes multiprocesseurs, cette problématique s’est fortement complexifiée, vu que le système doit à présent déterminer quelle fonctionnalité s’exécute à quel moment sur quel processeur afin que toutes les contraintes temporelles soient respectées. Pour finir, ces systèmes embarqués temp réel multiprocesseurs se sont rapidement retrouvés confrontés à un problème de consommation d’énergie. Leur demande en terme de performance (et donc en terme d’énergie) à évolué beaucoup plus rapidement que la capacité des batteries qui les alimentent. Ce problème est actuellement rencontré par de nombreux systèmes, tels que les téléphones portables par exemple. L’objectif de cette thèse est de parcourir les différents composants de tels système embarqués et de proposer des solutions afin de réduire leur consommation d’énergie.

L'algorithme génétique (AG), est fondé sur les méanismes de codage, sélection, croisement, mutation et insertion. Chacun présente plusieurs choix ce qui donne résultat à plusieurs variantes de AG.<br /><br /> Nous avons obtenu une variante meilleure d'algorithme génétique pour le problème du voyageur de commerce. Dans laquelle, nous avons introduit notre nouvel opérateur de croisement Cedrx qui est jumelé avec l'opérateur edrx donne de bons résultats. <br /><br /> Cette étude, nous a permis de créer des variantes efficaces d'algorithme génétique pour les probèmes suivants: <br /><br />+ Le problème d'ordonnancement dans les ateliers de type Job Shop;<br />+ Le problème des atterrissages d'avions (PAA);<br />+ Le problème d'ordonnancement des véhicules sur une chaîe de <br /> production dans une usine (POV).

Cette thèse se situe dans le domaine des systèmes informatiques temps-réel embarqués, plus particulièrement les logiciels embarqués dans l'automobile pour tous les dispositifs émergents et à venir d'évaluation des systèmes d'aide à la conduite (ADAS) pour les prochaines générations de véhicules. Ce document présente les trois axes principaux des travaux de cette thèse : Le premier axe comprend le développement d'un middleware reconfigurable dynamiquement, SCOOT-R. Le deuxième axe concerne le développement des techniques d'ordonnancement distribuées des opérations SCOOT-R avec un objectif de qualité de service de bout en bout. Finalement, le développement des techniques d'ordonnancement régulé pour l'adaptation du système à des situations de conduite et comportements du conducteur variables. Dans ce cas l'importance des fonctions est adaptée suivant le contexte momentané du système.

Cette thèse se situe dans le cadre de la planification de la production à moyen et court terme dans un environnement de production à la commande et s'intéresse plus particulièrement à une problématique d'ordonnancement de tâches. Elle propose une approche décisionnelle à deux niveaux permettant conjointement l'ajustement charge-capacité des ressources et l'ordonnancement des opérations appartenant à un ensemble d'Ordres de Fabrication (OF). Le niveau supérieur (macro-ordonnancement) positionne les OF sur un horizon moyen-terme discrétisé en périodes et aide le décideur à élaborer une planification agrégée optimisée compte tenu de la politique de gestion retenue (heures supplémentaires, sous-traitance, retards, etc.). Ce niveau est modélisé par un programme linéaire en variables mixtes. Des mécanismes d'agrégation sont proposés. Ils permettent d'associer au niveau supérieur des données agrégées (par macro-périodes) obtenues à partir des données détaillées (définies sur le temps continu). L'étude s'intéresse également à des extensions du modèle de macro-ordonnancement dans le cas de la prise en compte de différents types de leviers décisionnels, de la prise en compte de ressources alternatives,... Le niveau inférieur (ordonnancement) positionne finement (en temps continu, horizon court-terme) les opérations sur les ressources pouvant être utilisées. Il est chargé de "suivre" le macro-ordonnancement ayant optimisé le positionnement grossier des OF. Afin d'intégrer les deux niveaux décisionnels, différents mécanismes de "guidage" sont proposés. Ces mécanismes permettent de désagréger les décisions prises au niveau supérieur. Ces mécanismes permettent l'utilisation de logiciel d'ordonnancement standard au niveau inférieur. Des expérimentations numériques sont effectuées afin d'étudier les performances de la structure multiniveau. Ces expérimentations permettent d'apprécier le comportement de la structure décisionnelle face à différents grandeurs d'éléments c aractéristiques de l'approche : pas de discrétisation, mécanismes de guidage, taux de contraintes,...

Nowadays, computer systems are everywhere. From simple portable devices such as watches and MP3 players to large stationary installations that control nuclear power plants, computer systems are now present in all aspects of our modern and every-day life. In about only 70 years, they have completely perturbed our way of life and they reached a so high degree of sophistication that they will be soon capable of driving our cars and cleaning our houses without any human intervention. As computer systems gain in responsibilities, it becomes essential that they provide both safety and reliability. Indeed, a failure in systems such as the anti-lock braking system (ABS) in cars could threaten human lives and generate catastrophic and irreversible consequences. Hence, for many years, researchers have addressed these emerging problems of system safety and reliability which come along with this fulgurant evolution. <p><p>This thesis provides a general overview of embedded real-time computer systems, i.e. a particular kind of computer system whose number grows daily. We provide the reader with some preliminary knowledge and a good understanding of the concepts that underlie this emerging technology. We focus especially on the theoretical problems related to the real-time issue and briefly summarizes the main solutions, together with their advantages and drawbacks. This brings the reader through all the conceptual layers constituting a computer system, from the software level---the logical part---that specifies both the system behavior and requirements to the hardware level---the physical part---that actually performs the expected treatments and reacts to the environment. In the meanwhile, we introduce the theoretical models that allow researchers for theoretical analyses which ensure that all the system requirements are fulfilled. Finally, we address the energy consumption problem in embedded systems. We describe the various factors of power dissipation in modern technologies and we introduce different solutions to reduce this consumption./Cette thèse se focalise sur un type de systèmes informatiques bien précis appelés “systèmes embarqués temps réel”. Un système est dit “embarqué” lorsqu’il est développé afin de servir un but bien précis. Un téléphone portable est un parfait exemple de système embarqué étant donné que toutes ses fonctionnalités sont rigoureusement définies avant même sa conception. Au contraire, un ordinateur personnel n’est généralement pas considéré comme un système embarqué, les concepteurs ne sachant pas à l’avance à quelles fins il sera utilisé. Une grande partie de ces systèmes embarqués ont des contraintes temporelles très fortes, ce qui les distingue encore plus des ordinateurs grand public. A titre d’exemple, lorsqu’un conducteur de voiture freine brusquement, l’ordinateur de bord déclenche l’application ABS et il est primordial que cette application soit traitée endéans une courte échéance. Autrement dit, cette fonctionnalité ABS doit être traitée prioritairement par rapport aux autres fonctionnalités du véhicule. Ce type de système embarqué est alors dit “temps réel”, dû à ces notions de temps et de priorités entre les applications. La problèmatique posée par les systèmes temps réel est la suivante. Comment déterminer, à tout moment, un ordre d’exécution des différentes fonctionnalités de telle sorte qu’elles soient toutes exécutées entièrement endéans leur échéance ?De plus, avec l’apparition récente des systèmes multiprocesseurs, cette problématique s’est fortement complexifiée, vu que le système doit à présent déterminer quelle fonctionnalité s’exécute à quel moment sur quel processeur afin que toutes les contraintes temporelles soient respectées. Pour finir, ces systèmes embarqués temp réel multiprocesseurs se sont rapidement retrouvés confrontés à un problème de consommation d’énergie. Leur demande en terme de performance (et donc en terme d’énergie) à évolué beaucoup plus rapidement que la capacité des batteries qui les alimentent. Ce problème est actuellement rencontré par de nombreux systèmes, tels que les téléphones portables par exemple. L’objectif de cette thèse est de parcourir les différents composants de tels système embarqués et de proposer des solutions afin de réduire leur consommation d’énergie. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Cette thèse représente une étude d'un nouvel indicateur d'aide à la décision pour le problème d'ordonnancement d'ateliers de production sous présence d'incertitudes. Les contributions apportées dans ce travail se situent dans le contexte des groupes d'opérations permutables. Cette approche consiste à proposer une solution d'ordonnancement flexible caractérisant un ensemble fini non-énuméré d'ordonnancements. Un opérateur est ensuite censé sélectionner l'ordonnancement qui répond le mieux aux perturbations survenues dans l'atelier. Nous nous intéressons plus particulièrement à cette phase de sélection et nous mettons l'accent sur l’intérêt de l'humain pour la prise de décision. Dans un premier temps, nous présentons le meilleur des cas; indicateur d'aide à la décision pour le calcul du meilleur ordonnancement caractérisé par l'ordonnancement de groupes. Nous proposons des bornes inférieures pour le calcul des dates de début/fin des opérations. Ces bornes sont ensuite implémentées dans une méthode de séparation et d'évaluation permettant le calculer du meilleur des cas. Grâce à des simulations effectuées sur des instances de job shop de la littérature, nous mettons l'accent sur l'utilité et la performance d'un tel indicateur dans un système d'aide à la décision. Enfin, nous proposons une Interface Homme-Machine (IHM) adaptée à l'ordonnancement de groupes et pilotée par un système d'aide à la décision multicritères. L'implémentation de cette IHM sur un cas d'étude réel a permis de soulever certaines pratiques efficaces pour l'aide à la décision dans le contexte de l'ordonnancement sous incertitudes. / This thesis represents a study of a new decision-aid criterion for manufacturing scheduling under uncertainties. The contributions made in this work relate to the groups of permutable operations context. This approach consists of proposing a flexible scheduling solution characterizing a non-enumerated and finite set of schedules. An operator is then supposed to select the appropriate schedule that best copes with the disturbances occurred on the shop floor. We focus particularly on this selection phase and we emphasize the important of the human for decision making. First, we present the best-case; a decision-aid criterion for computing the best schedule characterized by the groups of permutable operations method. We propose lower bounds for computing the best starting/completion time of operations. These lower bounds are then implemented in a branch and bound procedure in order to compute the best-case. Through to several simulations carried out on literature benchmark instances, we stress the usefulness of such criterion in a decision-aid system. Finally, we propose a Human-Machine-Interface (HMI) adapted to the groups of permutable operations and driven by a multi-criteria decision-aid system. The implementation results of this HMI on a real case study provided some insight about the practice of decision-making and scheduling under uncertainties.

Le thème de ce mémoire est l'ordonnancement dans les ateliers de production. L'objectif est d'étudier différents modèles classiques en analysant les liens et différences entre ces modèles et les problèmes pratiques associés. Les méthodes utilisées sont l'analyse de problèmes de nos partenaires industriels, l'étude de la complexité des problèmes ou de la structure des solutions et la proposition de méthodes de résolution exactes ou approchées. Le premier axe de cette thèse est l'étude de problèmes d'ordonnancement avec contraintes de ressources d'entrée/sortie. Les environnements considérés sont les flowshops robotisés et le nouveau modèle d'indisponibilité des opérateurs. Le second axe abordé concerne l'ordonnancement avec high multiplicity où les pièces sont agrégées en catégories. La description complète d'un ordonnancement (c'est-à-dire les instants de fabrication des tâches) n'est que pseudo-polynomiale de la taille de l'instance.

Dans cette thèse, nous étudions trois problèmes d'ordonnancement de la chaîne logistique dans le modèle de production à la demande. Le premier problème est un problème d'ordonnancement de production et de distribution intermédiaire dans une chaîne logistique avec un producteur et un prestataire logistique. Le deuxième problème est un problème d'ordonnancement de production et de distribution aval avec des dates de début au plus tôt et des dates limites de livraison dans une chaîne logistique avec un producteur, un prestataire logistique et un client. Le troisième problème est un problème d'ordonnancement de production et de distribution aval avec des temps de réglage et des fenêtres de temps de livraison dans une chaîne logistique avec un producteur, un prestataire logistique et plusieurs clients. Pour les trois problèmes, nous étudions les problèmes d'ordonnancement individuels et les problèmes d'ordonnancement coordonnés. Nous proposons des algorithmes polynomiaux ou prouvons la NP-Complétude de ces problèmes, et développons des algorithmes exacts ou heuristiques pour résoudre les problèmes NP-Difficiles. Nous proposons des mécanismes de coordination et évaluons le bénéfice de la coordination. / In this dissertation, we aim at investigating three supply chain scheduling problems in the make-To-Order business model. The first problem is a production and interstage distribution scheduling problem in a supply chain with a manufacturer and a third-Party logistics (3PL) provider. The second problem is a production and outbound distribution scheduling problem with release dates and deadlines in a supply chain with a manufacturer, a 3PL provider and a customer. The third problem is a production and outbound distribution scheduling problem with setup times and delivery time windows in a supply chain with a manufacturer, a 3PL provider and several customers. For the three problems, we study their individual scheduling problems and coordinated scheduling problems: we propose polynomial-Time algorithms or prove the intractability of these problems, and develop exact algorithms or heuristics to solve the NP-Hard problems. We establish mechanisms of coordination and evaluate the benefits of coordination.