Este trabalho apresenta o problema de programação de operações em máquinas no ambiente no-wait flowshop com o critério de minimização da duração total da programação. Aplicações para o problema no-wait flowshop podem ser encontrados em muitas indústrias, por exemplo, em indústrias de processamento de metais, químicos e farmacêuticos. Neste trabalho, são propostos e avaliados novos métodos heurísticos para o problema, e a superioridade do melhor método proposto é comprovada através uma extensa experimentação computacional. / This work deals with the no-wait flowshop scheduling problem with the objective of minimizing total completion time. Applications of no-wait flowshop can be found in many industries, for example, in steel factories, chemical and pharmaceutical. In this work, we propose evaluate new heuristics methods for the problem. Experimental results show that the best proposed heuristic provides better solutions concerning both the solution quality and computational effort.

Este trabalho apresenta o problema de programação de operações em máquinas no ambiente no-wait flowshop com o critério de minimização da duração total da programação. Aplicações para o problema no-wait flowshop podem ser encontrados em muitas indústrias, por exemplo, em indústrias de processamento de metais, químicos e farmacêuticos. Neste trabalho, são propostos e avaliados novos métodos heurísticos para o problema, e a superioridade do melhor método proposto é comprovada através uma extensa experimentação computacional. / This work deals with the no-wait flowshop scheduling problem with the objective of minimizing total completion time. Applications of no-wait flowshop can be found in many industries, for example, in steel factories, chemical and pharmaceutical. In this work, we propose evaluate new heuristics methods for the problem. Experimental results show that the best proposed heuristic provides better solutions concerning both the solution quality and computational effort.

O problema integrado de programação de produção e dimensionamento de lotes em ambiente fowshop consiste em estabelecer tamanhos de lotes de produção e alocar máquinas para processá-los dentro de um horizonte de planejamento, em uma linha de produção com máquinas dispostas em série. O problema considera que a demanda deve ser atendida sem atrasos, que a capacidade das máquinas deve ser respeitada e que as preparações de máquinas são dependentes da sequência de produção e preservadas entre períodos do horizonte de planejamento. O objetivo é determinar uma programação de produção visando minimizar os custos de preparação de máquina, de produção e de estoque. Um modelo matemático da literatura é apresentado assim como procedimentos para obtenção de limitantes inferiores. Além disso, abordamos o problema por meio de distintas versões da metaheurística Times Assíncronos (A-Teams). Os procedimentos propostos foram comparados com heurísticas da literatura baseadas em Programação Inteira Mista (MIP). As metodologias desenvolvidas e os resultados obtidos são apresentados nesta dissertação / The integrated production scheduling and lot sizing problem in a fowshop environment consists in establishing production lot sizes and alocate machines to process them inside a planning horizon, in a production line with machines arranged in series. The problem considers that demand must be met without backlogging, the capacity of the machines must be respected, machine setup are sequence-dependent and preserved between periods of the planning horizon. The objective is to determine a production schedule to minimize the setup, production and inventory costs. A mathematical model from the literature is presented as well as procedures for obtaining lower bounds. In addition, we propose to address the problem through different versions of the metaheuristic Asynchronous Teams (A-Teams). The procedures were compared with literature heuristics based on Mixed Integer Programming (MIP). The developed methodologies and the obtained results are presented in this dissertation

Ce sujet de thèse concerne de manière générale l'évaluation des performances et l'ordonnancement dans des systèmes de production flexibles et principalement les problèmes d'ordonnancement d'atelier de type Flow-Shop et Flow-Shop hybride. Le problème d'ordonnancement d'un Flow-Shop peut être défini ainsi : un ensemble de N jobs composés chacun de M opérations, doivent passer sur M machines dans le même ordre. Une machine peut exécuter une seule opération à la fois, chaque job ne peut avoir qu'une seule opération en cours de réalisation simultanément et la préemption n'est pas autorisée. Dans le cas des Flow-Shops hybrides, Mk machines identiques sont disponibles à chaque étage k en un ou plusieurs exemplaires. Pour cette étude, notre objectif est toujours de minimiser le temps total d'exécution aussi appelé makespan. Les problèmes d'ordonnancement les plus répandus sont de type Flow-Shop classique où les espaces de stockage entre les machines sont considérées comme infinies. D'autres problèmes sont caractérisés par des capacités de stockage limitées ou nulles qui engendre une seule contrainte de blocage. Cette contrainte peut être un blocage classique (de type RSb) ou particulier (de type RCb ou RCb*). Dans nos travaux de recherche, nous présentons un cas général qui peut être tiré de l'industrie et modélisé sous forme de systèmes de type Flow-Shop et Flow-Shop hybride soumis simultanément à plusieurs types de blocage. Pour résoudre ce genre de problèmes, nous avons étudié dans cette thèse la complexité de ces systèmes et nous avons proposé des méthodes exactes, des méthodes approchées ainsi que des bornes inférieures / This thesis deals mainly with makespan minimization in Flow-Shop and hybrid Flow-Shop scheduling problems where mixed blocking constraints are considered. In Flow-Shop scheduling problem, a set of N jobs must be executed on a set of M machines. All jobs require the same operation order that must be executed according to the same manufacturing process. Each machine can only execute one job at any time. Pre-emptive operation is not authorized in presented work. In case of hybrid Flow-Shop, at any processing stage k, there exist one or more identical machines Mk. Objective function consists in determining best schedule in order to reduce makespan, i.e. time where all operations are completed. The most common scheduling problem is classical flowshop where buffer space capacity between machines is considered as unlimited. Other problems are characterized by the fact that the storage capacity is limited or null and which generates one blocking constraint. This constraint can be a classical blocking (RSb) or particular blocking (RCb or RCb*). In our works, we present a general case which can be derived from industry and modeled as Flow-Shop and hybrid Flow-Shop systems subject simultaneously to different blocking. To solve these problems, we studied in this thesis complexity of these systems and we proposed exact methods, approached methods and lower bounds

Dans cette thèse, nous avons traité les problèmes d'ordonnancement d'ateliers de type flow- shop hybride à deux étages avec machines à traitement par batches sur le second étage et compatibilité entre les tâches. Les durées opératoires des tâches sont données par des intervalles, et les tâches sont dites compatibles si elles partagent une même durée d'exécution. Pour le problème de minimisation de la date de fin d'ordonnancement de ce type d'atelier, nous avons développé 6 heuristiques à performances garanties. D'après les expériences réalisées, ces heuristiques sont efficaces sur de grandes instances. Pour les petites instances, nous avons présenté deux méthodes exactes de type procédures par séparation évaluation qui permettent de résoudre des instances de 20 tâches. Nous avons également développé un schéma d'approximation polynomial (PTAS) utilisable lorsque les durées d'exécution sur le premier étage sont identiques. En complément de ces travaux, nous avons également étudié d'autres problèmes de minimisation de critères réguliers sur une machine à traitement par batches. Nous avons développé des algorithmes de programmation dynamiques pseudo-polynomiaux pour les problèmes de minimisation de la somme des dates de fin d'exécution et pour les problèmes avec dates de fin souhaitées. Afin de compléter ces résultats de complexité, nous avons montré la NP-complétude des problèmes avec dates de fin souhaitées.

This thesis studies Production Scheduling in a multistage hybrid flowshop facility. It first states the general Production Planning and Scheduling problem and highlights some drawbacks of classical solutions. A theoretical decomposition-based approach is introduced whose main issue is to overcome non-efficient capacity utilization. By using Branch and Bound methods, an in-depth analysis of the scheduling part of the system is then carried out throughout the study and development of upper and lower bounds as well as branching schemes. Already-existing and new heuristics are presented and compared on different shop floor configurations. Five different heuristic approaches are studied. By scheduling the HFS one stage at a time the first approach uses different stage sequencing orders. The second and third approaches are mainly list heuristics. The second approach uses ideas derived from the multistage classical flowshop with a single machine per stage, while the third approach uses classical dispatching priority rules. The fourth and fifth approaches, respectively, use random scheduling and local search techniques. Statistical analysis is carried out in order to compare the heuristics and to select the best of them for each shop configuration. Already-existing and new lower bounds on the single stage subproblem are also presented and compared. Three new lower bounds are developed: a dual heuristic based bound, a partially preemptive bound and a heuristic for the so-called subset bound. Some of these lower bounds use a network flow algorithm. A new version of the “Preflow Push” algorithm which runs faster than the original one is presented. The best lower bounds are selected based on numerical tests. Two branch and bound algorithms are presented, an improved version of the sequence enumeration method and a generalization of the so-called interval branching method, along with several bounding strategies. Based on the upper and lower bound studies, several branch and bound algorithms are presented and compared using numerical tests on different shop floor configurations. Eventually, an Object Model for Scheduling Algorithm Implementations (OMSAI), that has been used for the computer implementation of the developed algorithms, is presented.

This thesis studies Production Scheduling in a multistage hybrid flowshop facility. It first states the general Production Planning and Scheduling problem and highlights some drawbacks of classical solutions. A theoretical decomposition-based approach is introduced whose main issue is to overcome non-efficient capacity utilization. By using Branch and Bound methods, an in-depth analysis of the scheduling part of the system is then carried out throughout the study and development of upper and lower bounds as well as branching schemes. Already-existing and new heuristics are presented and compared on different shop floor configurations. Five different heuristic approaches are studied. By scheduling the HFS one stage at a time the first approach uses different stage sequencing orders. The second and third approaches are mainly list heuristics. The second approach uses ideas derived from the multistage classical flowshop with a single machine per stage, while the third approach uses classical dispatching priority rules. The fourth and fifth approaches, respectively, use random scheduling and local search techniques. Statistical analysis is carried out in order to compare the heuristics and to select the best of them for each shop configuration. Already-existing and new lower bounds on the single stage subproblem are also presented and compared. Three new lower bounds are developed: a dual heuristic based bound, a partially preemptive bound and a heuristic for the so-called subset bound. Some of these lower bounds use a network flow algorithm. A new version of the “Preflow Push” algorithm which runs faster than the original one is presented. The best lower bounds are selected based on numerical tests. Two branch and bound algorithms are presented, an improved version of the sequence enumeration method and a generalization of the so-called interval branching method, along with several bounding strategies. Based on the upper and lower bound studies, several branch and bound algorithms are presented and compared using numerical tests on different shop floor configurations. Eventually, an Object Model for Scheduling Algorithm Implementations (OMSAI), that has been used for the computer implementation of the developed algorithms, is presented.

This work should serve as a source of information on the issue of production scheduling. The work is particularly focused on the relatively new terms in optimization of processing of production batches area, such as flowshop and its modifications in the form of so-called hybrid flowshop. The work is divided into five chapters. The first chapter consists of an introduction. In the second chapter I mention the theory of scheduling, the third part deals with the history of flowshop and in the fourth part I check the functionality of new models on real data. In conclusion I summarize the contents of work, comment resulting calculations and deliver the practical usage of flowshop.

Organizações eficientes são aquelas que conseguem manter equilibradas as vertentes de qualidade, custo e tempo. Em relação ao último, existem várias etapas da cadeia produtiva nas quais o tempo deve ser monitorado. Quando a programação da produção nas indústrias não é priorizado, pode-se incorrer vários efeitos negativos. Um deles, é o atraso em relação à data de entrega, no qual a corporação pode sofrer penalidades financeiras, além de uma exposição negativa para a marca, a qual pode ter sua credibilidade contestada. Dessa forma, essa pesquisa tem por objetivo propor métodos construtivos, que minimize a medida de desempenho total tardiness (atraso total). Para aproximar o método à realidade vivenciada pelas indústrias, será considerada a restrição de manutenção preventiva. Além disso, o ambiente de estudo será o contexto de no-wait flowshop, no qual as tarefas são processados continuamente e sem que haja interrupções entre uma operação e outra de uma mesma tarefa. Além da proposição de métodos construtivos para a resolução do problema, apresenta-se uma metaheurística como forma de demostrar como pode-se aprimorar os resultados gerado pelos métodos construtivos. Experimentações computacionais foram elaboradas e realizadas para comparação dos algoritmos. Dentre as heurísticas construtivas a que apresentou melhor desempenho foi a \"EDD + NEH + LS1 + LS2\'\', na qual utiliza uma lógica de inserção. A metaheurística proposta é baseada no procedimento IG (iterated greedy), sendo que há melhora de resultado em relação as heurísticas construtivas. Assim, espera-se que essa pesquisa possa ser utilizada e aplicada pela indústria de manufatura para aumentar a efetividade da programação da produção. / Efficient organizations are those that manage to keep the quality, cost and time strands balanced. With respect to the variable time, there are several stages of the production chain in which it must be monitored. When scheduling in companies is not prioritized, several negative effects incur. One of them is the delay in relation to the due date, for which the corporation can suffer financial penalties, in addition to a negative exposure to the brand, which may have its credibility challenged. Therefore, this research aims to propose constructive methods, which minimizes the performance criterion of total tardiness. In order to approximate the method to the reality of the industries, preventive maintenance constraints will be considered. And the environment of the study will be the no-wait flowshop, in which jobs are processed continuously and without interruptions between one operation and another of the same job. In addition to proposing constructive methods to solve the problem, a metaheuristic is presented as a way of demonstrating how to improve the results generated by the constructive methods. Computational experiments were elaborated and performed for comparison of the algorithms. Among the constructive heuristics that presented the best performance was \"EDD + NEH + LS1 + LS2\", in which it uses an insertion logic. The proposed metaheuristic is based on the IG (iterated greedy) procedure, and there is an improvement of the result in relation to the constructive heuristics. Thus, it is expected that this research can be used and applied by the manufacturing industry to increase the effectiveness of scheduling.

Em um contexto industrial, a programação da produção tem como objetivo alocar recursos para operações de forma a aumentar a eficiência operacional do processo de fabricação. Esta programação pode ser modelada na forma de problemas de sequenciamento de tarefas, que são resolvidos visando minimizar um determinado critério de desempenho. A aplicação de métodos exatos nestes problemas possibilita encontrar a solução ótima, tanto para aplicação direta como para a validação de métodos heurísticos e metaheurísticas. Entretanto, a literatura mostra que os métodos exatos, tanto a resolução do problema pela modelagem em programação linear-inteira mista como o branch-and-bound, têm sua aplicação restrita à problemas de menores tamanhos. O objetivo deste trabalho é propor novas formulações de limitantes inferiores para a aplicação do branch-and-bound em problemas de flowshop permutacional visando aumentar sua eficiência e aplicabilidade. Os limitantes propostos são avaliados em problemas de flowshop permutacional com tempos de setup dependente da sequência, tendo como critérios de desempenho o tempo de fluxo total e o atraso total. A avaliação da aplicabilidade de cada limitante é feita através do número de nós explorados e o tempo computacional gasto pelo branch-and-bound para resolver problemas de diversos tamanhos. / In an industrial context, production sequencing aims at allocating resources for job processing while increasing manufacturing efficiency. This task can be modelled in the form of scheduling problems, which are solved by minimizing a pre-determined performance criterion. The use of exact methods allows the optimal solution to be found, which can be applied directly in the manufacturing shop or used to validate heuristic and metaheuristic methods. However, the literature shows that MILP and branch-and-bound, both exact methods, are restrained to small-sized scheduling problems. The aim of this project is to propose new lower bound formulations to be used in the branch-and-bound method for permutational flowshop probems, in order to extend its efficiency and applicability. The proposed bounds are tested in permutational flowshop problems with sequence dependent setup times, and using as performance criteria the total flow time and the total tardiness. The evaluation of each lower bounds applicability is done considering the number of explored nodes and the required computational time for the branch-and-bound to solve problem instances of different sizes.