O problema de escalonamento num flow shop (ou flow shop scheduling problem, FSSP) é um modelo de sistemas de produção muito comum que é bem estudado na literatura. No entanto, quase toda a literatura foca-se em escalonamentos permutacionais, desconsiderando soluções ótimas e quase ótimas que são escalonamentos não-permutacionais. Além disso, a prática comum padroniza os tempos de processamento de cada operação, mesmo que estes tempos variem dependendo das diferentes capacidades dos operadores das máquinas, cuja diversidade deve ser considerada no processo de escalonamento quando seja significativa, e.g., em centros de emprego para deficientes (CEDs). Nesta tese, propomos métodos para resolver o FSSP não-permutacional, usando o mesmo tempo e esforço que os métodos do estado da arte usam para o FSSP permutacional, e produzindo escalonamentos não-permutacionais com melhor qualidade do que escalonamentos permutacionais e não-permutacionais produzidos por métodos do estado da arte. Também propomos métodos para resolver o problema combinado de designação de trabalhadores heterogêneos e escalonamento de tarefas num flow shop (ou heterogeneous workforce assignment and flow shop scheduling problem, Het-FSSP), produzindo soluções que compensam as diferentes capacidades e deficiências dos trabalhadores com pequenas perdas nos objetivos da produção. Além do mais, a designação de trabalhadores heterogêneos pode ser integrada em outros problemas de escalonamento, como fizemos com o problema combinado de designação de trabalhadores heterogêneos e escalonamento de tarefas num job shop (ou heterogeneous workforce assignment and job shop scheduling problem, Het-JSSP). / The flow shop scheduling problem (or FSSP) is a very common model of production systems that is well studied in the literature. However, almost all the literature focuses on the permutation FSSP, disregarding optimal and near optimal solutions that are non-permutation schedules. Besides, common practice standardizes the processing times of each operation, even when those times may vary depending on different capabilities of the machine operators, whose diversity must be considered in the scheduling process when it is significant, e.g., in Sheltered Work centers for Disabled (SWDs). In this thesis, we propose methods to solve the non-permutation FSSP, using the same time and effort as state-of-the-art methods for the permutation FSSP, and producing non-permutation schedules with better quality than permutation and non-permutation schedules produced by state-of-the-art methods. We also propose methods to solve the combined heterogeneous workforce assignment and flow shop scheduling problem (or Het-FSSP), producing solutions that compensate the different capabilities and disabilities of the workers with minor or null losses in the productivity objectives. Moreover, the heterogeneous workforce assignment may be integrated into other shop scheduling models, as we did with the heterogeneous workforce assignment and job shop scheduling problem (or Het-JSSP) with similar results.

No description available.

In this dissertation, we investigate the use of lot streaming in a two-stage assembly system and a two-stage hybrid flow shop in order to improve system performance. Lot streaming accelerates the flow of a production lot through a production process by splitting it into sublots, and then, processing these sublots in an overlapping fashion over the machines, thereby reducing work-in-process and cycle-time. Traditionally, lot streaming has been applied to problems in various flow shop machine configurations. It has also been applied to machine environments of job shop, open shop, and parallel machines. Its application to assembly system is relatively new. The two-stage assembly system that we consider consists of multiple suppliers at Stage 1 with each supplier producing one type of a subassembly (or a component), and one or more assembly locations at Stage 2, where the subassemblies are then put together. Lot-attached and sublot-attached setup time and cost are encountered on the machines at both the stages, and sublot-attached time and cost are encountered for the transfer of sublots from Stage 1 to Stage 2. Mass customization is an example of such a system in which the final assembly of a product is postponed to capture specific customer demands. Dell Computer constitutes a real-life example of this system. A customer picks his/her computer processor, memory, storage, and other equipment, on Dell's web site. Dell's supply chain is configured to obtain subassemblies from suppliers (stage 1), and then, to assemble the requisite systems in different market areas (stage 2). This enables a reduction in operating cost while improving responsiveness to customers. The problem that we address is as follows: Given a maximum number of sublots of each lot, determine the number of sublots to use (assuming equal sublot sizes), and also, the sequence in which to process the lots, in order to minimize two criteria, namely, makespan, total cost. We propose two column generation-based methods that rely on different decomposition schemes. The results of our computational investigation conducted by using randomly generated data sets reveal that the proposed column generation methods obtain solutions in a few seconds of CPU time while the direct solution by CPLEX of a mixed integer programming model of the problem requires much larger CPU times. For the hybrid flow shop lot streaming problem, the machine configuration that we consider consists of one machine at Stage 1 and two machines at Stage 2 (designated as 1+2 system). A single lot is to be processed in the system, and the objective is to minimize the makespan. A removal time is associated with each sublot at Stage 1. We present a mixed integer programming model for this problem to determine optimal number of sublots and sublot sizes. First, we consider the case of a given number of sublots for which we develop closed-form expressions to obtain optimal, continuous sublot sizes. Then, we consider determination of optimal number of sublots in addition to their sizes. We develop an upper bound on optimal number of sublots, and use a simple search procedure in conjunction with the closed-form expressions for sublot sizes to obtain an optimal solution. We also consider the problem of determining integer sublot sizes, and propose a heuristic method that directly solves the mixed integer programming model after having fixed values of appropriate variables. The results of our numerical experimentation reveal the efficacy of the proposed method to obtain optimal, continuous sublot sizes, and also, that of the proposed heuristic method to obtain integer sublot sizes, which are within 0.2% of optimal solutions for the testbed of data used, each obtained within a few seconds of CPU time. The last problem that we address is an extension of the single-lot lot streaming problem for a $1+2$ hybrid flow shop considered above to the case of multiple lots, where each lot contains items of a unique product type. We consider two objectives: minimize makespan, and minimize the sum of the completion times for all the lots. The consideration of multiple lots introduces a complicating issue of sequencing the lots. We use the results derived for the single-lot problem and develop effective heuristic methods for this problem. The results of our computational investigation on the use of different heuristic methods reveal their efficacy in solving this problem. / Ph. D.

Este trabalho trata do problema de programação de operações no ambiente flow shop com máquinas múltiplas, com seus tempos de preparação (setup) assimétricos e dependentes da seqüência de processamento das tarefas. Este ambiente de produção é comum em indústrias gráficas, químicas, têxteis, de papel e de tinta, caracterizadas por sistemas com amplo mix de produtos. Qualquer processo produtivo requer um gerenciamento eficaz por meio do Planejamento e Controle da Produção (PCP). Esta atividade inclui a programação da produção, ou seja, a alocação de recursos para a execução de tarefas em uma base de tempo. A atividade de programação é uma das tarefas mais complexas no gerenciamento de produção, pois há a necessidade de lidar com diversos tipos diferentes de recursos e atividades simultaneamente. Além disso, o número de soluções possíveis cresce exponencialmente em várias dimensões, de acordo com a quantidade de tarefas, operações ou máquinas, conferindo uma natureza combinatorial ao problema. No ambiente estudado neste trabalho as operações de cada tarefa são executadas em múltiplos estágios de produção, podendo variar a quantidade de máquinas em cada um deles. Cada operação é processada por apenas uma máquina em cada estágio. Os tempos de preparação das máquinas possuem uma variabilidade relevante em função da ordem de execução das tarefas nas máquinas. A função-objetivo considerada é a minimização da duração total da programação (makespan). Foram desenvolvidos quatro métodos heurísticos construtivos com base em algoritmos reportados na literatura para solução de problemas flow shop permutacional e máquinas paralelas no ambiente cujo tempo de setup é dependente da seqüência. Como não foram encontrados na literatura métodos para programação no ambiente tratado neste trabalho, os algoritmos construídos foram comparados entre si. O foco da pesquisa foi o estudo da influência da relação entre as ordens de grandeza dos tempos de processamento e de setup em cada método de solução. Os resultados obtidos na experimentação computacional foram analisados e discutidos com base na porcentagem de sucesso, desvio relativo (%), desvio-padrão do desvio relativo e tempo médio de computação / This work adressess the hybrid flow shop scheduling problem with asymmetric sequence dependent setup times. This environment of production system is common in graphical, chemical, fabric, paper and ink industries. It’s characterized by systems with large mix of products. Any productive process requires an efficient management by means of Production Planning and Control. This activity includes scheduling, i.e., the resources allocation for the execution of jobs in a time base. Scheduling is one of the tasks most complex in production management, since it deals simultaneously with different types of resources and activities. Moreover, the number of possible solutions grows exponentially in some dimensions, in accordance with the number of jobs, operations or machines, conferring a combinatorial nature to the problem. In the environment studied in this work, the operations of each job are processed in multiple production stages. The number of machines in each stage can be different. Each operation is processed by only one machine in each stage. The setup times have a significant variability in function of the sequence of job processing on the machines. The objective is minimizing the total time to complete the schedule (makespan). Four constructive heuristic methods were developed on the basis of algorithms reported in the literature for solving permutation flow shop and parallel machine problems with sequence dependent setup times. The proposed heuristic methods have been compared between themselves, since no constructive heuristics have been found in the literature for the scheduling problem considered in this work. The focus of the research was the study of the influence of the relations among the range of the times processing and setup times in each method. The statistics used in order to evaluate the heuristic performances were the percentage of success (in finding the best solution), relative deviation, standard deviation of relative deviation and average computation time. Results from computational experience are discussed

Os processos industriais de produção exigem uma programação da produção efetiva. Essa atividade consiste da alocação dos recursos produtivos, a fim de executar tarefas determinadas por um período de tempo definido. Programar a produção é uma das atividades mais complexas do Planejamento da Produção, pois existem diferentes tipos de recursos a serem administrados simultaneamente. E também a quantidade de possíveis soluções aumenta exponencialmente com o aumento da quantidade de tarefas e máquinas presentes no sistema. A proposta deste trabalho é apresentar um método heurístico construtivo para a solução de problemas flow shop permutacional. A função-objetivo utilizada é a minimização do tempo total da programação (makespan). O algoritmo foi desenvolvido com base no melhor algoritmo construtivo presente na literatura, e os resultados obtidos são discutidos e analisados com base na porcentagem de sucesso, desvio relativo médio e tempo médio de computação. / Industrial productive processes demand an effective production scheduling. These activities consist in allocating the productive resources in order to execute determined jobs for a established period of time. Scheduling the production is one of the most complex activities involved in Planning the Production because there are different kinds of resources to be managed simultaneously. Furthermore, the amounts of feasible solutions increase exponentially as the number of jobs and machines in large systems. This dissertation presents a constructive heuristic method to solve the permutational flow shop problem. The evaluation criterion is the total production elapsed time (makespan). The developed algorithm was based on the best algorithm found in the literature, the results are analysed based on the success rate, mean relative deviation and computing time.

A teoria de programação da produção preocupa-se em fornecer diretrizes e métodos eficientes para a utilização dos recursos nas atividades produtivas. Este trabalho investiga o problema de programação da produção em ambientes flow shop com máquinas múltiplas e tempos de preparação das máquinas assimétricos e dependentes da seqüência de execução das tarefas. A atividade de programação da produção constitui uma das várias funções executadas pelo planejamento e controle da produção, que tem como objetivo comandar e gerenciar o processo produtivo, e caracteriza uma das atividades mais complexas no gerenciamento dos sistemas produtivos. A programação da produção preocupa-se com a alocação de recursos sobre o tempo para executar um conjunto de tarefas. No ambiente estudado neste trabalho as operações de cada tarefa são executadas em múltiplos estágios de produção, podendo variar a quantidade de máquinas em cada um deles. Cada operação é processada por apenas uma máquina em cada estágio. Os tempos de preparação das máquinas possuem uma variabilidade relevante em função da ordem de execução das tarefas nas mesmas. A função-objetivo considerada é a minimização do tempo médio de fluxo. Foram desenvolvidos quatro métodos heurísticos construtivos com base em algoritmos reportados na literatura para solução do problema flow shop permutacional e máquinas paralelas cujo tempo de setup é dependente da seqüência de execução das tarefas. Como não foram encontrados na literatura métodos de solução para o problema investigado neste trabalho, os algoritmos propostos foram comparados entre si. Foi efetuado um estudo da influência da relação entre as ordens de grandeza dos tempos de processamento das tarefas e do setup das máquinas em cada método de solução. Os resultados obtidos na experimentação computacional foram analisados e discutidos com base na porcentagem de sucesso, desvio relativo, desvio-padrão do desvio relativo e tempo médio de computação. / Scheduling theory attempts to provide guidelines and efficient methods to the use of the resources in the productive activities. This study investigates the hybrid flow shop problem with asymmetric sequence dependent setup times. The activity of production scheduling constitute is one of the several functions carried by production planning and control, which has as the objective command and management the production system, and characterize is one of the tasks most complex in production management. This activity of the scheduling aims within the allocation of the resources for the execution of jobs in a time base. In the environment studied in this work, the operations of each job are processed in multiple production stages. The number of machines in each stage can be different. Each operation is processed by only one machine in each stage. The setup times have a significant variability in function of the sequence of job processing on the machines. The objective is minimizing the mean flow time. Four constructive heuristic methods were proposed on the basis of algorithms reported in the literature for solving permutation flow shop and parallel machine problems with sequence dependent setup times. The proposed heuristic methods will have compared between themselves, since no constructive heuristics have been found in the literature for the scheduling problem considered in this work. It was carried out the study of the influence of the relations among the range of the times processing and setup times in each method. The statistics used in order to evaluate the heuristic performances were the percentage of success (in finding the best solution), relative deviation, standard deviation of relative deviation and average computation time. Results from computational experience are discussed.

Este trabalho aborda o problema de programação de tarefas, a partir de um caso específico, conhecido como Flow Shop com buffer zero. O problema consiste em programar n tarefas em m máquinas no ambiente Flow Shop permutacional. Com o aumento do nível de exigência dos clientes, pesquisas que buscam o atendimento das datas de entrega têm se tornado de extrema importância em ambientes de manufatura. Este trabalho analisa o problema de minimização do atraso total no ambiente Flow Shop onde não existe a possibilidade de armazenagem das tarefas entre estágios de produção sucessivos (buffer zero), tendo como consequência o bloqueio de máquinas. A Heurística Evolutiva Clustering Search foi proposta e analisada para a obtenção de soluções de altíssima qualidade para o problema. Finalmente, uma extensa experimentação computacional foi realizada. Quando comparado com o melhor método reportado na literatura, o método proposto apresentou qualidade superior. / This work deals with the Flow Shop scheduling problem. The objective is scheduling n jobs on m machines in the Permutation Flow Shop environment. With the increasing customer demand level, researches that aims the attendance of due dates have become extremely important in manufacturing process. This work studies the total tardiness minimization problem in the flow shop environment where there is no buffer storage between machines, resulting in the machine block. The Heuristic Evolutionary Clustering Search was proposed and analyzed to obtain high quality solutions to the problem. Finally, an extensive computational experiment was performed. When compared to the best method reported in the literature, the proposed method showed high quality.

Este trabalho é direcionado ao problema de Programação de Operações No-Idle Flow Shop Permutacional. Uma propriedade do problema, oriunda de estudo sobre a sua característica, é apresentada e utilizada para o desenvolvimento de um novo método heurístico construtivo, com o objetivo de minimizar a Duração Total da Programação (makespan). O novo método é comparado com os melhores heurísticos construtivos reportados na literatura, conhecidos por IG, KK e FRB3. Os resultados da experimentação computacional mostraram o melhor desempenho do método proposto, denominado BHBN, para os problemas testes de Ruiz et al. (2008) e Taillard (1993), quanto à qualidade da solução, apresentando também eficiência computacional. / This work is addressed to the No-Idle Flow Shop Sequencing problem. As a result of an investigation on the problem characteristics it is presented a property of this scheduling problem, which is used for the development of a new constructive heuristic with the objective of minimizing the Total Time to complete the schedule (makespan). The new method is compared with the best constructive heuristics reported in the literature, named IG, KK and FRB3. Results from computational experience showed the best performance of the proposed method, denoted by BHBN, for the instances of Ruiz et al. (2008) and Taillard (1993), as to the quality of the solution, and also computational efficiency.

Este trabalho apresenta o problema de programação de operações em máquinas no ambiente no-wait flow shop com critério de minimização do tempo total de fluxo (total flowtime). Aplicações para o problema no-wait flow shop podem ser encontradas em muitas indústrias. Por exemplo, em indústrias de metais, o metal aquecido deve seguir por uma série de operações antes de ser resfriado, com a finalidade de prevenir defeitos na sua composição. Um segundo exemplo é a indústria de plásticos que requer uma série de processos, um imediatamente após o outro, a fim de prevenir a degradação. Situações similares também são encontradas em outros processos industriais, como químicos e farmacêuticos. Neste trabalho, são propostos e avaliados novos métodos heurísticos para o problema, tão bons quanto os já existentes na literatura. Os métodos são avaliados através de um grande número de problemas de vários tamanhos. Os resultados da experimentação computacional também são analisados. / This work deals with the no-wait flow shop scheduling problem with the objective of minimizing total flowtime. Applications of no-wait flow shop can be found in many industries. For example, in steel factories, the heated metal continuously goes through a sequence of operations before it is allowed to cool in order to prevent defects in the composition of the steel. A second example is a plastic product that requires a series of processes to immediately follow on another in order to prevent degradation. Similar situations arise in other process industries such as the chemical and pharmaceutical. In this work, we propose evaluate new heuristics methods for the problem, as well as the existing in the literature. The methods are evaluated over a large number of problems of various sizes. The results of the computational experience are also reported.

Neste trabalho é abordado o problema da programação da produção em ambiente flow shop permutacional, tendo como objetivo analisar dois critérios de otimização: o primeiro critério é a minimização do tempo total de programação da produção (makespan), e o segundo é a minimização do tempo total de fluxo (total flowtime). Estes objetivos são relevantes para a dinâmica do ambiente de produção, porque enquanto que a minimização do makespan tende a melhorar a utilização dos recursos produtivos, a minimização do total flowtime conduz a um menor estoque em processo. Por este motivo, estes problemas tem atraído a atenção de vários pesquisadores ao longo dos anos. Neste sentido, será realizado uma revisão do estado da arte e novas heurísticas construtivas serão propostas para gerarem soluções de qualidade para ambos os problemas estudados. Com este objetivo, uma extensa experimentação computacional foi realizada para fins de comparação e avaliação dos métodos propostos com os melhores métodos heurísticos reportados da literatura. / This work addresses the scheduling problem in permutation flow shop environment, having as objective to analyze two optimization criteria: the first criterion is to minimize the makespan, and the second is to minimize the total flow time. These objectives are relevant to the dynamics of the production environment, because while minimizing the makespan tends to improve the resources utilization, minimizing the total flowtime leads to a lower in-process inventory. For this reason, these problems have attracted the attention of many researchers over the years. In this regard, will be performed a review of the state of the art and new constructive heuristics will be proposed to generate quality solutions for both problems in consideration. For this purpose, an extensive computational experiment was performed for comparison and evaluation of the proposed heuristics with the best heuristic methods reported in the literature.