Dans cette thèse, nous considérons une famille des problèmes d’ordonnancement avec machine parallèle identique et contraintes de précédences. Ce champ de recherche fait l’objet de nombreuses études. Malgré tout, la complexité de ces problèmes varie selon de nombreux paramètres,notamment le type de graphe de précédence ou le critère retenu. De plus, il existe encore de nombreux problèmes ouverts. Nous étudions certains de ces problèmes dans cette thèse. Nous montrons notamment que le problème ouvert avec tâches de durée unitaires et graphe de précédence de type intree est NP-complet. Puis, nous prouvons que le problème avec graphe de précédence de type level order est NP-complet aussi. La preuve est ensuite étendue à des problèmes connexes. Par la suite, on améliore un algorithme exponentiel pour un problème spécifique qui est NP-complet. Enfin, nous proposons un modèle linéaire pour le problème avec contraintes de précédence quelconque, améliorant aussi les résultats de littérature. / The main problem studied in this thesis is that of parallel machine scheduling with precedence constraints. The complexity depends on the shape that the precedence graph takes and the objective function. We prove that one minimum-open problem of scheduling equal-processing-time jobs which subject to in-tree precedence constrains is NP complete while minimizing the total competition time.Then, we prove that the open problem of scheduling level-order precedence constrains is NP-complete too. We adapted the second proof to other scheduling problems as well.On the other hand, we improved an exponential algorithm designed for a specific NP-hard problem. At the end, we propose a linear programming model for the general scheduling problem with arbitrary precedence constraints and processing-time. We adapt the existing models which are originally designed for other scheduling problems to parallel scheduling problem and compare these models with ours.

[pt] Esta dissertação investiga o uso de Algoritmos Genéticos e de Co-Evolução Cooperativa na otimização de problemas de planejamento com restrições de precedência. Neste tipo de problema algumas ou todas as tarefas têm restrições que implicam na necessidade de planejá-las ou executá-las antes ou depois de outras. Por esta razão, o uso de modelos evolucionários convencionais como, por exemplo, os baseados em ordem pode gerar soluções inválidas, não penalizáveis, que precisam ser descartadas, comprometendo assim o desempenho do algoritmo. O objetivo do trabalho foi, portanto, estudar formas de representação de soluções para este tipo de problema capazes de gerar somente soluções válidas, bem como avaliar o desempenho dos modelos propostos. O trabalho consistiu de 3 etapas principais: um estudo sobre problemas de otimização de planejamento com algoritmos genéticos; a definição de novos modelos usando algoritmos genéticos e co-evolução cooperativa para otimização de problemas de planejamento com restrições de precedência e a implementação de uma ferramenta para estudo de caso. O estudo sobre os problemas de otimização de planejamentos com algoritmos genéticos envolveu o levantamento de representações, dificuldades e características deste tipo de problema e, mais especificamente, de representações baseadas em ordem. A modelagem do algoritmo genético consistiu fundamentalmente na definição de uma representação dos cromossomas e da função da avaliação que levasse em conta a existência de restrições de precedência (tarefas que devem ser planejadas/executadas antes de outras). A construção do modelo co-evolucionário por sua vez consistiu em definir uma nova população, com uma outra representação, que se responsabilizasse pela distribuição dos recursos para execução das tarefas, responsabilidade esta que, no modelo com algoritmos genéticos convencionais, era tratada de forma simples por um conjunto de heurísticas. Finalmente, desenvolveu-se uma ferramenta para implementar estes modelos e tratar de um estudo de caso complexo que oferecesse as características necessárias para testar a qualidade das representações e avaliar os resultados. O estudo de caso escolhido foi a otimização do planejamento da descarga, armazenamento e embarque de minério de ferro de modo a minimizar o tempo de estadia dos navios em um porto fictício. Foram realizados vários testes que demonstraram a capacidade dos modelos desenvolvidos em gerar soluções viáveis, sem a necessidade de heurísticas de correção, e os resultados obtidos foram comparados com os de um processo de busca aleatória. Em todos os casos, os resultados obtidos pelos modelos foram sempre superiores aos obtidos pela busca aleatória. No caso do modelo de representação com uma única população obteve-se resultados até 41% melhores do que com os obtidos por uma busca aleatória. No caso do modelo de representação com co-evolução o resultado ficou 33% melhor que a busca aleatória com tratamento de solução idêntico ao da solução co-evolucionária. Os resultados da co-evolução comparados com o algoritmo genético com uma única espécie foram 29% melhores. / [en] This work investigates the use of Genetic Algorithms and Cooperative Co-Evolution in optimization of scheduling problems with precedence constraints. In this kind of problem some or all tasks have constraints that imply planning or executing them before or after others. For this reason, the use of order-based conventional evolutionary models may generate invalid solutions, which cannot be penalized, needing to be discarded and therefore compromising the algorithm performance. The main goal was therefore to study models for this kind of problem that are capable of generating only valid solutions. The work was divided in 3 main steps: a survey on scheduling optimization problems using genetic algorithms; definition of two models based on genetic algorithms and cooperative co-evolution for optimizing scheduling problems with precedence constraints; and the implementation of a tool for a case study. The study on scheduling optimization problems with genetic algorithms consisted in gathering information about representations and characteristics of this kind of problem and, more specifically, about order-based representations. The genetic algorithm modeling consisted basically in defining a chromosome representation and an evaluation function that took into account the existence of precedence constraints (tasks that must be scheduled or executed before others). The co-evolutionary model consisted in defining a new population, with another representation scheme, which was responsible for distributing resources for tasks execution. On the conventional genetic algorithm model, this role was played by a simple set of heuristics. Finally, a tool was developed for implementing those models and treating a complex case study which offered the needed characteristics for testing representation performance and evaluating results. The chosen case study was the optimization of iron ore dumping, stocking and ship loading on a fictitious harbor, targeting minimization of ships waiting time. Tests were done in order to demonstrate the ability of the developed models in generating viable solutions without the need of corrective heuristics and the results were compared to the results obtained through exhaustive search. In all cases, the models` results were better than the exhaustive search ones. In the case where the representation used a single population the results obtained were up to 41% better than the ones with the exhaustive search. The co- evolutionary results outperformed the co-evolutionary search with the same solution representation by 33%. Compared to the single specie genetic algorithm, the co- evolutionary model outperformed it by 29%.

Embedded real time applications are often subject to time and energy constraints. Real time applications are usually characterized by logically separable set of tasks with precedence constraints. The computational effort behind each of the task in the system is responsible for a physical functionality of the embedded system. In this work we mainly define theoretical models for relating the quality of the physical func- tionality to the computational load of the tasks and develop optimization problems to maximize the quality of the system subject to various constraints like time and energy. Specifically, the novelties in this work are three fold. This work deals with maximizing the final output quality of a set of precedence constrained tasks whose quality can be expressed with appropriate cost functions. We have developed heuristic scheduling algorithms for maximizing the quality of final output of embedded applications. This work also dealswith the fact that the quality of output of a task in the system has noticeable effect on quality of output of the other dependent tasks in the system. Finally run time characteristics of the tasks are also modeled by simulating a distribution of run times for the tasks, which provides for averaged quality of output for the system rather than un-sampled quality based on arbitrary run times. Many real-time tasks fall into the IRIS (Increased Reward with Increased Service) category. Such tasks can be prematurely terminated at the cost of poorer quality output. In this work, we study the scheduling of IRIS tasks on multiprocessors. IRIS tasks may be dependent, with one task feeding other tasks in a Task Precedence Graph (TPG). Task output quality depends on the quality of the input data as well as on the execution time that is allowed. We study the allocation/scheduling of IRIS TPGs on multiprocessors to maximize output quality. The heuristics developed can effectively reclaim resources when tasks finish earlier than their estimated worst-case execution time. Dynamic voltage scaling is used to manage energy consumption and keep it within specified bounds.

This dissertation is devoted to the development of new flow-based formulations for the asymmetric traveling salesman problem (ATSP) and to the demonstration of their applicability in effectively solving some scheduling problems. The ATSP is commonly encountered in the areas of manufacturing planning and scheduling, and transportation logistics. The integration of decisions pertaining to production and shipping, in the supply chain context, has given rise to an additional and practical relevance to this problem especially in situations involving sequence-dependent setups and routing of vehicles. Our objective is to develop new ATSP formulations so that algorithms can be built by taking advantage of their relaxations (of integer variables, thereby, resulting in linear programs) to effectively solve large-size problems. In view of our objective, it is essential to have a formulation that is amenable to the development of an effective solution procedure for the underlying problem. One characteristic of a formulation that is helpful in this regard is its tightness. The tightness of a formulation usually refers to the quality of its approximation to the convex hull of integer feasible solutions. Another characteristic is its compactness. The compactness of a formulation is measured by the number of variables and constraints that are used to formulate a given problem. Our formulations for the ATSP and the scheduling problems that we address are both tight and compact. We present a new class of polynomial length formulations for the asymmetric traveling salesman problem (ATSP) by lifting an ordered path-based model using logical restrictions in concert with the Reformulation-Linearization Technique (RLT). We show that a relaxed version of this formulation is equivalent to a flow-based ATSP model, which, in turn, is tighter than the formulation based on the exponential number of Dantzig-Fulkerson-Johnson (DFJ) subtour elimination constraints. The proposed lifting idea is applied to derive a variety of new formulations for the ATSP, and a detailed analysis of these formulations is carried out to show that some of these formulations are the tightest among those presented in the literature. Computational results are presented to exhibit the relative tightness of our formulations and the efficacy of the proposed lifting process.> While the computational results demonstrate the efficacy of employing the proposed theoretical RLT and logical lifting ideas, yet it remains of practical interest to take due advantage of the tightest formulations. The key requirement to accomplish this is the ability to solve the underlying LP relaxations more effectively. One approach, to that end, is to solve these LP relaxations to (near-) optimality by using deflected subgradient methods on Lagrangian dual formulations. We solve the LP relaxation of our tightest formulation, ATSP6, to (near-) optimality by using a deflected subgradient algorithm with average direction strategy (SA_ADS) (see Sherali and Ulular [69]). We also use two nondifferentiable optimization (NDO) methods, namely, the variable target value method (VTVM) presented by Sherali et al. [66] and the trust region target value method (TRTV) presented by Lim and Sherali [46], on the Lagrangian dual formulation of ATSP6. The preliminary results show that the near-optimal values obtained by the VTVM on solving the problem in the canonical format are the closest to the target optimal values. Another approach that we use is to derive a set of strong valid inequalities based on our tighter formulations through a suitable surrogation process for inclusion within the more compact manageable formulations. Our computational results show that, when the dual optimal solution is available, the associated strong valid inequalities generated from our procedure can successfully lift the LP relaxation of a less tight formulation, such as ATSP2R¯, to be as tight as the tightest formulation, such as ATSP6. We extend our new formulations to include precedence constraints in order to enforce a partial order on the sequence of cities to be visited in a tour. The presence of precedence constraints within the ATSP framework is encountered quite often in practice. Examples include: disassembly optimization (see Sarin et al. [62]), and scheduling of wafers/ ICs on automated testing equipments in a semiconductor manufacturing facility (see Chen and Hsia [17]); among others. Our flow-based ATSP formulation can very conveniently capture these precedence constraints. We also present computational results to depict the tightness of our precedence-constrained asymmetric traveling salesman problem (PCATSP) formulations. We, then, apply our formulations to the hot strip rolling scheduling problem, which involves the processing of hot steel slabs, in a pre-specified precedence order, on one or more rollers. The single-roller hot strip rolling scheduling problem can be directly formulated as a PCATSP. We also consider the multiple-roller hot strip rolling scheduling problem. This gives rise to the multiple-asymmetric traveling salesman problem (mATSP). Not many formulations have been presented in the literature for the mATSP, and there are none for the mATSP formulations involving a precedence order among the cities to be visited by the salesmen, which is the case for the multiple-roller hot strip rolling scheduling problem. To begin with, we develop new formulations for the mATSP and show the validity of our formulations, and present computational results to depict their tightness. Then, we extend these mATSP formulations to include a pre-specified, special type of precedence order in which to process the slabs, and designate the resulting formulations as the restricted precedence-constrained multiple-asymmetric traveling salesman problem (rPCmATSP) formulations. We directly formulate the multiple-roller hot strip rolling scheduling problem as a rPCmATSP. Furthermore, we consider the hot strip rolling scheduling problem with slab selection in which not all slabs need to be processed. We model the single-roller hot strip rolling scheduling problem with slab selection as a multiple-asymmetric traveling salesman problem with exactly two traveling salesmen. Similarly, the multiple-roller hot strip rolling scheduling problem with slab selection is modeled as a multiple-asymmetric traveling salesman problem with (m+1) traveling salesmen. A series of computational experiments are conducted to exhibit the effectiveness of our formulations for the solution of hot strip rolling scheduling problems. Furthermore, we develop two mixed-integer programming algorithms to solve our formulations. These are based on Benders΄ decomposition [13] and are designated Benders΄ decomposition and Modified Benders΄ methods. In concert with a special type of precedence order presented in the hot strip rolling scheduling problems, we further introduce an adjustable density ratio of the associated precedence network and we use randomly generated test problems to study the effect of various density ratios in solving these scheduling problems. Our experimentation shows the efficacy of our methods over CPLEX. Finally, we present a compact formulation for the job shop scheduling problem, designated as JSCD (job shop conjunctive-disjunctive) formulation, which is an extension of our ATSP formulations. We use two test problems given in Muth and Thompson [53] to demonstrate the optimal schedule and the lower bound values obtained by solving the LP relaxations of our formulations. However, we observe that the lower bound values obtained by solving the LP relaxations of all variations of our JSCD formulation equal to the maximum total processing time among the jobs in the problem. / Ph. D.

No description available.

Research into modular approaches for constructing power electronics control systems has provided a number of benefits, as well as new opportunities. Control systems composed of an interconnected collection of standardized parts makes distributed processing a realistic possibility. Unfortunately, current strategies to supporting software on such systems have a number of critical drawbacks. Many existing approaches rely on centralized control strategies, fail to support fault tolerance in the face of failures among processing nodes or communications links, and fail to robustly support live addition or removal of nodes from a running network. In this context, failure of a single element means failure of the entire system. This thesis describes research to extend the Dataflow Architecture Real-time Kernel (DARK) to support distributed, fault-tolerant execution of control algorithms for power electronics control systems. An appropriate scheme for fault-tolerant scheduling of processes on distributed processing nodes is described, added to DARK, and evaluated. Literature indicates that fault-tolerant multiprocessor scheduling for hard real-time tasks with task precedence constraints is an NP-hard problem. The new system is based on an off-line fault-tolerant scheduling strategy that generates a static schedule of tasks for each processing unit to follow. This algorithm handles both the task precedence constraints and the constraints imposed by the underlying network protocol(DRPESNET). Modifications to the underlying daisy-chained, packet-switched, time-triggered ring network protocol to support communications fault tolerance and plug-and-play addition or removal of live nodes from an existing control system are also described. / Master of Science