Minimização do custo de antecipação e atraso para o problema de sequenciamento de uma máquina com tempo de preparação dependente da sequência: aplicação em uma usina siderúrgica

Nesta dissertação foi estudado o problema de seqüenciamento de uma máquina, com objetivo de minimizar o somatório dos custos de antecipação e atraso no atendimento de uma demanda e com tempo de preparação de máquina dependente da sequência de produção. O problema do planejamento operacional da produção do laminador de uma usina siderúrgica, que serve de inspiração e ambiente para esta pesquisa, consiste em determinar uma melhor seqüência para a produção de um conjunto de ordens planejadas. Cada ordem possui uma data desejada para atendimento, ocorrendo a incidência de custo de atraso se a ordem é programada para produzir posteriormente à respectiva data desejada, ou custo de antecipação se a ordem PE produzida antes do desejado. Para representar o problema, foram desenvolvidos modelos utilizando Programação Linear Inteira Mista. Foram propostos dois modelos utilizando as formulações de Manne [16] e Wagner [24], tratando o tempo de preparação de máquina como uma restrição do problema. Entretanto, a partir das conclusões iniciais para situações de ociosidade da máquina, foi percebida a necessidade de tratar também o custo de preparação, sendo desenvolvido então um outro modelo. As dificuldades de modelagem do problema estudado partindo-se das definições de Manne e Wagner são explicitadas, assim como a comparação do desempenho dos modelos quando aplicados na resolução de um mesmo cenário de teste. Os modelos foram implementados utilizando a linguagem de programação MathProg e o software de otimização GLPK 4.8. A modelagem proposta e as análises dos resultados, mesmo que limitados para problemas em escala reduzida, permitem avaliar a aplicação dos modelos para o caso estudado e conhecer melhor o problema e suas soluções, gerando conhecimento que pode contribuir para o desenvolvimento de heurísticas convenientes para tratar problemas reais.In this dissertation was studied the one-machine scheduling problem, with the objective of minimizing the sumo f earliness and tardiness costs, with sequence dependent setup time. The operational planning problem of rolling production in a steel plant, which was the inspiration and environment to this research, consists of determining a best sequence to produce a set of production planning orders. Each order has a due date. If the sequence programming the order produces after the due date, there is tardiness cist, otherwise, if the order is programmed before the due date, there is earliness cost. To present the problem were developed Mixed Integer Linear Programming models. Two models were proposed, using the Mannes [16] and Wagner1s [24] formulations, dealing with setup times like a problem restriction. However, from the initial conclusions in idleness situations, was understood the necessity of dealing with setup costs also, when was developed another model, This difficulties of the modeling of the problem studied, from Mannes and Wagners definitions, are showed, such as the comparison about the performance when it is used to resolve the some problem. The models were implemented using the language MathProg and optimizing package GLPK 4.8. The modeling proposed and the result analysis, even that limited to problems with reduced size, allow evaluate the application for models in the studied case and understand the problem and its solutions, generating knowledge that can contribute to development of suitable heuristics to solve real problems