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.

This diploma thesis contains the technological project of a Wastewater treatment plant and sewer system located in Brno and. Thesis is focused on a selected part of a technology project that co-creates detailed description of work activities and their relation during construction.

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.

Dans cette thèse, nous nous intéressons à la validation temporelle ainsi qu'au déploiement d'applications de contrôle industriel à base de composants. La technologie des composants retenue est celle des Blocs Fonctionnels définie dans la norme industrielle IEC 61499. Un Bloc Fonctionnel est défini comme un composant réactif supportant des fonctionnalités d'une application. L'avantage de cette norme, connue dans l'industrie, est la description statique de l'application ainsi que de son support d'exécution. Une première contribution de la thèse est l'interprétation des différents concepts définis dans la norme. Nous précisons, en particulier, la dynamique du composant en vue de décrire un comportement déterministe de l'application. Pour appliquer une validation temporelle exhaustive, nous proposons un modèle de comportement d'un Bloc Fonctionnel à l'aide du formalisme des automates temporisés. D'autre part, nous fournissons une sémantique au concept de réseau de Blocs Fonctionnels pour décrire une application comme une composition de Blocs. Une deuxième contribution de la thèse est le déploiement de tels réseaux sur une architecture distribuée multi-tâches tout en respectant des propriétés sur les temps de réponse de bout en bout. Nous transformons un réseau de Blocs Fonctionnels vers un ensemble de tâches élémentaires dépendantes, appelées actions. Cette transformation permet l'exploitation de résultats d'ordonnancement pour valider la correction temporelle de l'application. Pour déployer les blocs d'une application, nous proposons une approche hybride alliant un ordonnancement statique non-préemptif et un autre ordonnancement en ligne préemptif. L'ordonnancement statique permet la construction des tâches s'exécutant sur chaque calculateur. Ces tâches sont vues comme des séquencements statiques d'actions. Elles sont alors à ordonnancer dynamiquement selon une politique préemptive reposant sur EDF (Earliest Deadline First). Grâce à cette approche, nous réduisons le nombre de commutation de contexte en regroupant les actions au sein des tâches. De plus l'ordonnancement dynamique préemptif augmente la faisabilité du système. Enfin, une dernière contribution est une extension de la deuxième. Nous proposons une approche d'allocation de réseaux de blocs fonctionnels sur un support d'exécution distribué. Cette allocation, basée sur une heuristique de Liste, se repose sur la méthode hybride pour assurer un déploiement faisable de l'application. Le problème d'allocation est de trouver pour chaque bloc fonctionnel le calculateur capable de l'exécuter tout en respectant des contraintes fonctionnelles, temporelles et de support d'exécution. Notons enfin que l'heuristique proposée se base sur une technique de retour-arrière pour augmenter l'espace de solutions. / This thesis deals with the temporal validation and the deployment of component-based industrial control applications. We are interested in the Function Blocks approach, defined in the IEC 61499 standard, as a well known component based technology in the industry. A Function Block is an event triggered component owning data to support the application functionalities. The advantage of this technology is the taking into account of the application and also its execution support. The first thesis contribution deals with the interpretation of the different concepts defined in the standard. In particular, we propose a policy defining a deterministic behavior of a FB. To apply an exhaustive temporal validation of the application, we propose a behavioral model of a Block as Timed Automata. On the other hand, we propose a semantic for the concept of FBs networks to develop industrial control applications. The second thesis contribution deals with the deployment of FBs networks in a distributed multi-tasking architecture. Such deployment has to respect classical End to End Response Time Bounds as temporal constraints. To validate the temporal behavior of an application, we propose an approach transforming its blocks into an actions system with precedence constraints. The purpose is to exploit previous theories on the scheduling of real-time systems. To deploy FBs networks in feasible OS tasks, we propose a Hybrid scheduling approach combining an off-line non-preemptive scheduling and an on-line preemptive one. The off-line scheduling allows to construct OS tasks from FBs, whereas the on-line one allows to schedule these tasks according to the classical EDF policy. A constructed OS task is an actions sequence defining an execution scenario of the application. Thanks to this approach, we reduce the context switching at run-time by merging application actions in OS tasks. In addition, the system feasibility is increased by applying an on-line preemptive policy. Finally, the last thesis contribution is an extension of the previous one. We propose an approach allocating FBs networks in a distributed architecture. Based on a heuristic, such approach uses the hybrid method to construct feasible OS tasks in calculators. The allocation problem of a particular application FB is to look for a corresponding calculator while respecting functional, temporal and execution support constraints. We note that the proposed heuristic is based on a back-tracking technic to increase the solutions space.

Les travaux réalisés dans le cadre de cette thèse ont pour objectif de proposer un langage de description temporelle pour des systèmes temps-réel et d’établir les conditions de leur ordonnançabilité sous l’algorithme Earliest Deadline First (EDF). Les langages de description temporelle permettent de spécifier le comportement temporel d’une application indépendamment de son comportement fonctionnel. Le programmeur déclare dans ces langages à quels instants précis doivent être déclenchées et terminées les activités du système. Cette gestion du temps, précise et explicite, apporte au système son caractère déterministe. Le langage proposé, Extended Timing Definition Language (E-TDL), étend des langages dirigés par le temps existants, en particulier Giotto et TDL, en introduisant un nouveau modèle de tâche donné par quatre paramètres : phase, pire temps d’exécution, temps d’exécution logique TEL (intervalle de temps séparant le lancement de la tâche et sa terminaison) et période. L’introduction de ce nouveau modèle de tâche nécessite de revisiter en particulier le problème de l’ordonnançabilité des tâches pour EDF. Cette thèse propose et développe une analyse basée sur la fonction de demande pour des ensembles de tâches décrites en E-TDL et s’exécutant en contexte monoprocesseur. Une condition nécessaire et suffisante est obtenue au travers d’une analyse précise des intervalles séparant les activations de tâches au sein de différents modules s’exécutant indépendamment et pouvant changer de mode à des instants prédéfinis. Une borne de la longueur des intervalles sur lesquels doit s’opérer la vérification est déterminée. Un outil mettant en œuvre cette analyse a été développé. / The goal of this research is to define a time-triggered language for modeling real-time systems and to provide the conditions for their schedulability under Earliest Deadline First (EDF). Time-triggered languages separate the functional part of applications from their timing definition. These languages permit to model the real-time system temporal behavior by assigning system activities to particular time instants. We propose a new time-triggered framework, Extended Timing Definition Language (E-TDL), that enhances the basic task model used in Giotto and TDL while keeping compositional and modular structure brought by the latter. An E-TDL task is characterized by: an offset, a worst case execution time, a Logical Execution Time (a time interval between task release and its termination) and a period. The schedulability analysis of the system based on this new task model should be, in particular for EDF, investigated. We develop, on the concept of the processor demand criterion, conditions for the feasibility of an E-TDL system running on a single CPU under EDF. A necessary and sufficient condition is obtained by considering the global schedules that are made up of execution traces occurring at the same time in distinct modules that are able to switch their modes at predefined instants. We estimate a maximal length of the interval on which the schedulability condition must be checked. A tool suite performing the schedulability analysis of the E-TDL systems is developed.