La conception de systèmes temps-réel embarqués se développe de plus en plus avec l’intégration croissante de fonctionnalités critiques pour les applications de surveillance, notamment dans le domaine biomédical, environnemental, domotique, etc. Le développement de ces systèmes doit relever divers défis en termes de minimisation de la consommation énergétique. Gérer de tels dispositifs embarqués, entièrement autonomes, nécessite cependant de résoudre différents problèmes liés à la quantité d’énergie disponible dans la batterie, à l’ordonnancement temps-réel des tâches qui doivent être exécutées avant leurs échéances, aux scénarios de reconfiguration, particulièrement dans le cas d’ajout de tâches, et à la contrainte de communication pour pouvoir assurer l’échange des messages entre les processeurs, de façon à assurer une autonomie durable jusqu’à la prochaine recharge et ce, tout en maintenant un niveau de qualité de service acceptable du système de traitement. Pour traiter cette problématique, nous proposons dans ces travaux une stratégie de placement et d’ordonnancement de tâches permettant d’exécuter des applications temps-réel sur une architecture contenant des cœurs hétérogènes. Dans cette thèse, nous avons choisi d’aborder cette problématique de façon incrémentale pour traiter progressivement les problèmes liés aux contraintes temps-réel, énergétique et de communications. Tout d’abord, nous nous intéressons particulièrement à l’ordonnancement des tâches sur une architecture mono-cœur. Nous proposons une stratégie d’ordonnancement basée sur le regroupement des tâches dans des packs pour pouvoir calculer facilement les nouveaux paramètres des tâches afin de réobtenir la faisabilité du système. Puis, nous l’avons étendu pour traiter le cas de l’ordonnancement sur une architecture multi-cœurs homogènes. Finalement, une extension de ce dernier sera réalisée afin d’arriver à l’objectif principal qui est l’ordonnancement des tâches pour les architectures hétérogènes. L’idée est de prendre progressivement en compte des contraintes d’exécution de plus en plus complexes. Nous formalisons tous les problèmes en utilisant la formulation ILP afin de pouvoir produire des résultats optimaux. L’idée est de pouvoir situer nos solutions proposées par rapport aux solutions optimales produites par un solveur et par rapport aux autres algorithmes de l’état de l’art. Par ailleurs, la validation par simulation des stratégies proposées montre qu’elles engendrent un gain appréciable vis-à-vis des critères considérés importants dans les systèmes embarqués, notamment le coût de la communication entre cœurs et le taux de rejet des tâches. / The design of embedded real-time systems is developing more and more with the increasing integration of critical functionalities for monitoring applications, particularly in the biomedical, environmental, home automation, etc. The developement of these systems faces various challenges particularly in terms of minimizing energy consumption. Managing such autonomous embedded devices, requires solving various problems related to the amount of energy available in the battery and the real-time scheduling of tasks that must be executed before their deadlines, to the reconfiguration scenarios, especially in the case of adding tasks, and to the communication constraint to be able to ensure messages exchange between cores, so as to ensure a lasting autonomy until the next recharge, while maintaining an acceptable level of quality of services for the processing system. To address this problem, we propose in this work a new strategy of placement and scheduling of tasks to execute real-time applications on an architecture containing heterogeneous cores. In this thesis, we have chosen to tackle this problem in an incremental manner in order to deal progressively with problems related to real-time, energy and communication constraints. First of all, we are particularly interested in the scheduling of tasks for single-core architecture. We propose a new scheduling strategy based on grouping tasks in packs to calculate the new task parameters in order to re-obtain the system feasibility. Then we have extended it to address the scheduling tasks on an homogeneous multi-core architecture. Finally, an extension of the latter will be achieved in order to realize the main objective, which is the scheduling of tasks for the heterogeneous architectures. The idea is to gradually take into account the constraints that are more and more complex. We formalize the proposed strategy as an optimization problem by using integer linear programming (ILP) and we compare the proposed solutions with the optimal results provided by the CPLEX solver. Inaddition, the validation by simulation of the proposed strategies shows that they generate a respectable gain compared with the criteria considered important in embedded systems, in particular the cost of communication between cores and the rate of new tasks rejection.

En raison de l'augmentation des coûts d'énergie et des préoccupations environnementales telles que les empreintes de carbone élevées, les systèmes de la production d'électricité centralisée se restructurent pour profiter des avantages de la production distribuée afin de répondre aux exigences énergétiques toujours croissantes. Les microgrids sont considérés comme une solution possible pour déployer une génération distribuée qui inclut des ressources énergétiques distribuées DERs (Distributed Energy Resources)(e.g, solaire, éolienne, batterie, etc). Dans cette thèse, nous traitons les défis de la gestion d'énergie dans un microgrid industriel où les charges énergétique sont constituées de processus industriels. Notre plan consiste à diviser la gestion de l'énergie du microgrid en deux parties: la production et la demande d’énergie.Du côté de la production d'énergie, les défis incluent la modélisation des générations de puissance et le lissage des fluctuations des DER. Pour modéliser les générations de puissance, nous proposons un modèle basé sur les concepts de service courbé de Network Calculus. En utilisant cet outil mathématique, nous déterminons une quantité minimale de puissance que les DERs peuvent générer; leur agrégation nous donnera une production d'énergie totale dans le microgrid. Après cela, s'il existe un déséquilibre entre la production et la demande d'énergie, nous proposons des stratégies différentes pour minimiser les coûts d'approvisionnement énergétique. Sur la base des données réelles de la consommation d'énergie d'un site industriel situé en France, des économies significatives peuvent être réalisées en adoptant ces stratégies. Dans cette thèse, nous étudions également comment atténuer les effets des fluctuations de puissance des DERs en conjonction avec des systèmes de stockage d'énergie. Pour cela, nous proposons un algorithme de lissage gaussien et nous le comparons avec des algorithmes de lissage trouvés dans l'état de l'art. Nous avons trouvé que l'algorithme proposé utilise de batterie de moins de taille à des fins de lissage par rapport à d'autres algorithmes. À cette fin, nous sommes également intéressés à étudier les effets de la gamme admissible des fluctuations sur les tailles de la batterie.Du côté de la demande, l'objectif est de réduire les coûts de l'énergie grâce aux approches de gestion de la demande DSM (Demand Side Management) telles que Demand Response (DR) et Energy Efficiency. Comme les processus industriels consomment énormément, une petite réduction de la consommation d'énergie en utilisant les approches DSM pourrait se traduire par des économies cruciales. Cette thèse se concentre sur l'approche DR qui peut profiter des prix variables de l'électricité dans le temps pour déplacer les demandes énergétiques des heures de pointe aux heures creuses. Pour atteindre cet objectif, nous comptons sur un modèle basé sur la théorie de file d'attente pour caractériser les comportements temporels (arrivée et départ des tâches) d'un système de fabrication. Après avoir défini les processus d'arrivée et de départ de tâches, une fonction d'utilisation efficace est utilisée pour prédire le comportement de la machine dans un domaine temporel et qui peut afficher son statut (allumé/éteint) à tout moment. En prenant le statut de chaque machine dans une ligne de production comme une entrée, nous proposons également un algorithme de planification DR qui adapte la consommation d'énergie d'une ligne de production aux deux contraintes de puissance disponibles et de taux de production. L'algorithme est codé à l'aide d’une machine d’état fini déterministe (Deterministic Finite State Machine) dans laquelle les transitions d'état se produisent en insérant une tâche à l'entrée du tapis roulant (on peut aussi avoir des transitions sans insertion de taches). Nous définissons des conditions pour l'existence d’un planificateur réalisable et aussi des conditions pour accepter positivement des demandes DRs / Due to increased energy costs and environmental concerns such as elevated carbon footprints, centralized power generation systems are restructuring themselves to reap benefits of distributed generation in order to meet the ever growing energy demands. Microgrids are considered as a possible solution to deploy distributed generation which includes Distributed Energy Resources (DERs) (e.g., solar, wind, battery, etc). In this thesis, we are interested in addressing energy management challenges in an industrial microgrid where energy loads consist of industrial processes. Our plan of attack is to divide the microgrid energy management into supply and demand sides.In supply side, the challenges include modeling of power generations and smoothing out fluctuations of the DERs. To model power generations, we propose amodel based on service curve concepts of Network Calculus (NC). Using this mathematical tool, we determine a minimum amount of power the DERs can generate and aggregating them will give us total power production in the microgrid. After that, if there is an imbalance between energy supply and demand, we put forward different strategies to minimize energy procurement costs. Based on real power consumption data of an industrial site located in France, significant cost savings can be made by adopting the strategies. In this thesis, we also study how to mitigate the effects of power fluctuations of DERs in conjunction with Energy Storage Systems (ESSs). For this purpose, we propose a Gaussian-based smoothing algorithm and compare it with state-of-the-art smoothing algorithms. We found out that the proposed algorithm uses less battery size for smoothing purposes when compared to other algorithms. To this end, we are also interested in investigating effects of allowable range of fluctuations on battery sizes.In demand side, the aim is to reduce energy costs through Demand Side Management (DSM) approaches such as Demand Response (DR) and Energy Efficiency (EE). As industrial processes are power-hungry consumers, a small power consumption reduction using the DSM approaches could translate into crucial savings. This thesis focuses on DR approach that can leverage time varying electricity prices to move energy demands from peak to off-peak hours. To attain this goal, we rely on a queuing theory-based model to characterize temporal behaviors (arrival and departure of jobs) of a manufacturing system. After defining job arrival and departure processes, an effective utilization function is used to predict workstation’s (or machine’s) behavior in temporal domain that can show its status (working or idle) at any time. Taking the status of every machine in a production line as an input, we also propose a DR scheduling algorithm that adapts power consumption of a production line to available power and production rate constraints. The algorithm is coded using Deterministic Finite State Machine (DFSM) in which state transitions happen by inserting a job (or not inserting) at conveyor input. We provide conditions for existence of feasible schedules and conditions to accept DR requests positively.To verify analytical computations on the queuing part, we have enhanced Objective Modular Network Testbed in C++ (OMNET++) discrete event simulator for fitting it to our needs. We modified various libraries in OMNET++ to add machine and conveyor modules. In this thesis, we also setup a testbed to experiment with a smart DR protocol called Open Automated Demand Response (OpenADR) that enables energy providers (e.g., utility grid) to ask consumers to reduce their power consumption for a given time. The objective is to explore how to implement our DR scheduling algorithm on top of OpenADR

Cette thèse se focalise sur le développement des algorithmes d’ordonnancement sous contrainte (m, k)-firm, ainsi que leurs applications pour la gestion de la qualité de service (QdS) dans les réseaux et systèmes temps réel distribués. L’objectif recherché est la garantie déterministe de la QdS tout en maintenant un fort taux d’utilisation des ressources. Les contributions sont (1) l’établissement d’une condition suffisante d’ordonnançabilité d'un ensemble de tâches sous l’algorithme « distance based priority »; (2) la définition de R-(m, k)-firm, un nouveau modèle qui relâche la contrainte (m, k)-firm et qui permet de modéliser de façon plus juste des exigences du temps réel souple; (3) le développement d’un algorithme efficace de dimensionnement de ressources sous contrainte (m, k)-firm relâchée; (4) la proposition de « Double Leaks Bucket » pour la gestion active de files d'attente permettant de maintenir une QdS en cas de surcharge des réseaux / This work focuses on the scheduling algorithms under (m,k)-firm constraint, as well as the applications for QoS (quality of service) management in the networks and distributed real-time system. The research aim is to achieve the deterministic guarantee of QoS with high resource utilization. The contributions in this thesis include (1) proposing a sufficient condition for determining the schedulability of a real-time task set under Distance Base Priority scheduling algorithm; (2) defining a novel real-time constraint which relaxes the (m,k)-firm constraint and provides a more suitable modelling of soft real-time; (3) developing an effective resource provisioning algorithm under this relaxed (m,k)-firm constraint; (4) proposing an active queue management mechanism, called Double Leaks Bucket, which can guarantee the QoS with dynamic dropping of the packets during the networks overload period

The ever-increasing functional and nonfunctional requirements in real-time safety-critical embedded systems call for new design flows that solve the specification, validation, and synthesis problems. Ensuring key properties, such as functional determinism and temporal predictability, has been the main objective of many embedded system design models. Dataflow models of computation (such as KPN, SDF, CSDF, etc.) are widely used to model stream-based embedded systems due to their inherent functional determinism. Since the introduction of the (C)SDF model, a considerable effort has been made to solve the static-periodic scheduling problem. Ensuring boundedness and liveness is the essence of the proposed algorithms in addition to optimizing some nonfunctional performance metrics (e.g. buffer minimization, throughput maximization, etc.). However, nowadays real-time embedded systems are so complex that real-time operating systems are used to manage hardware resources and host real-time tasks. Most of real-time operating systems rely on priority-driven scheduling algorithms (e.g. RM, EDF, etc.) instead of static schedules which are inflexible and difficult to maintain. This thesis addresses the real-time scheduling problem of dataflow graph specifications; i.e. transformation of the dataflow specification to a set of independent real-time tasks w.r.t. a given priority-driven scheduling policy such that the following properties are satisfied: (1) channels are bounded and overflow/underflow-free; (2) the task set is schedulable on a given uniprocessor (or multiprocessor) architecture. This problem requires the synthesis of scheduling parameters (e.g. periods, priorities, processor allocation, etc.) and channel capacities. Furthermore, the thesis considers two performance optimization problems: buffer minimization and throughput maximization.

Nos últimos anos os sistemas embarcados tem-se tornado notório nos mercados de eletroeletrônicos de consumo, automação industrial e comercial e em veículos em geral. Grande parte destas aplicações possui restrições temporais, sendo assim caracterizadas como sistemas de tempo real embarcado. Atualmente, a computação distribuída tem alcançado este tipo de sistema e por razão principal em custos desses sistemas, alguns barramentos ou redes de comunicação vêm sendo empregados como plataforma de conexão entre módulos eletrônicos. Um exemplo de aplicação de sistemas embarcados distribuídos e de tempo real é a eletrônica embarcada em veículos automotores, onde se encontram várias unidades de controle eletrônico espalhadas interior desses veículos com diferentes funções e se comunicando via rede de comunicação. Algumas pesquisas importantes nesta área já apresentaram diferentes abordagens em sistemas distribuídos de tempo real (SDTR) objetivando cobrir a crescente demanda de desempenho, previsibilidade e confiabilidade dessas aplicações emergentes. Tais requisitos envolvem baixa latência de transmissão, baixa variabilidade no tempo (jitter), tolerância a falhas e suporte para atualizações futuras - flexibilidade. Particularmente na área automotiva, onde é considerada a possibilidade de substituição de dispositivosmecânicos/hidráulicos por sistemas eletrônicos, conhecidos como "by-wire" systems. Assegurar um comportamento previsível e confiável desses sistemas assim como agregar um nível de flexibilidade são características necessárias em grande parte de aplicações de SDTR. O modelo de comunicação FTT (Flexible Time-Triggered) apresentado nesta dissertação, apresenta um alto grau de flexibilidade em relação a outros protocolos, tais como TTCAN, TTP e FlexRay. Um sistema distribuído de tempo real baseado no modelo FTT se adapta às mudanças de requisitos da aplicação em tempo de execução, sendo possível adicionar novas unidades de controle eletrônico sobre a rede após a fase de projeto. Esta característica advém do escalonador dinâmico deste modelo de comunicação. Este trabalho apresenta algumas propostas de melhoria de desempenho de tempo de resposta do protocolo FTT-CAN, descrevendo alguns pontos negligenciados na atual especificação do protocolo. As propostas têm como foco a estratégia de disparo de mensagens e tarefas, sendo a primeira relacionada à transmissão de mensagens síncrona (ou time-triggered), onde existem dois inconvenientes que geram jitter neste segmento de transmissão; a segunda é relacionado ao disparo de tarefas, onde existem algumas deficiências na liberação de tarefas síncronas na atual especificação do protocolo FTT-CAN. / Embedded computing systems have become widely used in many areas. The greater part of those systems has time constraints and therefore they can be characterized as real time embedded systems. Nowadays, distributed computing has reached the embedded application, where some fieldbuses are already being used as communication platforms. Some important researches has presented different approaches in the real time distributed embedded system domain aiming to cover the growing demands of performance, predictability and reliability of emerging applications. Such requirements involve low latency, reduced jitter, time composability, fault-tolerance and support for future extensions – flexibility. Particularly in the automotive area, on which several mechanical and/or hydraulic systems are being replaced by electronic "by-wire"systems, the importance of ensuring predictable behavior while also presenting some degree of flexibility plays a key role. Regarding to the flexibility, the Flexible Time Triggered communication model stands out against the others ones due to its high degree of flexibility. In this context, the FTT communication model appears as an interesting approach due to its high degree of flexibility while still ensuring a deterministic timing behavior. A distributed system based on a FTT communication infrastructure can adapts to changing application requirements, making possible the addition of new messages and nodes during operation. In this way, the communication infrastructure needs to schedule newest messages on-line. This master’s work presents some proposals to improve the FTT-CAN response-time and indicating some drawbacks in already presented approaches. The improvements are concerning messages and tasks scheduling. Despite of its interesting characteristics, FTT CAN present some negative aspects regarding its timing behavior: the issue is on the synchronous message transmission, where there are two neglected points that generate jitter in this traffic; the other one is tasks dispatching, where there are some deficiencies concerning synchronous tasks execution. These disadvantages were not discussed in literature yet. This work presents new proposals to task and message scheduling of FFT-CAN based applications, therefore overcoming some of the main drawbacks of the protocol.

Nos últimos anos os sistemas embarcados tem-se tornado notório nos mercados de eletroeletrônicos de consumo, automação industrial e comercial e em veículos em geral. Grande parte destas aplicações possui restrições temporais, sendo assim caracterizadas como sistemas de tempo real embarcado. Atualmente, a computação distribuída tem alcançado este tipo de sistema e por razão principal em custos desses sistemas, alguns barramentos ou redes de comunicação vêm sendo empregados como plataforma de conexão entre módulos eletrônicos. Um exemplo de aplicação de sistemas embarcados distribuídos e de tempo real é a eletrônica embarcada em veículos automotores, onde se encontram várias unidades de controle eletrônico espalhadas interior desses veículos com diferentes funções e se comunicando via rede de comunicação. Algumas pesquisas importantes nesta área já apresentaram diferentes abordagens em sistemas distribuídos de tempo real (SDTR) objetivando cobrir a crescente demanda de desempenho, previsibilidade e confiabilidade dessas aplicações emergentes. Tais requisitos envolvem baixa latência de transmissão, baixa variabilidade no tempo (jitter), tolerância a falhas e suporte para atualizações futuras - flexibilidade. Particularmente na área automotiva, onde é considerada a possibilidade de substituição de dispositivosmecânicos/hidráulicos por sistemas eletrônicos, conhecidos como "by-wire" systems. Assegurar um comportamento previsível e confiável desses sistemas assim como agregar um nível de flexibilidade são características necessárias em grande parte de aplicações de SDTR. O modelo de comunicação FTT (Flexible Time-Triggered) apresentado nesta dissertação, apresenta um alto grau de flexibilidade em relação a outros protocolos, tais como TTCAN, TTP e FlexRay. Um sistema distribuído de tempo real baseado no modelo FTT se adapta às mudanças de requisitos da aplicação em tempo de execução, sendo possível adicionar novas unidades de controle eletrônico sobre a rede após a fase de projeto. Esta característica advém do escalonador dinâmico deste modelo de comunicação. Este trabalho apresenta algumas propostas de melhoria de desempenho de tempo de resposta do protocolo FTT-CAN, descrevendo alguns pontos negligenciados na atual especificação do protocolo. As propostas têm como foco a estratégia de disparo de mensagens e tarefas, sendo a primeira relacionada à transmissão de mensagens síncrona (ou time-triggered), onde existem dois inconvenientes que geram jitter neste segmento de transmissão; a segunda é relacionado ao disparo de tarefas, onde existem algumas deficiências na liberação de tarefas síncronas na atual especificação do protocolo FTT-CAN. / Embedded computing systems have become widely used in many areas. The greater part of those systems has time constraints and therefore they can be characterized as real time embedded systems. Nowadays, distributed computing has reached the embedded application, where some fieldbuses are already being used as communication platforms. Some important researches has presented different approaches in the real time distributed embedded system domain aiming to cover the growing demands of performance, predictability and reliability of emerging applications. Such requirements involve low latency, reduced jitter, time composability, fault-tolerance and support for future extensions – flexibility. Particularly in the automotive area, on which several mechanical and/or hydraulic systems are being replaced by electronic "by-wire"systems, the importance of ensuring predictable behavior while also presenting some degree of flexibility plays a key role. Regarding to the flexibility, the Flexible Time Triggered communication model stands out against the others ones due to its high degree of flexibility. In this context, the FTT communication model appears as an interesting approach due to its high degree of flexibility while still ensuring a deterministic timing behavior. A distributed system based on a FTT communication infrastructure can adapts to changing application requirements, making possible the addition of new messages and nodes during operation. In this way, the communication infrastructure needs to schedule newest messages on-line. This master’s work presents some proposals to improve the FTT-CAN response-time and indicating some drawbacks in already presented approaches. The improvements are concerning messages and tasks scheduling. Despite of its interesting characteristics, FTT CAN present some negative aspects regarding its timing behavior: the issue is on the synchronous message transmission, where there are two neglected points that generate jitter in this traffic; the other one is tasks dispatching, where there are some deficiencies concerning synchronous tasks execution. These disadvantages were not discussed in literature yet. This work presents new proposals to task and message scheduling of FFT-CAN based applications, therefore overcoming some of the main drawbacks of the protocol.

Nos últimos anos os sistemas embarcados tem-se tornado notório nos mercados de eletroeletrônicos de consumo, automação industrial e comercial e em veículos em geral. Grande parte destas aplicações possui restrições temporais, sendo assim caracterizadas como sistemas de tempo real embarcado. Atualmente, a computação distribuída tem alcançado este tipo de sistema e por razão principal em custos desses sistemas, alguns barramentos ou redes de comunicação vêm sendo empregados como plataforma de conexão entre módulos eletrônicos. Um exemplo de aplicação de sistemas embarcados distribuídos e de tempo real é a eletrônica embarcada em veículos automotores, onde se encontram várias unidades de controle eletrônico espalhadas interior desses veículos com diferentes funções e se comunicando via rede de comunicação. Algumas pesquisas importantes nesta área já apresentaram diferentes abordagens em sistemas distribuídos de tempo real (SDTR) objetivando cobrir a crescente demanda de desempenho, previsibilidade e confiabilidade dessas aplicações emergentes. Tais requisitos envolvem baixa latência de transmissão, baixa variabilidade no tempo (jitter), tolerância a falhas e suporte para atualizações futuras - flexibilidade. Particularmente na área automotiva, onde é considerada a possibilidade de substituição de dispositivosmecânicos/hidráulicos por sistemas eletrônicos, conhecidos como "by-wire" systems. Assegurar um comportamento previsível e confiável desses sistemas assim como agregar um nível de flexibilidade são características necessárias em grande parte de aplicações de SDTR. O modelo de comunicação FTT (Flexible Time-Triggered) apresentado nesta dissertação, apresenta um alto grau de flexibilidade em relação a outros protocolos, tais como TTCAN, TTP e FlexRay. Um sistema distribuído de tempo real baseado no modelo FTT se adapta às mudanças de requisitos da aplicação em tempo de execução, sendo possível adicionar novas unidades de controle eletrônico sobre a rede após a fase de projeto. Esta característica advém do escalonador dinâmico deste modelo de comunicação. Este trabalho apresenta algumas propostas de melhoria de desempenho de tempo de resposta do protocolo FTT-CAN, descrevendo alguns pontos negligenciados na atual especificação do protocolo. As propostas têm como foco a estratégia de disparo de mensagens e tarefas, sendo a primeira relacionada à transmissão de mensagens síncrona (ou time-triggered), onde existem dois inconvenientes que geram jitter neste segmento de transmissão; a segunda é relacionado ao disparo de tarefas, onde existem algumas deficiências na liberação de tarefas síncronas na atual especificação do protocolo FTT-CAN. / Embedded computing systems have become widely used in many areas. The greater part of those systems has time constraints and therefore they can be characterized as real time embedded systems. Nowadays, distributed computing has reached the embedded application, where some fieldbuses are already being used as communication platforms. Some important researches has presented different approaches in the real time distributed embedded system domain aiming to cover the growing demands of performance, predictability and reliability of emerging applications. Such requirements involve low latency, reduced jitter, time composability, fault-tolerance and support for future extensions – flexibility. Particularly in the automotive area, on which several mechanical and/or hydraulic systems are being replaced by electronic "by-wire"systems, the importance of ensuring predictable behavior while also presenting some degree of flexibility plays a key role. Regarding to the flexibility, the Flexible Time Triggered communication model stands out against the others ones due to its high degree of flexibility. In this context, the FTT communication model appears as an interesting approach due to its high degree of flexibility while still ensuring a deterministic timing behavior. A distributed system based on a FTT communication infrastructure can adapts to changing application requirements, making possible the addition of new messages and nodes during operation. In this way, the communication infrastructure needs to schedule newest messages on-line. This master’s work presents some proposals to improve the FTT-CAN response-time and indicating some drawbacks in already presented approaches. The improvements are concerning messages and tasks scheduling. Despite of its interesting characteristics, FTT CAN present some negative aspects regarding its timing behavior: the issue is on the synchronous message transmission, where there are two neglected points that generate jitter in this traffic; the other one is tasks dispatching, where there are some deficiencies concerning synchronous tasks execution. These disadvantages were not discussed in literature yet. This work presents new proposals to task and message scheduling of FFT-CAN based applications, therefore overcoming some of the main drawbacks of the protocol.

The manufacturing industries play a significant role in contributing to the economy of a country. Among various manufacturing industries, the semiconductor manufacturing (SM) industries is one of the fastest growing industries in the world having worldwide sales of $31 billion in the month of December 2016. Semiconductors are required by large number of industries, including Telecommunications, Medical Electronics, Automobile, Defence and Aerospace, Consumer Electronics, etc.,. Today, without semiconductors, the technology that we count on every day would not be possible. Because of these, the demand for SM industry is increased rapidly. In addition, most of the semiconductor based products‘ life is very short. Due to these, SM industry is highly competitive industry. Thus, to utilize the resources effectively, to handle the huge demand, and to deliver the product on-time, efficient scheduling is important in SM industry. SM process can be broadly classified into Wafer Fabrication (called as wafer fab), Wafer Probing, Assembly, and Final Testing. Scheduling is more important in wafer fab due to complex operations involving with multiple types of machines and re-entrant, expensive machines, and time-consuming process involved. Thus, this study concerns about scheduling in wafer fab, particularly diffusion operation. The diffusion operation, carried out on batch processing machine, heavily impacts the production rate of wafer fab and in turn the SM industry. This is due to the fact that, diffusion operation requires relatively longest processing time among all the operations in the wafer fab. Due to these, diffusion operation is the bottleneck operations in the wafer fab. Based on the detailed literature review, this study addresses a new research problem on dynamic scheduling (DS) of diffusion furnace(s) by considering together the various real-life problem characteristics: Non-identical parallel diffusion furnaces, Machine eligibility restriction, Incompatible-job families, Job and/or resource related real time events, and Non-agreeable release time and due-date. In addition, due to the importance of on-time delivery this study deals with five due-date based scheduling objectives: Total weighted tardiness (TWT), Number of tardy jobs (NT), On time delivery (OTD) rate, Total earliness and lateness (TE/L) and Maximum lateness (Lmax) as a single objective as well as multi objectives. Here, the multi objectives are developed, considering all the five due-date based scheduling objectives in a linear form by randomly assigning equal and unequal weights to each of the due-date based single objectives considered in this study. With these, the main objective of this thesis is to study the impact of job and/or resource related real time events (JR-RTE) on the relative efficiency of the proposed dynamic scheduling algorithms for diffusion furnace(s) while optimizing each of the due-date based scheduling objectives considered in this study. The research problem considered in this study is decomposed into five phases. From the analysis of the literature, it is observed that, there is no earlier study has the mathematical models for dynamic scheduling (DS) of diffusion furnaces to optimize all the due-date based scheduling objectives, considered in this study. Due to this, in the first phase, fourteen (0-1) mixed integer linear programming (MILP) models are proposed for DS of diffusion furnaces (seven models for DS of single diffusion furnace and seven models for DS of non-identical parallel diffusion furnaces) to optimize the due-date based single objectives: TWT, NT, OTD rate, TE/L, and Lmax and multi objectives: MO1 and MO2. All the proposed (0-1) MILP models are demonstrated for its workability by developing a suitable numerical example, LINGO set code (which generates each of the proposed (0-1) MILP model for any given data), and solving using LINGO solver. Further, based on the analysis of the literature a suitable experimental design is proposed and generated 15 small-scale test data. The computational complexity of each of the proposed (0-1) MILP models is discussed empirically by solving 15 small-scale test data. Due to the computational intractability of the proposed (0-1) MILP models for DS of diffusion furnaces, the second phase of the research focuses on a simple alternative approach based on dispatching rules, as the analysis of the literature reveals that dispatching rules are heavily used in the SM industry. However, there is no study in the literature presenting a comparative analysis of various dispatching rules particularly due-date based dispatching rules (DDR) for DS of diffusion furnace(s) to optimize various due-date based scheduling objectives. Accordingly, in the second phase, this study proposes a simple Greedy Algorithm (GA) based on DDR (called as GA-DDR) for Dynamic Scheduling of Single Diffusion Furnace (DS-SDF). Further, this study proposes twenty variants of GA-DDR considering various due-date based dispatching rules such as Earliest Due-Date, Flow Due-Date, Operational Due-Date, Modified Operational Due-Date, Critical Ratio, Minimum Slack First, Cost OVER Time, ten versions of Apparent Tardiness Cost (ATC) [including a new ATC rule proposed in this study] & five versions of Batch Apparent Tardiness Cost (BATC) [including a new BATC rule proposed in this study] for DS-SDF. All these twenty variants of GA-DDR are implemented in Turbo C. An experimental design is proposed in this phase for generating large-scale test data. Accordingly, 270 large-scale problem instances (representing 27 problem configurations and 10 instances per configurations) are generated. With these, a series of computational experiments are carried out to understand the relative efficiency of the twenty proposed variants of GA-DDR as follows: The efficiency of each of the twenty proposed variants of GA-DDR for DS-SDF with respect to each of the scheduling objectives considered in this study is analysed in comparison with optimal objective function value obtained from the corresponding (0-1) MILP models for 15 small-scale problem instances using the standard performance measures: Average Relative Percentage Deviation (ARPD) and Maximum Relative Percentage Deviation (MRPD). Further, for each of the 270 problem instances the efficiency of each of the twenty proposed variants of GA-DDR for DS-SDF with respect to each of the scheduling objectives is analysed in comparison with estimated objective function value, which is computed by giving the twenty feasible solutions obtained for each instances as input to Weibull distribution, (i) empirically using the performance measures: ARPD, MRPD, Integrated Rank (IRANK), & Global comparison based on Worst Solution (GCWS), and (ii) statistically by using the performance measures: Mean, Median, and 95% confidence interval. From the overall analysis, at the end of the second phase of the study, six efficient variants of GA-DDR among the twenty proposed variants of GA-DDR are identified for DS-SDF and discussed the insights for their better performance. In these six efficient variants of GA-DDR, two variants of GA-DDR uses the new ATC rule and/or BATC rule proposed by the author of this thesis. The second phase of the research considers only dynamic arrival of jobs in all the twenty variants of GA-DDR. But, in the real-life various unexpected job related real time events: rush job, due-date change, early/late arrival of job, change in job priority, and job cancellation and/or resource related real time events: machine breakdown, operator illness, tool failure, shortage of material, and defective material will occur in addition to the dynamic arrival of jobs. From the literature, it is observed that, all the studies in the dynamic scheduling of diffusion furnaces consider only future arrival of jobs and no study considering real time events. Further, to the best of our knowledge, the research studies on discrete processing machines develop various rescheduling algorithm or modify the existing algorithm whenever real time events occur while taking the scheduling decision. However, due to the longest operation time requirements at diffusion furnace and the computerized tracking system in the shop floor of wafer fab, we strongly propose a research hypothesis that modifying appropriately the work-in-process (WIP) data and/or the availability time of the corresponding diffusion furnace(s) for next scheduling depending upon the occurrence of job and/or resource related real time events respectively by utilizing the existing computerized tracking system in the shop floor is sufficient, and changing any proposed efficient algorithms for DS-SDF is not required. This hypothesis is proved both empirically and statistically in the third phase of this research, considering the twenty proposed variants of GA-DDR for DS-SDF and the proposed experimental design. Accordingly, this study propose a formal researchable hypothesis that there is no impact of JR-RTE on the relative efficiency of the twenty proposed variants of GA-DDR for DS-SDF while optimizing each of the due-date based scheduling objectives considered in this study. For testing the proposed hypothesis, this study proposed adjusted GA-DDR (with JR-RTE) for each of the proposed GA-DDR, in which there is step to update the WIP data if job related event occurs, and/or the next available time of corresponding diffusion furnace(s) for scheduling the same if resource related event occurs, before finalizing the scheduling decision. Each of the 270 large-scale problem instances generated using the proposed experimental design is solved by each of the 20 adjusted variants of GA-DDR (with JR-RTE). The comparison on the relative efficiency of each of the 20 proposed variants of GA-DDR and adjusted GA-DDR (with JR-RTE) is carried out using the performance measures: ARPD and MRPD [that is, ARPD(GA-DDR) vs. ARPD(adjusted GA-DDR with JR-RTE), and MRPD(GA-DDR) vs. MRPD(adjusted GA-DDR with JR-RTE)] while optimizing each of the seven scheduling objectives considered in this study. The empirical analysis of the comparisons reveals that there is no change in the relative efficiency of each of the 20 proposed variants of GA-DDR and the corresponding 20 adjusted variants of GA-DDR (with JR-RTE) while optimizing each of the scheduling objectives considered in this study. Further, this study proved the proposed hypothesis statistically by conducting the Spearman‘s rank order correlation between each of the 20 variants of GA-DDR and adjusted GA-DDR (with JR-RTE) for DS-SDF while optimizing each of the seven due-date based scheduling objectives considered in this study. From the empirical and statistical analyses carried out in the third phase of the study indicated that, no need to adjust the proposed variants of GA-DDR for any occurrences of real time events for obtaining efficient schedule. The SM industry normally would have more than one non-identical diffusion furnaces and that too in parallel. Due to some technical reasons, some jobs are processed only in specific diffusion furnace(s) available in the shop floor (this is called as machine eligibility restriction in scheduling theory). Hence, the impact of JR-RTE on the dynamic scheduling (DS) of non-identical parallel diffusion furnaces (NPDF) with machine eligibility restriction (MER) is addressed in the fourth phase of this study. In the fourth phase of the research study, the twenty proposed variants of GA-DDR for DS-SDF extended appropriately for DS-NPDF with MER [called as Extended GA-DDR (EGA-DDR)]. Further, a few new problem parameters required for NPDF with MER are identified from the literature and extended the proposed experimental design and generated 270 problem instances for representing NPDF with MER. For testing the proposed hypothesis on the impact of JR-RTE on DS-NPDF with MER, exactly the similar research processes carried out for comparing GA-DDR vs. adjusted GA-DDR (with JR-RTE) is followed for comparing EGA-DDR vs. adjusted EGA-DDR (with JR-RTE). Both empirical and statistical analyses clearly proved that there is no impact of JR-RTE on the relative efficiency of the twenty variants of EGA-DDR for DS-NPDF with MER while optimizing each of the due-date based scheduling objectives considered in this study and no need to adjust the variants of EGA-DDR for any occurrences of real time events for obtaining efficient schedule. So far, the study addressed the development of efficient GA-DDR and EGA-DDR for DS-SDF and DS-NPDF with MER respectively and studied the impact of JR-RTE on the relative efficiency of these proposed GA-DDR and EGA-DDR. Now, in the final phase of the research study, the impact of JR-RTE on the meta heuristics: Simulated Annealing (SA) and Tabu Search (TS), one at a time, for DS-SDF while minimizing TWT are studied. Accordingly, the required parameters for these two meta heuristics are identified from the literature and the meta heuristics: SA and TS, considering each of the six solutions obtained from the six efficient variants of GA-DDR respectively as initial solution are implemented. From the analysis of the solutions obtained, for each of the 270 problem instances, from each of the six efficient variants of GA-DDR and from each of the meta heuristics: SA and TS, it appears that the six efficient proposed variants of GA-DDR seems to be robust in terms of both quality and computational time requirements in obtaining efficient solution. Further, to study the impact of JR-RTE on meta heuristics: SA and TS, this study considers (a) six solutions obtained from each of the six efficient variants of GA-DDR for DS-SDF as the initial solution and obtained six final solutions respectively from each of the meta heuristics, and (b) six solutions obtained from each of the six adjusted variants of GA-DDR (with JR-RTE) for DS-SDF as the initial solution and obtained six final solutions respectively from each of the meta heuristics. For each of the meta heuristics, these two sets of final solutions, obtained for each of the 270 problem instances, are compared empirically and statistically, based on various performance measures considered in this study, and proved the research hypothesis defined in this study. The major research contributions of this study are as follows - By analyzing the literature on scheduling diffusion furnaces and the real-life situation in scheduling diffusion furnaces, a new research problem on dynamic scheduling (DS) of diffusion furnaces with incompatible-job families, machine eligibility restriction, non-agreeable release time and due-date, considering job and/or resource related real time events (JR-RTE) along with dynamic job arrival to optimize due-date based scheduling objectives: TWT, NT, OTD rate, TE/L, and Lmax as a single objective as well as multi objective was defined. - Seven (0-1) MILP models for each of DS-SDF and DS-NPDF were proposed for optimizing each of the seven due-date based scheduling objectives considered in this study and the computational complexity was observed. - Due to the computational complexity of the proposed (0-1) MILP models and the popularity of the dispatching rules in the semiconductor manufacturing industry, this study proposed and compared the twenty variants of (i) greedy algorithm based on due-date based dispatching rules (GA-DDR) for DS-SDF, and (ii) Extended GA-DDR for DS-NPDF with machine eligibility restriction (MER). - The impact of JR-RTE on the twenty proposed variants of (a) GA-DDR for DS-SDF, and (b) EGA-DDR for DS-NPDF with MER was studied and observed that modifying the data appropriately by utilizing the existing computerized tracking system available in the shop floor is sufficient and rescheduling or modifying the existing algorithms are not required when the occurrences of JR-RTE happens. - Finally, single solution based meta heuristics: Simulated Annealing (SA) and Tabu Search (TS), considering each of the six solution obtained from each of the six efficient variants of GA-DDR proposed in this study as initial solution respectively, were proposed for DS-SDF to minimize TWT. Performance analysis of the solution obtained from each of the six efficient variants of GA-DDR and from each of the meta heuristics were carried out and observed that efficient variants of GA-DDR seems to be robust in terms of both quality and computational time requirements in obtaining efficient solution. In addition, the impact of JR-RTE on the meta heuristics: SA and TS were studied and proved the research hypothesis proposed in this study. Although, this study considers many real-life problem characteristics, there are certain limitations in this study. Though this study proposed mathematical model for DS-NPDF, the required additional constraint on Machine Eligibility is not considered in this study. Further, the impact of JR-RTE on the meta heuristics: SA and TS were studied considering only DS-SDF and not for DS-NPDF with MER. In addition to overcoming the limitations mentioned here, there are many immediate future research directions for the problem studied in this thesis such as proposing the greedy algorithms for scheduling diffusion operation along with upstream or downstream operation, and proposing population based meta heuristics for the research problem defined in this study.

For the past several decades, we have experienced the tremendous growth, in both scale and scope, of real-time embedded systems, thanks largely to the advances in IC technology. However, the traditional approach to get performance boost by increasing CPU frequency has been a way of past. Researchers from both industry and academia are turning their focus to multi-core architectures for continuous improvement of computing performance. In our research, we seek to develop efficient scheduling algorithms and analysis methods in the design of real-time embedded systems on multi-core platforms. Real-time systems are the ones with the response time as critical as the logical correctness of computational results. In addition, a variety of stringent constraints such as power/energy consumption, peak temperature and reliability are also imposed to these systems. Therefore, real-time scheduling plays a critical role in design of such computing systems at the system level. We started our research by addressing timing constraints for real-time applications on multi-core platforms, and developed both partitioned and semi-partitioned scheduling algorithms to schedule fixed priority, periodic, and hard real-time tasks on multi-core platforms. Then we extended our research by taking temperature constraints into consideration. We developed a closed-form solution to capture temperature dynamics for a given periodic voltage schedule on multi-core platforms, and also developed three methods to check the feasibility of a periodic real-time schedule under peak temperature constraint. We further extended our research by incorporating the power/energy constraint with thermal awareness into our research problem. We investigated the energy estimation problem on multi-core platforms, and developed a computation efficient method to calculate the energy consumption for a given voltage schedule on a multi-core platform. In this dissertation, we present our research in details and demonstrate the effectiveness and efficiency of our approaches with extensive experimental results.

The resource demand on embedded devices is constantly growing. This is caused by the sheer explosion of software based functions in embedded systems, that are growing far faster than the resources of the single-core and multi-core embedded processors. As one of the limitation is the computing power of the processors we need to explore ways to use this resource more efficiently. We identified that during the run-time of the embedded devices the resource demand of the software functions is permanently changing dependent on the device situation. To enable an embedded device to take advantage of this dynamic resource demand, the allocation of the software functions to the processor must be handled by a scheduler that is able to evaluate the resource demand of the software functions in relation to the device situation. This marks a change in embedded devices from static defined software systems to dynamic software systems. Above that we can increase the efficiency even further by extending the approach from a single device to a distributed or networked system (many-core system). However, existing approaches to deal with dynamic resource allocation are focused on individual devices and leave the optimization potential of manycore systems untouched. Our concept will extend the existing Hierarchical Asynchronous Multi-Core Scheduler (HAMS) concept for individual devices to many-core systems. This extension introduces a dynamic situation aware scheduler for many-core systems which take the current workload of all devices and the system-situation into account. With our approach, the resource efficiency of an embedded many-core system can be increased. The following paper will explain the architecture and the expected results of our concept.