Nous abordons dans cette thèse deux types de problèmes d’ordonnancement sur une machine ou sur des machines parallèles : 1. les problèmes d’ordonnancement de type juste-à-temps : il s’agit de déterminer un ordonnancement de sorte que les travaux se terminent le plus près possible de leur date de fin souhaitée. On considère le cas où la date de fin souhaitée commune est connue et le cas où elle est à déterminer. De nouveaux algorithmes exacts sont proposés. Des schémas d’approximation sont élaborés. 2. les problèmes d’ordonnancements de travaux interférants : il s’agit de déterminer un ordonnancement qui permet d’optimiser un critère pour tous les travaux, sachant que la solution trouvée doit permettre également l’optimisation d’un autre critère défini uniquement sur un sous-ensemble des travaux. Il s’agit ici d’un nouveau problème d’ordonnancement multicritère, différent de la notion classique. Les approches considérées pour trouver une solution non dominée sont l’approche e-contrainte, la combinaison linéaire de critères et le goal programming. De nouveaux résultats de complexité sont montrés et des algorithmes exacts sont développés. / In this thesis, we consider two kinds of scheduling problems on a single machine or on parallel machines : 1. just-in-time scheduling problems : it aims to determine a schedule so that a job completes as close as possible to its due date.We consider the case where the common due date is known and the case where the common due date has to be fixed. New exact algorithms based on greedy algorithms and dynamic programming are proposed. Approximation schemes are given. 2. scheduling problems with interfering jobs : the aim is to determine a schedule that optimizes a criterion for the whole set of jobs and so that the solution optimizes another objective only for a subset of jobs. It is here a new multi-criteria scheduling problem, different from the classical notion. The approaches considered for finding a non-dominated solution are the e-constraint approach, the linear combination of criteria and the goal programming approach. New complexity results are proposed and exact algorithms are developed.

Les travaux présentés dans cette thèse visent à proposer des méthodes d’optimisation des changements de série sur des lignes de production afin d’améliorer la flexibilité de la production. Nous modélisons ce problème sous forme de problème à machines parallèles non reliées : les tâches sont les réglages des machines d’une ligne et les ressources sont des opérateurs. Nous prenons en compte notamment, la structure de la ligne de production qui comporte des machines en plusieurs exemplaires, les compétences des opérateurs et leurs disponibilités. Les méthodes utilisées sont une procédure par séparation et évaluation dans le cas où la ligne est composée de machines en série et des heuristiques de type descente locale et algorithme génétique dans le cas général. Nous proposons des bornes permettant d’évaluer les performances des méthodes. Pour le cas série, nous proposons également une méthode hybride faisant collaborer une procédure par séparation et évaluation et un algorithme génétique. / The work presented in this thesis aims at proposing new methods for setup optimization in production lines in order to improve production flexibility. This problem is modelized using an unrelated parallel machines problem : the tasks are the setup tasks of each machine of the production line and the ressources are the operators. We take into consideration the production line structure that may contain multiple machines on some stages and the skills of operators. The skill model has been validated using a simulation approach. We have used a Branch-and-Bound to solve the special case of serial production line and hill climbing and genetic algorithm meta heuristics for the general case. In both cases, we propose bounds that are used to evaluate the performances of the different methods. For the serial special case, we also propose a hybrid algorithm that use both a genetic algorithm and a Branch-and-Bound that are colaborating together.

Les machines parallèles (MPs) existent depuis plus d'un demi-siècle et ils ont fait l'objet d'études intensives. Par opposition avec leurs homologues de structure série, ces mécanismes sont constitués de plusieurs chaînes cinématiques qui relient la base fixe à la plateforme mobile. L'intérêt de ces architectures s'explique par les nombreux avantages qu'elles offrent, parmi lesquels: une rigidité élevée, un rapport important charge/poids global, des capacités dynamiques élevées en raison des masses en mouvement réduites (en particulier lorsque les actionneurs sont sur ou près de la base), une meilleure précision, des fréquences propres plus élevées, etc. Néanmoins, leur exploitation comme machines-outils reste timide et limitée, et le plus souvent elles ne dépassent pas le stade d'étude et de prototype de laboratoires universitaires ou de fabricants de machines-outils. Les principaux inconvénients qui entravent la généralisation des MPs dans l'industrie sont les suivants: un espace de travail limité, des débattements angulaires réduits, la présence de configurations singulières, la complexité de conception, les difficultés d'étalonnage, les problèmes causés par les collisions, la complexité du contrôle/commande (en particulier dans le cas de redondance à actionnement), etc. De plus, si les MPs ont rencontré un grand succès dans les applications de pick-and-place grâce à leur rapidité (capacité d'accélération), leur précision reste inférieure à ce qui a été prévu initialement. Par ailleurs, on trouve également des MPs de très précision, mais malheureusement avec de faibles performances dynamiques. En partant du constat précédant, cette thèse se concentre sur l'obtention de MPs avec un bon compromis entre rapidité et précision. Nous commençons par donner un aperçu de la bibliographie disponible concernant MPs et les avancées majeures dans ce domaine, tout en soulignant les limites de performance des MPs, ainsi que les limites des outils de conception classique. En outre, nous insistons sur les outils d'évaluation des performances, et montrons leurs limites dès qu'il s'agit de traiter le cas de la redondance ou l'hétérogénéité des degrés de liberté (ddl). En effet, si la synthèse architecturale est un point dur de la conception de MPs, la synthèse dimensionnelle reposant sur des indices de performances réellement significatifs l'est également. Par conséquent, de nouveaux indices de performance sont proposés pour évaluer la précision, les capacités cinétostatiques et dynamiques des manipulateurs de manière générale qui apportent des solutions aux difficultés évoquées ci-dessus. Par la suite, plusieurs nouvelles architectures 3T-2R et 3T-1R (T: signifie ddl en translation et R signifie un ddl de rotation) sont présentées, à savoir MachLin5, ARROW V1, et ARROW V2 et ses versions dérivées ARROW V2 M1 et M2. En outre, la synthèse dimensionnelle d'ARROW V2 M2 est réalisée, et les performances de la machine sont évaluées. Finalement, des améliorations futures concernant la précision sont proposées au regard de premiers résultats obtenus sur le prototype. / Parallel manipulators (PMs) have been there for more than half a century and they have been subject of intensive research. In comparison with their serial counterparts, PMs consist of several kinematic chains that connect the fixed base to the moving platform. The interest in such architectures is due to the several advantages they offer, among which we mention: high rigidity and payload-to-weight ratio, elevated dynamical capabilities due to reduced moving masses (especially when the actuators are at or near the base), better precision, higher proper frequencies, etc. Nevertheless, despite of the aforementioned merits, their exploitation as machine tools is still timid and limited, in which they most often do not exceed the research and prototyping stages at university laboratories and machine tool manufacturers. The main drawbacks that hinder the widespread of parallel kinematic machines (PKMs) are the following: limited operational workspace and tilting capacity, presence of singular configurations, design complexities, calibration difficulties, collision-related problems, sophistication of control (especially in the case of actuation redundancy), etc. Besides, though PMs have met a great success in pick-and-place applications, thanks to their rapidity (acceleration capacity), still their precision is less than what has been initially anticipated. On the other hand, extremely precise PMs exist, but unfortunately with poor dynamic performance. Starting from the aforementioned problematics, the current thesis focuses on obtaining PKMs with a good compromise between rapidity and precision. We begin by providing a survey of the available literature regarding PKMs and the major advancements in this field, while emphasizing the shortcomings on the level of design as well as performance. Moreover, an overview on the state of the art regarding performance evaluation is presented and the inadequacies of classical measures, when dealing with redundancy and heterogeneity predicaments, are highlighted. In fact, if finding the proper architectures is one of the prominent issues hindering PKMs' widespread, the performance evaluation and the criteria upon which these PKMs are dimensionally synthesized are of an equal importance. Therefore, novel performance indices are proposed to assess precision, kinetostatic and dynamic capabilities of general manipulators, while overcoming the aforementioned dilemmas. Subsequently, several novel architectures with 3T-2R and 3T-1R degrees of freedom (T and R signify translational and rotational degrees of freedom), namely MachLin5, ARROW V1, and ARROW V2 with its mutated versions ARROW V2 M1/M2, are presented. Furthermore, the dimensional synthesis of the executed PKM, namely ARROW V2 M2, is discussed with its preliminary performances and possible future enhancements, particularly regarding precision amelioration.

Dans une machine sans mémoire commune, les processeurs communiquent par échanges de messages via des liaisons point à point. Les machines à connectique fixe utilisent des liaisons permanentes organisées selon un graphe d'interconnexion régulier tel qu'une grille ou un hypercube. Les messages qui ne beneficient pas d'une liaison directe doivent être routés de voisin en voisin jusqu'à leur destination. Les performances de ces machines sont tributaires de l'adéquation entre le graphe des communications entre tâches et le graphe d'interconnexion<br />physique des processeurs.<br />Cette thèse examine les possibilités offertes par les machines<br />à réseau d'interconnexion programmable, dites reconfigurables, et<br />deux modes de fonctionnement seront étudiés. La reconfiguration synchrone programme le réseau d'interconnexion en une seule fois avant l'exécution de l'application. Le routage des messages n'est pas totalement éliminé et l'utilisation possible de topologies irrégulières en complique la mise en oeuvre. Le réseau peut au contraire être reprogrammé systématiquement pour chaque message de telle sorte qu'il bénéficie d'une liaison directe le temps de son transfert. Ce mode de reconfiguration, dit asynchrone, impose<br />de fortes contraintes sur la vitesse de commande du réseau.<br />Cette thèse a été entreprise dans le cadre du projet de recherche<br />européen ESPRIT "supernode" ; le but de celui-ci étant la construction de multiprocesseurs reconfigurables à base de transputers.

Le travail présenté dans cette thèse, issu d'une problématique industrielle réelle, traite de la coordination entre la production et la distribution, dans un environnement multisite, multiproduit et multipériode. Après une présentation de la problématique industrielle, la première partie du mémoire s'intéresse essentiellement à l'organe de production et étudie des problèmes d'ordonnancement de machines parallèles. Dans cette partie, nous introduisons tout d'abord les problèmes d'ordonnancement, puis nous présentons un état de l'art concernant l'ordonnancement de machines parallèles. Enfin, nous proposons des méthodes de résolution pour des problèmes d'ordonnancement de machines parallèles non liées avec temps de changement dépendant de la séquence entre les produits. La deuxième partie du mémoire s'intéresse à une prise en compte plus globale de l'ensemble de la division industrielle et en particulier aux aspects multisites et aux problèmes liés à la coordination. Après une revue des travaux récents dans ce domaine, nous proposons une décomposition spatiale permettant de diviser le problème global en plusieurs problèmes plus petits et d'utiliser ainsi des méthodes plus performantes pour résoudre chacun d'entre eux. Enfin, le dernier chapitre détaille l'étude d'un problème réel et donne les performances et les limites du modèle proposé pour sa résolution.

Nous étudions quatre problèmes d'ordonnancement sur machines parallèles. Ces quatre problèmes diffèrent par le critère que l'on cherche à minimiser : la somme des dates de fin, la somme pondérée des dates de fin, le retard total ou le retard total pondéré. Les jobs à ordonnancer sout soumis à des dates de disponibilité. Nous avons proposé pour ces quatres problèmes plusieurs règles de dominance. Une étude des bornes<br />inférieures a également été réalisée. Enfin, nous avons proposé une méthode de résolution exacte utilisant les règles de dominance ainsi que les bornes inférieures.

Cette thèse est une contribution à l'étude du placement dynamique de processus sur des machines multiprocesseurs à mémoire distribuée. Le contexte de notre travail est celui de la simulation et de l'évaluation de l'exécution d'applications dont le nombre de processus et le moment de leur création dépendent de l'exécution en cours. Nous proposons un nouvel algorithme évolutif de placement dynamique de processus de type approximatif, avec des éléments de contrôle et d'information distribués. A chaque noeud X d'une machine parallèle est associé un sous-ensemble de processeurs avec lesquels il peut partager sa charge de manière équitable. Ce sous-ensemble est appelé la Solution de Placement (SP) du noeud. La Solution de Placement initiale d'un noeud X est composée du sous-ensemble des noeuds directement connectés au noeud X. La décision de placement d'un processus est faite au moment de sa création, il peut alors être placé sur le noeud sur lequel il a été créé ou bien sur un des noeuds de sa SP. Sous l'effet de certains opérateurs (declin, croissance, fusion, remplacement, rotation) la Solution de Placement d'un noeud évolue au cours de l'exécution de l'application ce qui permet une répartition et un équilibrage des charges des noeuds. Pour étudier le comportement de l'algorithme évolutif, nous avons utilisé le simulateur séquentiel SIMAD qui est un outil conçu pour évaluer les algorithmes d'allocation dynamique de charge sur des machines MIMD à mémoire distribuée. Le deuxième apport de cette thèse est la définition et l'intégration dans SIMAD d'un langage synthétique qui permet de décrire des applications parallèles avec des graphes de communication généraux. Le document se termine par la présentation d'une partie des résultats de l'ensemble des expériences que nous avons menées, dans le but d'évaluer les performances et le comportement de notre approche du placement dynamique de processus. Deux types de résultats sont présentés et analysés. Tout d'abord nous recherchons l'influence de certains paramètres (la taille maximale des SP, l'actualisation des SP, le nombre de processus par niveau de charge et l'opérateur de fusion) sur le comportement de l'algorithme évolutif. Ensuite, une étude comparative avec d'autres méthodes de placement dynamique permet de mettre en évidence les performances de notre approche.

Les travaux de cette thèse s’articulent autour des « problèmes d’ordonnancement multiagent avec une fonction objectif globale ». Ces modèles considèrent différents agents associés à des sous-ensembles de travaux disjoints, chacun d’eux vise à minimiser un objectif qui ne dépend que de ses propres travaux. Un critère global est aussi considéré, qui est appliqué à la totalité des travaux. La résolution de ces problèmes revient à trouver les meilleurs compromis entre les critères des agents et le critère global. Ces problèmes sont une classe particulière des problèmes d’ordonnancement « multi-agents » qui ont connu une grande expansion, reflétant leurs intérêts dans le domaine de l’ordonnancement. / This thesis addresses the multi-agent scheduling problems with a global objective function. We consider the problems featured by various agents, each of which is associated with a distinct subset of jobs. Each agent aims at minimizing a certain objective function, which only operates on its assigned jobs. A global criterion associated with a global agent is applied on the whole set of the jobs. Solving these problems involves finding the best compromises between the requirements of agents and that of the global agent. These problems belong to a particular class of multi-criteria scheduling problems. Such a class has drawn a significant interest to researchers in the area of scheduling and operational research.

Dans cette thèse, nous avons examiné différentes possibilités d'intégration des décisions d'ordonnancement avec des informations provenant de systèmes avancés des contrôles des procédés dans la fabrication de semi-conducteurs. Nous avons développé des idées d'intégration et défini des nouveaux problèmes d'ordonnancement originales : Problème d'ordonnancement avec des contraintes de temps (PTC) et problème d'ordonnancement avec l'état de santé des équipement (PEHF). PTC et PEHF ont des fonctions objectives multicritères.PTC est un problème d'ordonnancement des familles de jobs sur des machines parallèles non identiques en tenant compte des temps de setup et des contraintes de temps. Les machines non identiques signifient que toutes les machines ne peuvent pas traités (qualifiés) tous les types de familles d'emplois. Les contraintes de temps nommés aussi Thresholds sont inspirées des besoins de l'APC. Elle est liée à l'alimentation régulière des boucles de contrôle de l'APC. L'objectif est de minimiser la somme des dates de fin et les pertes de qualification des machines lorsqu'une famille de jobs n'est pas ordonnancée sur la machine donnée avant un seuil de temps donné.D'autre part, PEHF est une extension de PTC. Il consiste d'intégrer les indices de santé des équipements (EHF). EHF est un indicateur associé à l'équipement qui donne l'état de la. L'objectif est d'ordonnancer des tâches de familles de jobs différents sur les machines tout en minimisant la somme des temps d'achèvement, les pertes de qualification de la machine et d'optimiser un rendement attendu. Ce rendement est défini comme une fonction d'EDH et de la criticité de jobs considérés. / In this thesis, we discussed various possibilities of integrating scheduling decisions with information and constraints from Advanced Process Control (APC) systems in semiconductor Manufacturing. In this context, important questions were opened regarding the benefits of integrating scheduling and APC. An overview on processes, scheduling and Advanced Process Control in semiconductor manufacturing was done, where a description of semiconductor manufacturing processes is given. Two of the proposed problems that result from integrating bith systems were studied and analyzed, they are :Problem of Scheduling with Time Constraints (PTC) and Problem of Scheduling with Equipement health Factor (PEHF). PTC and PEHF have multicriteria objective functions.PTC aims at scheduling job in families on non-identical parallel machines with setup times and time constraints.Non-identical machines mean that not all miachines can (are qualified to) process all types of job families. Time constraints are inspired from APC needs, for which APC control loops must be regularly fed with information from metrology operations (inspection) within a time interval (threshold). The objective is to schedule job families on machines while minimizing the sum of completion times and the losses in machine qualifications.Moreover, PEHF was defined which is an extension of PTC where scheduling takes into account the equipement Health Factors (EHF). EHF is an indicator on the state of a machine. Scheduling is now done by considering a yield resulting from an assignment of a job to a machine and this yield is defined as a function of machine state and job state.

L'objectif de cette thèse est l'étude d'un environnement d'exécution pour machines parallèles sans mémoire commune. Elle comprend la définition d'un modèle de programme parallèle, basé sur l'échange de message offrant une forme restreinte de mémoire partagée. La communication est indirecte, via des portes; les processus utilisent les barrières pour la synchronisation. Les entités du système. processus, portes et barrières, sont créées dynamiquement, et placées sur un processeur quelconque du réseau de processeurs de façon explicite. Nous proposons une implantation de ce modèle comme la mise en oeuvre systématique d'une architecture client/serveur. Cette implantation a été efféctuée sur une machine Supemode. La base est un Micro Noyau Parallèle, où le composant principal est un mécanisme d'appel de procédure à distance minimal. / This thesis describes an execution environment for parallel machines without shared memory. A parallel programming model based on message passing, with a special shared memory. In this model, process communication occurs indirectly, via ports, and the processes use barriers for synchronization. All the entities of the system, such as processes, ports and barriers, are created dynamically and loaded on any processor of the network of processors. The implementation architecture of our model is a systematic realization of the client/server model. An implementation is proposed in a Supernode parallel machine as a parallel micro kernel. The principal parallel micro kernel component is a minimal remote procedure call mechanism.