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.

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.

Este trabalho aborda o problema de no-wait flowshop em um ambiente com custos de setup apartados dos tempos de processamento, são investigados os casos de setups dependentes e independentes da seqüência para makespan e total flowtime. Diversas aplicações práticas podem ser modeladas sob estas suposições, dentre elas destacamos a indústria química e alimentícia. É proposta uma metaheurística evolutiva baseada em algoritmo genético e clustering search e seus resultados são comparados com os métodos de Brown et al (2004), França et al (2006) e Ruiz e Allahverdi (2007) através dos bancos de dados de Ruiz e Stützle (2008) e Ruiz e Allahverdi (2007). Os métodos são avaliados segundo o percentual de sucesso e desvio relativo médio. Os resultados obtidos demonstram a superioridade do método proposto para problemas de grande porte. / This work intends to research the no-wait flowshop scheduling problem with setup times separated from the processing costs; the both cases where the sequence is dependent and independent are targeted for makespan and total flowtime. There are numerous practical situations that can be modeled under these assumptions, such as, chemical industry, food processing, etc. A hybrid metaheuristic method based on a genetic algorithm and clustering search is proposed and its results are compared to the methods of Brown et al (2004), França et al (2006) e Ruiz e Allahverdi (2007) using the data base from Ruiz e Stützle (2008) and Ruiz e Allahverdi (2007). The methods are evaluated as regarding the success rate and average relative deviation. The results show that the proposed method delivers better solutions for problems with higher complexity.

Este trabalho aborda o problema de no-wait flowshop em um ambiente com custos de setup apartados dos tempos de processamento, são investigados os casos de setups dependentes e independentes da seqüência para makespan e total flowtime. Diversas aplicações práticas podem ser modeladas sob estas suposições, dentre elas destacamos a indústria química e alimentícia. É proposta uma metaheurística evolutiva baseada em algoritmo genético e clustering search e seus resultados são comparados com os métodos de Brown et al (2004), França et al (2006) e Ruiz e Allahverdi (2007) através dos bancos de dados de Ruiz e Stützle (2008) e Ruiz e Allahverdi (2007). Os métodos são avaliados segundo o percentual de sucesso e desvio relativo médio. Os resultados obtidos demonstram a superioridade do método proposto para problemas de grande porte. / This work intends to research the no-wait flowshop scheduling problem with setup times separated from the processing costs; the both cases where the sequence is dependent and independent are targeted for makespan and total flowtime. There are numerous practical situations that can be modeled under these assumptions, such as, chemical industry, food processing, etc. A hybrid metaheuristic method based on a genetic algorithm and clustering search is proposed and its results are compared to the methods of Brown et al (2004), França et al (2006) e Ruiz e Allahverdi (2007) using the data base from Ruiz e Stützle (2008) and Ruiz e Allahverdi (2007). The methods are evaluated as regarding the success rate and average relative deviation. The results show that the proposed method delivers better solutions for problems with higher complexity.

The problem of finding a schedule with the lowest makespan in the class of all flowtime-optimal schedules for parallel identical machines is an NP-hard problem. Several approximation algorithms have been suggested for this problem. We focus on algorithms that are fast and easy to implement, rather than on more involved algorithms that might provide tighter approximation bounds. A set of approaches for proving conjectured bounds on performance ratios for such algorithms is outlined. These approaches are used to examine Coffman and Sethi's conjecture for a worst-case bound on the ratio of the makespan of the schedule generated by the LD algorithm to the makespan of the optimal schedule. A significant reduction is achieved in the size of a hypothesised minimal counterexample to this conjecture.

The problem of finding a schedule with the lowest makespan in the class of all flowtime-optimal schedules for parallel identical machines is an NP-hard problem. Several approximation algorithms have been suggested for this problem. We focus on algorithms that are fast and easy to implement, rather than on more involved algorithms that might provide tighter approximation bounds. A set of approaches for proving conjectured bounds on performance ratios for such algorithms is outlined. These approaches are used to examine Coffman and Sethi's conjecture for a worst-case bound on the ratio of the makespan of the schedule generated by the LD algorithm to the makespan of the optimal schedule. A significant reduction is achieved in the size of a hypothesised minimal counterexample to this conjecture.

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.

Balancing trade-offs between production cost and holding cost is critical for production and operations management. Utilization of an operating room affects production cost, which relates to makespan, and patient flowtime affects holding cost. There are trade-offs between two objectives, to minimize makespan and to minimize flowtime. However, most existing constructive heuristics focus only on single-objective optimization. In the current literature, NEH is the best constructive heuristic to minimize makespan, and LR heuristic is the best to minimize flowtime. In this thesis, we propose a current and future deviation (CFD) heuristic to balance trade-offs between makespan and flowtime minimizations. Based on 5400 randomly generated instances and 120 instances in Taillard’s benchmarks, our CFD heuristic outperforms NEH and LR heuristics on trade-off balancing, and achieves the most stable performances from the perspective of statistical process control.

This study considers bicriteria approaches to the minimum cost network flow problem and a rescheduling problem where those approaches find their applications. For the bicriteria integer minimum cost network flow problem, we generate all efficient solutions in two phases. The first phase generates the extreme supported efficient points that are the extreme points of the objective space of the continuous bicriteria network flow problem. In the second phase, we generate the nonextreme supported and unsupported efficient points by Integer Programming Based approaches. Our rescheduling problem considers parallel unrelated machine environments. The criteria are the total flow time as an efficiency measure and the total reassignment cost as a stability measure. We show that the problems that address linear functions of the two criteria can be represented by bicriteria network flow models. To generate all efficient solutions, we use a Classical Approach that is based on the optimal solutions of the singly constrained network flow problem and provide a Branch and Bound approach that starts with extreme supported efficient set and uses powerful bounds. To find an optimal solution to any nonlinear function of the two criteria, we provide a Branch and Bound approach and an Integer Programming Based approach that eliminates some portions of the efficient set that cannot provide improved solutions. We contribute both to the network flow and scheduling literature by proposing algorithms to the bicriteria network flow models and applying them to a rescheduling problem that is bicriteria in nature. The results of our extensive computations with up to 100 jobs and 12 machines have revealed that, the Branch and Bound algorithm finds the efficient set in less computational effort compared to the classical approach. In minimizing a nonlinear function of the two criteria both IP Based approach and Branch and Bound algorithm perform quite satisfactory.

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.