Scheduling is concerned with the process of deciding how to commit resources between a variety of possible tasks with the aim of optimizing some performance criterion. Efficient scheduling is a vital tool in successful decision-making. To date, an enormous amount of research has been done on scheduling problems arising from various disciplines. Major attention has so far been dedicated to off-line (usually deterministic) scheduling problems. Off-line deterministic scheduling deals with perfect information. That is, all information with regard to a problem is known prior to any decision. However, this perfect information assumption violates the nature of many realistic issues with uncertainties, for example, a situation where the knowledge of problem instances is revealed over time, or a scenario in which processing tasks are temporarily disrupted or cancelled. To better formulate this sort of problem with high uncertainties, a new concept of on-line scheduling was introduced. On-line approaches have become increasingly important and are frequently encountered when only partial knowledge is available but instant or very fast solution methods are required and should nevertheless result in good outcomes. In on-line scheduling, a decision maker allocates resources between tasks as the information is gradually released. Obviously, given the same scheduling environment and problem instance, the result produced by an on-line scheduler cannot be better than that by the optimal off-line scheduler; but the on-line scheduling technique immunizes schedules from future disruptions and uncertainties. / This thesis extends the study of some scheduling problems derived from various industrial and computing situations to on-line scheduling environments, specifically the on-line-list and the on-line-time paradigms. The six topics studied are classified in two parts in this thesis. Part I consists of three machine scheduling problems taking into account various types of setup considerations. Part II includes the other three scheduling problems which are closely related to issues arising in the management of shipping containers and wind energy. / The effort is focused on constructing effective and efficient (on-line) decision-making strategies with the purpose of optimizing certain objective measures in those uncertain scheduling environments. The performance of the proposed heuristics as well as some existing on-line algorithms is evaluated and compared via competitive analysis. For some cases, empirical studies are also carried out to assess their average performance.

Scheduling is concerned with the process of deciding how to commit resources between a variety of possible tasks with the aim of optimizing some performance criterion. Efficient scheduling is a vital tool in successful decision-making. To date, an enormous amount of research has been done on scheduling problems arising from various disciplines. Major attention has so far been dedicated to off-line (usually deterministic) scheduling problems. Off-line deterministic scheduling deals with perfect information. That is, all information with regard to a problem is known prior to any decision. However, this perfect information assumption violates the nature of many realistic issues with uncertainties, for example, a situation where the knowledge of problem instances is revealed over time, or a scenario in which processing tasks are temporarily disrupted or cancelled. To better formulate this sort of problem with high uncertainties, a new concept of on-line scheduling was introduced. On-line approaches have become increasingly important and are frequently encountered when only partial knowledge is available but instant or very fast solution methods are required and should nevertheless result in good outcomes. In on-line scheduling, a decision maker allocates resources between tasks as the information is gradually released. Obviously, given the same scheduling environment and problem instance, the result produced by an on-line scheduler cannot be better than that by the optimal off-line scheduler; but the on-line scheduling technique immunizes schedules from future disruptions and uncertainties. / This thesis extends the study of some scheduling problems derived from various industrial and computing situations to on-line scheduling environments, specifically the on-line-list and the on-line-time paradigms. The six topics studied are classified in two parts in this thesis. Part I consists of three machine scheduling problems taking into account various types of setup considerations. Part II includes the other three scheduling problems which are closely related to issues arising in the management of shipping containers and wind energy. / The effort is focused on constructing effective and efficient (on-line) decision-making strategies with the purpose of optimizing certain objective measures in those uncertain scheduling environments. The performance of the proposed heuristics as well as some existing on-line algorithms is evaluated and compared via competitive analysis. For some cases, empirical studies are also carried out to assess their average performance.

Nous nous intéressons à la mise en oeuvre effective d'applications temps réel dans une approche d'ordonnancementhors-ligne de systèmes de tâches périodiques. L'ordonnancement hors-ligne consiste à rechercher avantl'exécution de l'application une séquence pire cas, c'est-à-dire une suite de blocs indiquant une date de débutet de fin d'exécution d'une instance de tâche. Mettre en oeuvre une séquence suppose de spécifier ce qui doit sepasser quand les durées d'exécution réelles sont inférieures aux durées pire cas prévues par la séquence. Notrepremière contribution consiste en la proposition de deux politiques de mise en oeuvre : une politique inflexiblequi respecte strictement les dates de début des blocs ; et une politique flexible qui permet de les avancer. Nousprouvons que ces politiques préservent la validité des séquences. Nous proposons ensuite un modèle de coûtspour l'évaluation et la comparaison de techniques respectant les politiques proposées. La seconde contributionconcerne la proposition de techniques de mise en oeuvre. Dans un premier temps, nous proposons sept techniquesde mise en oeuvre dans un contexte de tâches indépendantes et séquences sans préemption. Nous étendonsensuite l'utilisation de ces techniques aux séquences avec préemption, et aux tâches partageant des ressourcescritiques ou soumises à des contraintes de précédence. La troisième contribution concerne la mise en oeuvresous Posix. Nous présentons des outils de génération de code issus de l'ingénierie dirigée par les modèles. Nousproposons également un outil d'observation de séquences effectives. Enfin, une étude de cas présente l'utilisationpratique de notre approche. / We address the implementation of periodic task sets for off-line scheduling. Off-line scheduling approach consistsin computing a worst-case schedule before runtime. Implementing a schedule requires to specify what must happenwhen the actual execution times of tasks are lower than the planned execution times. The first contributionconsist of the formalization of implementation policies. These policies consider the date by which a task maystart execution, which may or not occur before the planned start time. The inflexible policy does not allowa task to run before its planned start time, the flexible policy does. Since many implementations can complywith these two policies, we also propose a cost model which enables to perform some comparisons betweenthese implementations. The second contribution is the proposition and the presentation of a set of algorithmswhich implement the pre-computed schedules. We first deal with independent task sets in a non preemptivecontext. These algorithms are then adapted to be used in the context of preemptive scheduling, with sharedcritical ressources and precedence constraints. Using the model driven engeneering, we next provide a Posixcode generation tool. We also present a schedule observation tool. Finally, our work has been tested through apratical case study.

This study deals with chocolate production line scheduling. The particular production line allows producing multiple items at the same time. Another distinguishing property affecting the planning methodology is that an item can have different production capacities when produced in different product combinations which are called production patterns in this study. Planning is done on a 12 weeks rolling horizon. There are 21 products and 103 production patterns covering all the production possibilities. The subject of the study is to construct an algorithm that gives 12 weeks&rsquo / production values of each product and to construct the shift based scheduling of the first week of the planning horizon. The first part is Master Production Scheduling (MPS) and the objective is minimizing the shortage and overage costs. A mathematical modeling approach is used to solve the MPS problem. The second part is the scheduling part which aims to arrange the production patterns obtained from the MPS module within the shifts for the first week of the planning horizon considering the setup times. The MPS module is a large integer programming model. The challenge is finding a reasonable lower bound whenever possible. If it is not possible, finding a reasonable upper bound and seeking solutions better than that is the main approach. The scheduling part, after solving MPS, becomes a TSP and the setup times are sequence independent. In this part, the challenge is solving TSP with an appropriate objective function.

ABSTRACT Broadcasting data delivery is rapidly becoming the good choice for disseminating information to a massive user population in many new application areas where the client-to-server communication is limited. There are two different ways of data dissemination. One is called push-based that the data items are broadcasted periodically in the channels, another one is called pull-based that the client requests a piece of data on the uplink channel and the server responds by sending this piece of data to the client. In push-based, most of the previous researches assume that each mobile client needs only one data item. However, in many situations, a mobile client might need more than one data item. In pull-based, the data items were broadcasted dynamically. Most of the previous researches assume that the data items which requested by the clients are of the same size. However, the data items may of different sizes in reality. In this thesis, we propose Improved QDS Expansion Method (Improved-QEM) and Heuristic On-line Algorithm to overcome the above two weaknesses, respectively. The issue of scheduling the broadcast data for the situation that each client may access multiple data items can not be simply considered as multiple subissues. There have been two methods was proposed, Query Expansion Method (QEM) and Modified Query Expansion Methods (Modified-QEM). These two methods are heuristic-based algorithm and do not provide the optimal solution. To improve the performance, our Improved-QEM is an efficient scheduling for query-set-based broadcasting, which is integrated with Query Expansion Method (QEM) and mining association rules technique. The mining association rules can globally find the data item sets (large itemsets) which are requested by clients, frequently. From our simulation results, we show that, as compared to the local optimal approach in the previous methods, our Improved-QEM can construct the schedule with the smaller TQD than that constructed by QEM and Modified-QEM, where TQD is denotes Total Query Distance and is proportional to the average access time. The on-line (push-based) algorithms are easy to adapt to time varying demands for the data items, which uses some decision-making mechanism to determine which data item is to be broadcasted next. Hence, when the number of data items is huge, it is important to schedule broadcasting program such that, it can provide the small overall mean access time. Therefore, Vaidya and Hameed have proposed two on-line algorithms, On-line Algorithm and On-line with Bucketing Algorithm. The main disadvantage of On-line Algorithm is the heavy run-time overhead and the main disadvantage of On-line Algorithm with Bucketing is the poor performance of the overall mean access time. Therefore, we propose the heuristic on-line algorithm to solve these two problems. From our simulation results, we show that our heuristic algorithm provides the performance that closes to the overall mean access time and has with low run-time overhead.

Dans cette thèse nous étudions le problème d'ordonnancement temps réel multiprocesseur préemptif avec prise en compte du coût exact du système d'exploitation. Ce coût est formé de deux parties : une partie facile à déterminer, correspondant au coût de l'ordonnanceur et une partie difficile à déterminer, correspondant au coût de la préemption. Cette difficulté est due au fait qu'une préemption peut en engendrer une autre, pouvant ainsi créer un phénomène d'avalanche. Dans un premier temps, nous avons étudié l'ordonnancement hors ligne multiprocesseur de tâches indépendantes avec prise en compte du coût exact de la préemption et proposé une analyse d'ordonnançabilité fondée sur une heuristique d'ordonnancement multiprocesseur. Cette heuristique utilise la stratégie d'ordonnancement multiprocesseur par partitionnement. Pour prendre en compte le coût exact de la préemption sur chaque processeur nous avons utilisé la condition d'ordonnançabilité proposée par Meumeu et Sorel. Cette condition d'ordonnançabilité pour des tâches à priorités fixes, est basée sur une opération binaire d'ordonnancement qui permet de compter le nombre exact de préemption et d'ajouter leur coût dans l'analyse d'ordonnançabilité des tâches. L'heuristique proposée permet de maximiser le facteur d'utilisation restant afin de répartir équitablement les tâches sur les processeurs et de réduire leur temps de réponse. Elle produit une table d'ordonnancement hors ligne. Dans un second temps, nous avons étudié l'ordonnancement hors ligne multiprocesseur de tâches dépendantes avec prise en compte du coût exact de la préemption. Puisque la condition d'ordonnançabilité utilisée pour ordonnancer les tâches indépendantes ne s'applique qu'à des tâches à priorités fixes, elle ne permet pas de gérer les inversions de priorités que peuvent entraîner les tâches dépendantes. Nous avons donc proposé une nouvelle condition d'ordonnançabilité pour des tâches à priorités dynamiques. Elle prend en compte le coût exact de la préemption et les dépendances sans aucune perte de données. Ensuite en utilisant toujours la stratégie d'ordonnancement par partitionnement, nous avons proposé pour des tâches dépendantes une heuristique d'ordonnancement multiprocesseur qui réutilise cette nouvelle condition d'ordonnançabilité au niveau de chaque processeur. Cette heuristique d'ordonnancement prend en compte les coûts de communication inter-processeurs. Elle permet aussi de minimiser sur chaque processeur le makespan (temps total d'exécution) des tâches. Cette heuristique produit pour chaque processeur une table d'ordonnancement hors ligne contenant les dates de début et de fin de chaque tâches et de chaque commmunication inter-processeur. En supposant que nous avons une architecture multiprocesseur de type dirigée par le temps (Time-Triggered) pour laquelle tous les processeurs ont une référence de temps unique, nous avons proposé pour chacun des processeurs un ordonnanceur en ligne qui utilise la table d'ordonnancement produite lors de l'ordonnancement hors ligne. Cet ordonnanceur en ligne a l'avantage d'avoir un coût constant qui de plus est facile à déterminer de manière exacte. En effet il correspond uniquement au temps de lecture dans la table d'ordonnancement pour obtenir la tâche sélectionnée lors de l'analyse d'ordonnançabilité hors ligne, alors que dans les ordonnanceurs classiques en ligne ce coût correspond à mettre à jour la liste des tâches qui sont dans l'état prêt à l'exécution puis à sélectionner une tâche selon un algorithme, par exemple RM, DM, EDF, etc. Il varie donc avec le nombre de tâches prêtes à s'exécuter qui change d'une invocation à l'autre de l'ordonnanceur. C'est ce coût qui est utilisé dans les analyses d'ordonnançabilités évoquées ci-dessus. Un autre avantage est qu'il n'est pas nécessaire de synchroniser l'accès aux mémoires de données partagées par plusieurs tâches, car cette synchronisation a été déjà effectuée lors de l'analyse d'ordonnançabilité hors ligne. / In this thesis we studied the problem of multiprocessor preemptive real-time scheduling taking into account the exact cost of the operating system (OS). This cost is composed of two parts: a part easy to determine, corresponding to the scheduler cost and another part difficult to determine, corresponding to the preemption cost. This difficulty is due to the fact that a preemption can involve another one, being able to so create an avalanche phenomenon. First, we studied the off-line multiprocessor real-time scheduling of independent tasks taking into account the exact preemption cost. We proposed a schedulability analysis based on a multiprocessor scheduling heuristic. This heuristic uses the partitioned multiprocessor scheduling approach. In order to take into account the exact preemption cost on every processor we use the schedulability condition proposed by Meumeu and Sorel. This schedulability condition for fixed priorities tasks, is based on a binary scheduling operation which counts the exact number of preemptions and add their cost in the schedulability analysis. The proposed heuristic maximizes the remaining utilization factor to fairly distribute the tasks on processors and to reduce their response time. It produces an off-line scheduling table. Secondly, we studied the off-line multiprocessor real-time scheduling of dependent tasks taking into account the exact preemption cost. Because the schedulability condition used for scheduling independent tasks can be applied only to fixed priorities tasks, it does not allow to manage priorities inversions that are involved by dependent tasks. We proposed a new schedulability condition for dependent tasks which enables fixed and dynamic priorities. This schedulability condition takes into account the exact preemption cost and dependences between tasks without any loss of data. Always with the partitioned scheduling approach, we proposed for dependent tasks a multiprocessor scheduling heuristic which reuses, on every processor, the schedulability condition proposed previously. In addition, this scheduling heuristic takes into account the interprocessors communication costs. It also minimizes on every processor the makespan (total execution time of the tasks on all the processors). This heuristic produces for every processor an off-line scheduling table. Supposing that we have a time-triggered multiprocessor architecture such that all the processors have a unique time reference, we proposed for every processor an on-line scheduler which uses the scheduling table produced during the off-line schedulability analysis. This on-line scheduler has the advantage to have a constant cost that is easy to determine exactly.Indeed, this cost corresponds only to the time necessary to read in the scheduling table the task selected for execution. In the on-line classical scheduler, this cost corresponds to the time necessary to update the list of ready tasks in order to select a task, according to a given scheduling algorithm, for example RM, DM, EDF, etc. In this case, the cost for selecting a task varies with the number of ready tasks which changes from an invocation of the scheduler to another one. Another advantage of the proposed on-line scheduler is that it is not necessary to synchronize the access to the data shared by several tasks, because this synchronization was already done during the off-line schedulability analysis.

Wine companies face two important challenges in their supply chain: the international shipping temperatures and their effect on the perceived quality of the wine and the optimization of the bottling schedule. The wine maker takes special care in producing the best quality product, which is then shipped to the importer/distributor or consumer, generally in non-refrigerated containers at the mercy of the prevailing environmental conditions. The contributions of this work is that it is the first to measure, for a significant period of time, the temperatures along the international wine supply chain and to link them to the specific supply chain processes. This is also the first work that analyzes the effect of shipping temperature on the perceived quality of the product by those who make the purchase decision for importers, restaurants and supermarkets. Results indicate that the wine is very likely to have been exposed to extreme temperatures during shipping. For white wines, tasters are able to detect differences in wines which have been exposed to shipping temperatures and show a preference towards them. For red wines, they are unable to detect differences. Our contribution to the second challenge was the development of a model that produces solutions for the wine bottling lot sizing and scheduling problem with sequence dependent setup times, in an adequate time-frame, which can be implemented by large wineries. We have developed a model and algorithm that produces fast, good and robust solutions for the winery lot sizing and scheduling problem with sequence dependent setup times. We implemented an effective decomposition algorithm that uses the structure of the problem, that can be applied to other families of sequence dependent scheduling and lot sizing problem. Results indicate that the model achieves reductions of 30\% in the total plan costs.

La planificación de la producción en plantas de proceso discontinuo es uno de los problemas más complejos e importantes para una amplia variedad de procesos industriales. A pesar de esta importancia la planificación de la producción es habitualmente un proceso manual que puede conducir a un exceso de inventario, una utilización ineficiente del capital y aumento en costes de producción.Este problema ha sido el sujeto de un importante esfuerzo investigador en los últimos años, especialmente desde principios de los 80 hasta la actualidad, aunque la industria se ha mostrado interesada en el problema desde los años 40. Durante este tiempo se ha realizado mucha investigación al respecto, pero la naturaleza compleja de problema hace que todavía no exista una solución aceptada ampliamente en la industria.Esta tesis describe un entorno genérico para la planificación de la producción en plantas de proceso discontinuo. Se han desarrollado diferentes componentes: un modelo de datos, un modelo de temporización, estrategias de asignación y secuenciación y diferentes alternativas de optimización.Uno de los aspectos más importantes del entorno presentado es su modularidad. El hecho de dividir el problema de planificación de la producción en diferentes módulos que comparten un modelo de datos común facilita la reutilización y la adaptación a escenarios industriales de las diferentes técnicas desarrolladas escogiendo la mejor alternativa para cada uno de ellos.El modelo de información orientado a objetos que se presenta en esta tesis permite la organización sistemática de la información de planta, permitiendo una representación detallada de las restricciones presentes en la industria.Por otra parte, el modelo de temporización de operaciones (EON) desarrollado en la presente tesis es la capacidad de representar restricciones temporales complejas presentes en la industria utilizando componentes sencillos. Se ha desarrollado una metodología para generar modelos EON a partir del modelo de información utilizado incluyendo restricciones de depósitos y restricciones temporales entre operaciones. Adicionalmente, un método iterativo permite tener en cuenta otros recursos limitantes dependientes de calendario, como mano de obra, electricidad, etc.En relación a las decisiones de nivel superior, se han desarrollado también reglas de balance de materiales, asignación y secuenciación que permiten obtener de una forma rápida y sencilla planes factibles a partir de un conjunto de demandas. Estas reglas se pueden aplicar tanto a planes de producción vacíos en situaciones de puesta en marcha de la planta, como a planes parcialmente llenos con la información de lotes que se están ejecutando en planta, lo que permite la replanificación en linea en caso de ser necesario.También se han aplicado diferentes técnicas de optimización a fin de mejorar planes de producción. Se han probado tanto métodos heurísticos como modelización matemática.En lo referente a los métodos heurísticos, se ha desarrollado un nuevo método de optimización (MSES) que mejora algunos aspectos referentes al algoritmo estándar de recocido simulado. Los algoritmos genéticos han sido también objeto de estudio, incorporando un algoritmo que transforma los individuos infactibles en factibles. Todos estos métodos han sido adaptados al entorno desarrollado permitiendo cambios de secuencia y asignación.En lo que respecta a la modelización matemática, se ha desarrollado un nuevo modelo MILP basado en una extensión del EON introduciendo variables de decisión de secuencia y asignación así como restricciones asociadas a almacenamientos intermedios.El entorno desarrollado en esta tesis ha sido aplicado a diferentes entornos industriales, proporcionando una validación de las tecnologías y modelos desarrollados. En todos los casos estudiados se han podido obtener planes de producción que cumplen con las restricciones presentes en planta, lo que permite establecer la validez de las metodologías desarrolladas para la planificación de la producción en plantas químicas de proceso discontinuo. / The scheduling of batch processes is one of the most complex and important problems faced by a wide variety of processing industries. In spite of this importance, scheduling is often a manual procedure, which leads to operation characterized by high inventories, inefficient capital utilization and increased operation costs. There are also reported complains about the lack of powerful, easy-to-use, PC based tools able to solve detailed operational problems, as well as perform high level analysis across the supply chain.This problem has been the focus of an important amount of research work in the recent years, especially from the early 1980's to nowadays, although the industry has been interested in effective ways of solving the scheduling problem since the early 1940's. An extensive work has been done but the complex nature of the scheduling problem results on the lack of a unique solution widely accepted in the industry.This thesis describes a global generic framework for planning and scheduling of batch chemical plants. Different components have been studied: a data model, a timing model, heuristic sequencing and assignment strategies and optimization procedures.One of the strongest points of the framework presented is its modularity. The fact of having the different components of planning and scheduling as separate modules sharing a common data model allows an easy use and adaptation of different techniques that can help solving the scheduling and planning problem in specific cases. This modular approach has been useful when applying the techniques presented to industrial scenarios. Adaptation to specific scenarios choosing the best alternative for each one is not only possible but also easy.The key point for achieving this is to share the common data and timing model (the EON model). The extensible object oriented data model presented in this thesis allows an organized and systematic information management dealing with the detailed representation of batch processes in the chemical industry. The main strength of the EON model is the capability of representation of complex time constraints between operations in the same schedule using simple components. EON model is presented and developed in detail. A methodology for the representation of storage constraints as time constraints as EON constraints is also presented. An iterative procedure allows also to take into account of limited resources as manpower, electricity, etc.Dispatching-like rules have been developed for the calculation of the material balances, the unit assignment and the batch sequencing. The strength of this approach is based in the easy implementation and adaptation to a batch oriented framework. These rules can be applied to empty schedules or to schedules that already contain frozen batches, which represents the actual situation in the plant. This last aspect allows the use of this kind of rules when performing on-line scheduling.Different optimization techniques have been used in this thesis to solve the scheduling approach presented. Stochastic and mathematical methods have been used and tested.Regarding to the stochastic methods, a new optimization algorithm (MSES) has been introduced that improves the performance of the SA standard algorithm. A modified GA algorithm has also been proposed that transforms the infeasible sequences commonly generated into feasible ones. All the stochastic methods used were adapted to batch processing structures involving batch sequencing and rule driven unit assignment.Regarding to the mathematical approach, the mathematical formulation presented in the EON timing model has been extended by introducing sequence and assignment variables as well as storage constraints.The framework developed in this thesis has been successfully applied to different industrial scenarios that are shown. The proposed solutions have been able to represent all the complexity of the test cases studied providing a powerful tool for planning and scheduling of the different plants.

Made available in DSpace on 2016-06-02T19:06:23Z (GMT). No. of bitstreams: 1 DissJCD.pdf: 3954079 bytes, checksum: 63ef4f081a962ca21478327fb623632d (MD5) Previous issue date: 2004-08-25 / Flexible manufacturing systems (FMS) have been designed to meet market requirements that demand products that are quality and ready to deliver. In order to meet the market requirements, the methodologies used in the FMS scheduling must consider a highly dynamic environment, where it is often necessary to meet or to react to uncertain demands and to get better use of its resources. An on-line scheduling procedure based on fuzzy logic is proposed in this work, whose main characteristic is shop floor tasks scheduling using fuzzy rules building with the support of an expert to meet several measures of performance. A simulation study was carried out with the objective to verify the applicability of the proposed approach, using a simulation tool integrated with the on-line scheduling procedure based on fuzzy logic. / Os sistemas flexíveis de manufatura (FMS) têm sido projetados para atender as necessidades do mercado, que demandam por produtos que apresentam qualidade e prazos de entrega pequenos. Para atender as necessidades do mercado, as metodologias usadas na programação de operações de FMS devem considerar um ambiente altamente dinâmico, onde é frequentemente necessário atender ou reagir a demandas incertas e fazer o melhor uso de seus recursos. Um procedimento de programação on-line baseado em lógica fuzzy é proposto neste trabalho, cuja característica principal é programar as tarefas do chão de fábrica utilizando regras fuzzy construídas com o apoio de um especialista para atender a várias medidas de desempenho simultaneamente. Um estudo por meio de simulação foi realizado com o objetivo de verificar a aplicabilidade da abordagem proposta, utilizando uma ferramenta de simulação integrada ao procedimento de programação on-line baseado em lógica fuzzy.

Les réseaux-sur-puces (NoCs) utilisés dans les architectures multiprocesseurs-sur-puces posent des défis importants aux approches d'ordonnancement temps réel en ligne (dynamique) et hors-ligne (statique). Un NoC contient un grand nombre de points de contention potentiels, a une capacité de bufferisation limitée et le contrôle réseau fonctionne à l'échelle de petits paquets de données. Par conséquent, l'allocation efficace de ressources nécessite l'utilisation des algorithmes da faible complexité sur des modèles de matériel avec un niveau de détail sans précédent dans l'ordonnancement temps réel. Nous considérons dans cette thèse une approche d'ordonnancement statique sur des architectures massivement parallèles (Massively parallel processor arrays ou MPPAs) caractérisées par un grand nombre (quelques centaines) de c¿urs de calculs. Nous identifions les mécanismes matériels facilitant l'analyse temporelle et l'allocation efficace de ressources dans les MPPAs existants. Nous déterminons que le NoC devrait permettre l'ordonnancement hors-ligne de communications, d'une manière synchronisée avec l'ordonnancement de calculs sur les processeurs. Au niveau logiciel, nous proposons une nouvelle méthode d'allocation et d'ordonnancement capable de synthétiser des ordonnancements globaux de calculs et de communications couvrants toutes les ressources d'exécution, de communication et de la mémoire d'un MPPA. Afin de permettre une utilisation efficace de ressources du matériel, notre méthode prend en compte les spécificités architecturales d'un MPPA et implémente des techniques d'ordonnancement avancées comme la préemption pré-calculée de transmissions de données. Nous avons évalué n / On-chip networks (NoCs) used in multiprocessor systems-on-chips (MPSoCs) pose significant challenges to both on-line (dynamic) and off-line (static) real-time scheduling approaches. They have large numbers of potential contention points, have limited internal buffering capabilities, and network control operates at the scale of small data packets. Therefore, efficient resource allocation requires scalable algorithms working on hardware models with a level of detail that is unprecedented in real-time scheduling. We consider in this thesis a static scheduling approach, and we target massively parallel processor arrays (MPPAs), which are MPSoCs with large numbers (hundreds) of processing cores. We first identify and compare the hardware mechanisms supporting precise timing analysis and efficient resource allocation in existing MPPA platforms. We determine that the NoC should ideally provide the means of enforcing a global communications schedule that is computed off-line (before execution) and which is synchronized with the scheduling of computations on processors. On the software side, we propose a novel allocation and scheduling method capable of synthesizing such global computation and communication schedules covering all the execution, communication, and memory resources in an MPPA. To allow an efficient use of the hardware resources, our method takes into account the specificities of MPPA hardware and implements advanced scheduling techniques such as pre-computed preemption of data transmissions. We evaluate our technique by mapping two signal processing applications, for which we obtain good latency, throughput, and resource use figures.