Emerging technologies enable a set of distributed resources across a network to be linked together and used in a coordinated fashion to solve a particular parallel application at the same time. Such applications are often abstracted as directed acyclic graphs (DAGs), in which vertices represent application tasks and edges represent data dependencies between tasks. Effective scheduling mechanisms for DAG applications are essential to exploit the tremendous potential of computational resources. The core issues are that the availability and performance of resources, which are already by their nature heterogeneous, can be expected to vary dynamically, even during the course of an execution. In this thesis, we first consider the problem of scheduling DAG task graphs onto heterogeneous resources with changeable capabilities. We propose a list-scheduling heuristic approach, the Global Task Positioning (GTP) scheduling method, which addresses the problem by allowing rescheduling and migration of tasks in response to significant variations in resource characteristics. We observed from experiments with GTP that in an execution with relatively frequent migration, it may be that, over time, the results of some task have been copied to several other sites, and so a subsequent migrated task may have several possible sources for each of its inputs. Some of these copies may now be more quickly accessible than the original, due to dynamic variations in communication capabilities. To exploit this observation, we extended our model with a Copying Management(CM) function, resulting in a new version, the Global Task Positioning with copying facilities (GTP/c) system. The idea is to reuse such copies, in subsequent migration of placed tasks, in order to reduce the impact of migration cost on makespan. Finally, we believe that fault tolerance is an important issue in heterogeneous and dynamic computational environments as the availability of resources cannot be guaranteed. To address the problem of processor failure, we propose a rewinding mechanism which rewinds the progress of the application to a previous state, thereby preserving the execution in spite of the failed processor(s). We evaluate our mechanisms through simulation, since this allow us to generate repeatable patterns of resource performance variation. We use a standard benchmark set of DAGs, comparing performance against that of competing algorithms from the scheduling literature.

One of the problems of real-life production scheduling is dynamics of manufacturing environments with new production demands and breaking machines during the schedule execution. Simple rescheduling from scratch in response to unexpected events occurring on the shop floor may require excessive computation time. Moreover, the recovered schedule may be prohibitively deviated from the ongoing schedule. This thesis reviews existing approaches in the field of dynamic scheduling and proposes techniques how to modify a schedule to accommodate disturbances such as resource failure, hot order arrival or order cancellation. The importance is put on the speed of suggested procedures as well as on a minimum modification from the original schedule. The scheduling model is motivated by the FlowOpt project, which is based on the Temporal Networks with Alternatives. The algorithms are written in the C# language.

The area of focus for this research is the Stochastic Resource Constrained Project Scheduling Problem (SRCPSP) with Stochastic Task Insertion (STI). The STI problem is a specific form of the SRCPSP, which may be considered to be a cross between two types of problems in the general form: the Stochastic Project Scheduling Problem, and the Resource Constrained Project Scheduling Problem. The stochastic nature of this problem is in the occurrence/non-occurrence of tasks with deterministic duration. Researchers Selim (2002) and Grey (2007) laid the groundwork for the research on this problem. Selim (2002) developed a set of robustness metrics and used these to evaluate two initial baseline (predictive) scheduling techniques, optimistic (0% buffer) and pessimistic (100% buffer), where none or all of the stochastic tasks were scheduled, respectively. Grey (2007) expanded the research by developing a new partial buffering strategy for the initial baseline predictive schedule for this problem and found the partial buffering strategy to be superior to Selim s extreme buffering approach. The current research continues this work by focusing on resource aspects of the problem, new buffering approaches, and a new rescheduling method. If resource usage is important to project managers, then a set of metrics that describes changes to the resource flow would be important to measure between the initial baseline predictive schedule and the final as-run schedule. Two new sets of resource metrics were constructed regarding resource utilization and resource flow. Using these new metrics, as well as the Selim/Grey metrics, a new buffering approach was developed that used resource information to size the buffers. The resource-sized buffers did not show to have significant improvement over Grey s 50% buffer used as a benchmark. The new resource metrics were used to validate that the 50% buffering strategy is superior to the 0% or 100% buffering by Selim. Recognizing that partial buffers appear to be the most promising initial baseline development approach for STI problems, and understanding that experienced project managers may be able to predict stochastic probabilities based on prior projects, the next phase of the research developed a new set of buffering strategies where buffers are inserted that are proportional to the probability of occurrence. The results of this proportional buffering strategy were very positive, with the majority of the metrics (both robustness and resource), except for stability metrics, improved by using the proportional buffer. Finally, it was recognized that all research thus far for the SRCPSP with STI focused solely on the development of predictive schedules. Therefore, the final phase of this research developed a new reactive strategy that tested three different rescheduling points during schedule eventuation when a complete rescheduling of the latter portion of the schedule would occur. The results of this new reactive technique indicate that rescheduling improves the schedule performance in only a few metrics under very specific network characteristics (those networks with the least restrictive parameters). This research was conducted with extensive use of Base SAS v9.2 combined with SAS/OR procedures to solve project networks, solve resource flow problems, and implement reactive scheduling heuristics. Additionally, Base SAS code was paired with Visual Basic for Applications in Excel 2003 to implement an automated Gantt chart generator that provided visual inspection for validation of the repair heuristics. The results of this research when combined with the results of Selim and Grey provide strong guidance for project managers regarding how to develop baseline predictive schedules and how to reschedule the project as stochastic tasks (e.g. unplanned work) do or do not occur. Specifically, the results and recommendations are provided in a summary tabular format that describes the recommended initial baseline development approach if a project manager has a good idea of the level and location of the stochasticity for the network, highlights two cases where rescheduling during schedule eventuation may be beneficial, and shows when buffering proportional to the probability of occurrence is recommended, or not recommended, or the cases where the evidence is inconclusive.

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

A hierarchical control system is proposed for automated flexible manufacturing cells (FMC) that operate in a job shop flow setting. The control system is made up of a higher level scheduler/reactive scheduler, which optimizes the production flow within the cell, and a lower level supervisor that implements the decisions of the scheduler on the shop floor. Previous studies have regularly considered the production scheduling and the supervisory control as two separate problems. This has led to: i) deadlock-prone optimized schedules that cannot be implemented in an automated setting, ii) deadlock-free optimized schedules that lack the means to be transformed into shop floor supervisors, or iii) supervisors that can safely drive the system with no consideration for production performance. The proposed control system combines mathematical models and an insertion heuristic to solve the deadlock-free scheduling problem in job shops, a deadlock-free reactive scheduling heuristic that can revise the schedules upon the occurrence of a wide variety of disruptions, and a systematic procedure that can transform schedules into readily implementable Petri net (PN) supervisors. The integration of these modules into one control hierarchy guarantees a correct, optimized and agile behavior of the controlled system. The performances of the mathematical models, the scheduling and the reactive scheduling heuristics were evaluated by comparison to performances of previous approaches. Experimental results showed that the proposed modules performed consistently better than the other corresponding approaches. The supervisor realization procedure and the overall control architecture were validated by simulation and implementation in an experimental robotic FMC. The control system developed was capable of driving the experimental cell to satisfactorily complete the processing of different product mixes that featured complex processing routes through the cell.

A hierarchical control system is proposed for automated flexible manufacturing cells (FMC) that operate in a job shop flow setting. The control system is made up of a higher level scheduler/reactive scheduler, which optimizes the production flow within the cell, and a lower level supervisor that implements the decisions of the scheduler on the shop floor. Previous studies have regularly considered the production scheduling and the supervisory control as two separate problems. This has led to: i) deadlock-prone optimized schedules that cannot be implemented in an automated setting, ii) deadlock-free optimized schedules that lack the means to be transformed into shop floor supervisors, or iii) supervisors that can safely drive the system with no consideration for production performance. The proposed control system combines mathematical models and an insertion heuristic to solve the deadlock-free scheduling problem in job shops, a deadlock-free reactive scheduling heuristic that can revise the schedules upon the occurrence of a wide variety of disruptions, and a systematic procedure that can transform schedules into readily implementable Petri net (PN) supervisors. The integration of these modules into one control hierarchy guarantees a correct, optimized and agile behavior of the controlled system. The performances of the mathematical models, the scheduling and the reactive scheduling heuristics were evaluated by comparison to performances of previous approaches. Experimental results showed that the proposed modules performed consistently better than the other corresponding approaches. The supervisor realization procedure and the overall control architecture were validated by simulation and implementation in an experimental robotic FMC. The control system developed was capable of driving the experimental cell to satisfactorily complete the processing of different product mixes that featured complex processing routes through the cell.

Submitted by Izabel Franco (izabel-franco@ufscar.br) on 2016-09-21T13:50:00Z No. of bitstreams: 1 TeseCCMT.pdf: 3540141 bytes, checksum: e392913d01ce26b3d8bd932aa7e84611 (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2016-09-27T19:31:27Z (GMT) No. of bitstreams: 1 TeseCCMT.pdf: 3540141 bytes, checksum: e392913d01ce26b3d8bd932aa7e84611 (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2016-09-27T19:31:38Z (GMT) No. of bitstreams: 1 TeseCCMT.pdf: 3540141 bytes, checksum: e392913d01ce26b3d8bd932aa7e84611 (MD5) / Made available in DSpace on 2016-09-27T19:42:35Z (GMT). No. of bitstreams: 1 TeseCCMT.pdf: 3540141 bytes, checksum: e392913d01ce26b3d8bd932aa7e84611 (MD5) Previous issue date: 2015-03-31 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / The generation of Reactive Production Scheduling (PRP) in order to minimize the makespan is an important activity in the manufacturing industry, in view of the numerous articles reflecting this search today. Among these studies highlight the global search use in hybridization or collaboration with local search, especially of Genetic Algorithm (GA) with Variable Neighborhood Search (VNS). But see that the neighborhood structures used are not related to the goal of makespan minimization or when they are, are difficult to obtain. In order to cover this topic, this thesis proposes the hypothesis that a strongly correlated neighborhood structure with objective of makespan minimization in PRP problems, based on spanning tree, and applied on a collaboration among a genetic algorithm with VNS, perform better or equal to those obtained by other studies using other neighborhood structures or without the use of local search. The purpose was to construct a collaboration of GA and VNS using a neighborhood structure based on the mapping of the solution in the spanning tree associated with the problem, in the local search time, and operating with the insert, swap and 2-opt operators. The planning of experiments for validation contemplated since the implementation and comparison of four variants of reactive production scheduling in three job shop scenarios of different sizes. Each pair of comparisons had its calculated sample size and has been tested with the appropriate hypothesis test. The four variants were compared: Genetic Algorithm only and three collaborations of GA with VNS using the neighborhood structure proposal and two other neighborhood structures (Critical Path and Natural Representation) found in the literature review. The scenarios came from Taillard base. The tests corroborate the hypothesis, with 95% confidence, compared to other works and the main contribution of this thesis is to create an efficient method for minimizing makespan in PRP. / A geração de Programação Reativa da Produção (PRP), com o objetivo de minimizar o makespan, é uma atividade importante na indústria manufatureira, tendo em vista os numerosos artigos que abordam esta pesquisa na atualidade. Dentre estas pesquisas, destaca-se o uso de hibridização ou colaboração de busca global com busca local, notadamente de Algoritmo Genético (AG) com Variable Neighborhood Search (VNS). Porém, nota-se que as estruturas de vizinhança utilizadas não são correlatas à função de minimização de makespan ou, quando o são, são de difícil obtenção. Com o intuito de cobrir tal tópico, esta tese propõe a hipótese de que uma estrutura de vizinhança fortemente correlata ao objetivo de minimização de makespan em problemas de PRP, baseando-se em árvore de cobertura e aplicada em uma colaboração de algoritmo genético e VNS, obtém resultados melhores aos obtidos por outros trabalhos, que fazem uso de outras estruturas de vizinhança ou que não utilizam a busca local. A proposta é a construção de um método de colaboração entre AG e VNS usando uma estrutura de vizinhança baseada no mapeamento da solução, em tempo de busca local, na árvore de cobertura associada ao problema, atuando com os operadores insert, swap e 2-opt. O planejamento dos experimentos para validação contempla a execução e comparação de quatro variantes de solução de problemas de Programação Reativa da Produção em três cenários de job shop de diversas dimensões. Cada par de comparações tem seu tamanho amostral calculado e é examinado com o teste de hipótese adequado. As quatro variantes comparadas são: Algoritmo Genético e três colaborações entre Algoritmo Genético e Variable Neighborhood Search (VNS) usando a estrutura de vizinhança proposta e outras duas estruturas de vizinhança (Caminho Crítico e Representação Natural) encontradas na revisão da literatura. Os cenários vem da base Taillard. Os testes corroboram a hipótese com 95% de confiança na comparação com outros trabalhos e a principal contribuição desta tese é a criação de um método eficiente para minimização de makespan em PRP.

Submitted by Alison Vanceto (alison-vanceto@hotmail.com) on 2017-08-30T12:26:40Z No. of bitstreams: 1 DissMSV.pdf: 2771156 bytes, checksum: add74067c9db203edececa7202e83a52 (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2017-09-20T14:06:15Z (GMT) No. of bitstreams: 1 DissMSV.pdf: 2771156 bytes, checksum: add74067c9db203edececa7202e83a52 (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2017-09-20T14:06:22Z (GMT) No. of bitstreams: 1 DissMSV.pdf: 2771156 bytes, checksum: add74067c9db203edececa7202e83a52 (MD5) / Made available in DSpace on 2017-09-20T14:11:11Z (GMT). No. of bitstreams: 1 DissMSV.pdf: 2771156 bytes, checksum: add74067c9db203edececa7202e83a52 (MD5) Previous issue date: 2016-08-29 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / In recent years, several studies have been carried out to minimize the production time (makespan) in a production schedule of a scenario that represents a manufacturing system. The problem of production scheduling is classified as a combinatorial problem belongs to the NP-hard class of computational problems. Furthermore, in a real world production system, there are many unexpected events (eg, review of production, entry of new products, breaking machines, etc.). To deal with the interruptions of the initial programming, we need to change any settings, which is called reactive production schedule or, simply, reactive scheduling. As a problem of combinatorial features, meta-heuristics is widely used in its resolution. This paper proposes a method that uses an evolutionary meta-heuristic Genetic Algorithm in conjunction with an operator called “Transgenics”, which allows to manipulate the genetic material of individuals adding features which are believed to be important, with the proposal to direct some population of individuals to a more favorable solution to the problem without removing the diversity of the population with a lower cost of time. The objective of this study is to use the Genetic Algorithm with transgenics operator obtain a reactive programming acceptable response time to minimize the makespan value. The objective of this study is to use the Genetic Algorithm with transgenics Operator obtain a reactive programming acceptable response time to minimize the makespan value. Experimental results show the proposed algorithm is able to bring better results than the makespan algorithm and compared in a shorter processing time due to the search direction which provides transgenic operator. / Nos últimos anos, várias pesquisas vêm sendo realizadas a fim de minimizar o tempo total de produção (makespan) em uma programação da produção de algum cenário que representa um sistema de manufatura. O problema da programação da produção é classificado como sendo um problema combinatório pertencente à classe NP-Hard dos problemas computacionais. Além disso, em um sistema de produção real, há muitos eventos inesperados (por exemplo, a revisão da produção, chegada de novos produtos, quebra máquinas, etc.). Para lidar com as interrupções da programação inicial, é preciso realizar outra programação, a qual é denominada de programação reativa da produção. Sendo um problema de recursos combinatórios, é amplamente utilizado metaheurísticas em sua resolução. Neste trabalho é proposto um método que faz uso de uma metaheurística evolutiva Algoritmo Genético em conjunto com um operador intitulado Operador de Transgenia, no qual possibilita manipular o material genético dos indivíduos acrescentando características das quais se acredita serem importantes, com a proposta de direcionar alguns indivíduos da população para uma solução mais favorável para o problema sem tirar a diversidade da população com um custo menor de tempo. O Objetivo deste trabalho é utilizando o Algoritmo Genético com Operador de Transgenia obter uma programação reativa em tempo de resposta aceitável, visando minimizar o valor de makespan. Resultados experimentais mostraram que algoritmo proposto foi capaz de trazer resultados de makespan melhores que os algoritmos comparados e em um menor tempo de processamento, devido ao direcionamento na busca que operador de transgenia proporciona.

Made available in DSpace on 2016-06-02T19:05:44Z (GMT). No. of bitstreams: 1 3127.pdf: 25890453 bytes, checksum: d4cbd429325861ff182934e97ff94c28 (MD5) Previous issue date: 2009-11-20 / Manufacturing systems with shared resources have been designed to meet the market needs, which require high quality products, low cost and the guarantee of the conditions agreed with the customer. The production scheduling in a manufacturing system is a complex task due to its combinatorial nature. Several studies show the use of search methods, such as Genetic Algorithms (GAs) and Tabu Search (TS), applied to the refinement of the production scheduling problem. The GAs present as disadvantages, the premature convergence, the lack of search intensification mechanisms in promising regions and also the lack of mechanisms which maintain the diversification of the population. In order to make GAs more effective in their search, by avoiding the premature convergence and ensuring the population diversity, some mechanisms are added to them so as to adjust their parameters during the search process, the so called Adaptative Genetic Algorithms (AGAs). However, these mechanisms do not guarantee the search intensification in the promising regions found. On the other hand, the TS presents mechanisms of search intensification and diversification, although its computational time depends on how optimal its initial solution is (solution by which the search process starts). In order to overcome the limitations of the traditional search methods, the Hybrid Algorithms (HAs) have been developed. They consist of the association of one method with another so that one helps the other in its deficiencies . This dissertation proposes the development of a Genetic-Tabu Algorithm (GTA) applied to the problem of the production reactive scheduling in a manufacturing system with shared resources, in order to ensure good compromise between makespan values and feedback time. The TS will be a functionality added to the AG and to the AGA, in other words, it will be a procedure to refine the individual(s) of the initial position and also to refine the individual obtained by the search methods. Tests have been conducted to determine which selection method (roulette or tournament) is more adequate for the definition of the neighborhood structure and also for the definition of the time to apply the mutation operator. Besides, other tests have been conducted by using different ways to calculate the makespan; one of them proposed in this dissertation and the others by Deriz (2007) and by Sanches (2008). / Os sistemas de manufatura com recursos compartilhados têm sido projetados para atender às necessidades do mercado, que demanda produtos que apresentem elevado padrão de qualidade, baixo custo e garantia das condições acordadas com o cliente. A programação da produção é uma tarefa complexa, pois é de natureza combinatória. Várias pesquisas apontam para a utilização de métodos de busca, como Algoritmos Genéticos (AGs) e Buscas Tabu (BTs), aplicados ao refinamento do problema da programação da produção. Os AGs apresentam como desvantagens a convergência prematura, a falta de mecanismos de intensificação da busca nas regiões promissoras e a falta de mecanismos que mantenham a diversificação da população. Para que os AGs possam ser mais efetivos em sua busca, de forma a evitar sua convergência prematura e garantir a diversidade populacional, acrescentam-se aos AGs, mecanismos que ajustam seus parâmetros no decorrer do processo de busca, os chamados Algoritmos Genéticos Adaptativos (AGAs). Esses mecanismos, no entanto, não garantem a intensificação da busca nas regiões promissoras encontradas. A BT, por sua vez, possui mecanismo de intensificação e diversificação da busca, porém o seu tempo computacional depende do quão ótimo é a sua solução inicial (solução pela qual se inicia o processo de busca). A fim de superar as limitações dos métodos de busca tradicionais, desenvolveram-se os Algoritmos Híbridos que agregam (ou associam) um método a outro, de forma que um auxilia o outro em sua deficiência . Neste trabalho, propõe-se o desenvolvimento de um Algoritmo Genético-Tabu (AGT) aplicado ao problema da programação reativa da produção em um sistema de manufatura com recursos compartilhados, a fim de garantir um bom compromisso entre valores de makespan e o tempo de obtenção da resposta. A BT será uma funcionalidade agregada ao AG e ao AGA, ou seja, é um procedimento que realizará o refinamento do(s) indivíduo(s) da população inicial e o refinamento do indivíduo obtido pelos métodos de busca. Realizam-se testes para definir qual método de seleção (roleta ou torneio) é mais bem aplicado ao problema, definição da estrutura da vizinhança e definição do momento de aplicação do operador de mutação. Além disso, foram também realizados testes com as diferentes formas de cálculo do makespan, sendo uma delas proposta neste trabalho e as demais propostas por Deriz (2007) e Sanches (2008).

Les établissements de santé sont confrontés à de nouveaux défis tels que le vieillissement de la population, la hausse des coûts des soins et les progrès rapides des technologies médicales. Les nouvelles politiques de contrôle du budget des soins ont été introduites pour augmenter l'efficacité, réduire les déchets et remodeler le système de santé.Ces établissements cibles présentent des réseaux complexes incluant de ressources humaines,financières, structurelles et technologiques visant à garantir les meilleurs soins. Ces enjeux concernent d’autant plus les services d’urgence engorgés par l’afflux massif des passages, qui doivent fournir des décisions rapides et assurer le dimensionnement de ses ressources afin de réduire les délais d’attente des patients sans compromettre la qualité de soin.L’objectif de cette thèse est de proposer des solutions appropriées aux services d’urgences permettant d’améliorer la prise en charge des patients en termes de temps d’attente. Nous avons commencé par analyser les problématiques de la filière des urgences afin d’engager une démarche d’amélioration. Par la suite, nous avons modélisé le processus de prise en charge des patients au service d’accueil des urgences à l’aide d’un système multi-agent ouvert et dynamique. Le système proposé permet de fournir une aide à la décision sur la planification de l’activité médicale et l’affectation des ressources humaines dans une unité où on se trouve souvent face à une situation d’urgence nécessitant une prise en charge rapide et efficace. Dans ce contexte, nous abordons le problème réactif d’optimisation de l’ordonnancement des opérations de soin et le problème de coordination du personnel médical. Nous nous intéressons au dimensionnement des ressources humaines au SU en adoptant une approche de prise en compte des compétences maîtrisées dans le but de trouver une adéquation avec celles requises par l’activité médicale afin avant tout d’accroitre la qualité, réduire les délais d’attente et permettre de dégager des gains de gestion / Health-care organizations are facing new challenges such as the aging population, the rise of health care costs and the rapid progress of medical technologies. New policies of health care budget control have been introduced to increase efficiency, reduce waste and reshape the entire health care system. Targeted organizations are complex networks of human,financial, structural and technological resources aiming at guarantying best public health care.These issues concern all the more Emergency Departments (ED) congested by the massive influx of passages and which must provide quick decisions and ensure the sizing of its resources to reduce waiting times for patients with out compromising quality of care.The objective of this thesis is to propose appropriate solutions to ED to improve carefor patients in terms of waiting time. We began by analyzing the problems of the emergency department in order to initiate a process of improvement. Subsequently, we modeled the process of care for patients at ED by using an open and dynamic multi-agent system. The proposed system can provide decision support on business planning and allocation of medical resources in a unit where one is often faced with an emergency situation requiring rapid and effective response. In this context, we study the reactive problem for optimizing scheduling of operations care and the coordination problem of medical staff. We take into account the skills mastered by human resources at ED in order to find a match with those required by the medical activity. This approach aims to increase quality, reduce time of expectation and provide pointers gains management