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 dedica-se ao problema de programação em flow shop permutacional com tempos de setup separados dos tempos de processamento e independentes da seqüência de execução das tarefas com o objetivo de minimizar a duração total da programação (Makespan). Por intermédio de investigações realizadas sobre as características estruturais do problema de programação e sua solução, uma propriedade deste problema é apresentada. Esta propriedade, denominada \"Propriedade LBY\", considerando quaisquer duas tarefas adjacentes Ju e Jv (Ju imediatamente precede Jv) independentemente de suas posições na seqüência de tarefas, fornece, um limitante inferior do tempo de espera para a tarefa Jv entre o fim do seu processamento na máquina Mk e o início do seu processamento na máquina seguinte. Dois novos métodos heurísticos são desenvolvidos, com base na propriedade apresentada e no procedimento de inserção de tarefas dos conhecidos métodos N&M e NEH: um construtivo, denominado BMc; e, um melhorativo, denominado BMm. Os métodos heurísticos propostos são comparados com os métodos heurísticos melhorativos de Cao; Bedworth (1992) e Rajendran; Ziegler (1997), através de um grande número de problemas gerados aleatoriamente. Os tempos de processamento são distribuídos no intervalo [1, 99] e os tempos de setup nos intervalos de [1, 49], [1, 99], [51, 149] e [101, 199]. Os métodos são avaliados quanto à porcentagem de sucesso em obter a melhor solução, ao desvio relativo médio e o tempo médio de computação. Os resultados da experimentação computacional mostram a qualidade do método construtivo BMc e a melhor performance do método melhorativo BMm. Estes resultados são apresentados e discutidos. / This work addresses the permutation flow shop scheduling problem with separated, non-batch, and sequence-independent setup times with the objective of minimizing the total time to complete the schedule (Makespan). Following an investigation of problem structural characteristics and your solution a property of this scheduling problem is presented. This property, denoted by \"Property LBY\", given any two adjacent jobs Ju e Jv (Ju immediately precedes Jv), regardless of their position in the sequence of jobs, provides an lower bound of the waiting time for job Jv between the end of its operations on the machine Mk and the beginning on machine M(k+1). Two news heuristics methods are development, on the basis of the presented property and in the job insertion procedure of the known methods named N&M and NEH: one constructive, denote by BMc; and, one improvement, denote by BMm. The proposed heuristics methods are compared with the improvement heuristics methods of Cao; Bedworth (1992) and Rajendran; Ziegler (1997), by a large number of randomly generated problems. The processing time are sampled from a distribution ranging from [1, 99] and, the setup times are sampled from distributions ranging from [1, 49], [1, 99], [51, 149] and [101, 199]. The methods are evaluated by the percentage of success in find the best solution, the average relative deviation and the average computation time. The results of the computational investigation show the quality of the constructive heuristic method BMc and that the improvement heuristic method BMc outperforms all others. These results are presented and discussed.

Este trabalho propõe uma heurística construtiva determinística e uma heurística construtiva probabilística para resolver o problema de programação de projetos com custo de disponibilidade de recursos e custo de penalidade por atraso no término do projeto (RACPT - Resource Availability Cost Problem with Tardiness). Os algoritmos combinam a flexibilidade da atividade com a flexibilidade do recurso para selecionar a próxima atividade a ser programada. A data de início de uma atividade é a data mais cedo em que sua execução não gera o maior pico de utilização dos recursos ou a data mais cedo na qual o custo total do projeto for menor. A melhor versão das heurísticas foi obtida após o teste de várias regras de prioridade, conforme a revisão bibliográfica realizada. As heurísticas propostas foram testadas em 360 instâncias de testes e seus resultados foram comparados aos obtidos pela formulação matemática baseada em strip packing e restrições disjuntivas implementada no programa CPLEX. A heurística construtiva determinística gera uma solução viável rapidamente, porém de baixa qualidade. Já a heurística construtiva probabilística gera soluções ótimas ou próximas da ótima para problemas pequenos ou para problemas fáceis e gera soluções muito melhores do que o CPLEX na metade do tempo computacional para os problemas médios e grandes ou para problemas difíceis. Dado os bons resultados obtidos e à implementação no programa VBA for Microsoft Excel, a heurística construtiva probabilística proposta é um método bom e prático para resolução do RACPT. / This work proposes a deterministic constructive heuristic and a probabilistic constructive heuristic for solving the resource availability cost problem with tardiness (RACPT). The algorithms combine the flexibility of an activity with the flexibility of a resource to select the next activity to be scheduled. The start time of the activity is the earliest date in which the activity\'s execution does not create resources usage peak or the earliest date with the lowest total project cost. We tested several priority rules according to the literature review and determined the best version of the heuristics. Afterwards, we tested the proposed heuristics in 360 instances and compared its results with the solutions obtained by the optimization software CPLEX. The RACPT implementation on CPLEX utilized a mathematical formulation based on strip packing concepts and disjunctive constraints. The computational results showed that the deterministic constructive heuristic generates feasible solutions of poor quality in low computational time. The probabilistic constructive heuristic achieved better results. For small instances or easy problems, it found optimal or near-optimal solutions. For medium and large instances or hard problems, it obtained better results than CPLEX in half-computational time. We believe that the probabilistic constructive heuristic is a good and practical method for solving the RACPT. The proposed algorithm produced good results in reasonable computational time and was implemented on the popular software VBA for Microsoft Excel.

O objetivo desse trabalho é o de estudar o problema de programação de tarefas num ambiente produtivo com uma única máquina com data comum de entrega. Nesse caso, as tarefas, depois de processadas uma única vez na máquina, devem ser entregues em uma data comum e sofrem penalidades de adiantamento e de atraso conforme o instante em que são completadas. Na prática, esse problema é encontrado em casos de pedidos de lotes de produtos com data de entrega comum préespecificada, embarques para exportação e material químico ou misturas que têm vida média de curta duração. Problemas desse tipo são NP-hard (Hall, Kubiak & Sethi, 1991; Hoogeven & van de Velde, 1991), sendo comumente tratados na literatura através de heurísticas e meta-heurísticas. Visto não ser de nosso conhecimento a existência na literatura de tratamento desse problema através de métodos exatos, propôs-se a utilização de um algoritmo do tipo branch-and-bound para obtenção da solução ótima do problema que minimize a soma das penalidades de adiantamento e de atraso. No desenvolvimento do algoritmo, a utilização de propriedades do problema foi importante na elaboração de limitantes inferiores e regras de dominância que melhoraram a eficiência do modelo. Os experimentos realizados avaliaram o desempenho de diferentes critérios elaborados, como escolha do nó pai, limitante inferior, ordem de execução das estratégias e ordem de construção da seqüência. Os resultados obtidos mostraram-se robustos quando comparados com o benchmark da literatura e revelaram o bom desempenho do modelo para problemas de pequeno porte, superando o desempenho de programas de otimização comerciais. / The objective of this work is to study the single-machine scheduling problem with a common due date. In this case, jobs, after be processed only once in the machine, must be delivered in a common due date and they are penalized of earliness or tardiness according to their completion time. This problem is found in cases of batch production with prespecified common due date, exportation shipping and chemical material that has short half-life period. This kind of problem is NP-hard (Hall, Kubiak & Sethi, 1991; Hoogeven & van de Velde, 1991) and it has been treated in the literature by heuristics and meta-heuristics. Not having knowledge about previous treatment by exact methods in the literature, it was proposed the implementation of a branch-and-bound algorithm to obtain the optimal solution that minimizes the total weighted earliness and tardiness penalties. In the development of the algorithm, the utilization of problem properties was important to the elaboration of lower bounds and pruning rules that have enhanced the efficiency of the model. The realized tests have evaluated the performance of different criteria, like the choice of father node, lower bound, strategy execution order and sequence construction order. The obtained results have demonstrated robustness comparing to benchmark and they have revealed the good working of the model for small problems, overcoming optimization software performance.

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

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.

Foi observado que para execução do planejamento diário, no qual há o envolvimento de diversas equipes como operação, perfuração e atividade de apoio, despende-se muito tempo para determinação dos alvos de produção. Em contrapartida, a maior parte das minas de grande porte utilizam sistemas de gerenciamento de equipamentos que são capazes de fornecer dados para tratamento e transformação em informação que poderiam auxiliar nesse planejamento, no entanto na maioria dos casos esses dados são pouco conhecidos e utilizados. Este estudo faz a estimativa de indicadores de desempenho de lavra, oriundos do banco de dados do sistema de Despacho, que podem ser utilizados no planejamento diário (tipo Line-Up aplicado na mina do Sossego, em Canaã dos Carajás - Pará). Metodologicamente, para atingir o proposto, foram realizadas as etapas de análise do Banco de Dados (BD) do sistema de Despacho, descrição do Line-Up da mina do Sossego, análise do contexto operacional entre os dois sistemas: Line-Up e Despacho, estimativa dos indicadores e definição de um cálculo de aderência ao Line-Up. Esse estudo demostra que a partir da coleta e sistematização dos dados é possível tornar as informações contidas no BD do Despacho mais conhecidas e utilizadas na programação diária, permitindo que a utilização dessas informações auxilie na gestão do planejamento de curto prazo, reduzindo o tempo de execução da programação diária e tornando o processo de avaliação da aderência ao Line-Up mais rápido e menos subjetivo. Os dados utilizados para esse estudo são do banco de dados do sistema de despacho da Mina do Sossego (local de exemplo de aplicação). / Daily planning execution, which calls for several teams such as operation, drilling and support to be engaged, has been observed to be a rather time-consuming activity in order for production targets to be determined. On the other hand, most of large-size mine sites make use of equipment management systems capable of providing data to be treated and eventually made into information that may assist such planning efforts. However, such data are mostly scarcely known and used. This paper provides the estimation of mine performance indicators stemming from Dispatch system database that may come in handy for daily planning efforts (Line-Up type, applied to Sossego mine site, in Canaã dos Carajás, state of Pará, Brazil). Methodologically speaking, in order for proposed outcomes to be attained, Dispatch system database has been analyzed, Sossego mine site Line-Up has been described, operational context underlying both systems, Line-Up and Dispatch, has been analyzed, indicators have been estimated, and a Line-Up adherence calculation has been defined. The present paper indicates that, based on data gathering and systematization, information from Dispatch database can be made well known and used during daily scheduling efforts, thus allowing for such information to assist short-term plan management, daily scheduling performance timeframe to be cut down on, and Line-Up adherence assessment process to be faster and less subjective. Data used for this paper come from Sossego mine site dispatch system database (example of local application).

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.