Programação em maquinas paralelas não-relacionadas, sujeitas a divisão de tarefas

Resumo: Nesta tese novos métodos e procedimentos para resolver o problema de programação de tarefas em múltiplas máquinas paralelas com custos de atraso e adiantamento são propostos. As máquinas são não-relacionadas, a divisão de tarefas é permitida, as tarefas podem ter datas previstas de entrega diferentes e os tempos de preparação de máquina para executar uma tarefa depende da tarefa anterior processada na mesma máquina. Este é um problema novo, de dificil resolução e não foram encontradas referências na literatura especializada. Apesar disso, tem muitas possíveis aplicações na manufatura. O problema é formulado através de um modelo linear de programação inteira mista para o caso sem divisão de tarefas e, posteriormente,dois outros modelos lineares são propostos para o caso onde a divisão de tarefas é permitida. Como o problema de minimização foi mostrado ser NP-completo, os modelos podem apenas ser utilizados para resolver pequenos problemas de teste. A partir do modelo de programação inteira mista, um método de busca em árvore é desenvolvido para uso com procedimentos Branch & Bound e Busca em Feixe Filtrada. Dois limitantes inferiores são desenvolvidos para o Branch & Bound e quatro limitantes para a Busca em Feixe Filtrada. Algumas propriedades e teoremas do problema original e um método de decomposição eficiente para resolver o modelo linear derivado do modelo de programação inteira mista, também são apresentados. Muitos problemas de teste com até 120 tarefas e 6 máquinas são utilizados para mostrar o desempenho dos métodos desenvolvidos aquiAbstract: In this thesis new methods and procedures to solve the multimachine scheduling problem with early and tardy costs are proposed. The machines are unrelated, job splitting is allowed, the jobs may have different due dates and the changeover time toprocess a new job on a machine depends on the job previously processed on the same machine. This problem is new, hard to solve and no references have been found in respecialized literature. However, it has many applications in the manufacturing. Two linear mixed-integer programming models one stated when job splitting is allowed, as well as similarmodel is proposed for the case without job splitting. Since the problem is NP-hard, the models can oniy be used to solve small test problems. Based on the mixed-integer formulation, a tree search method is developed to be used in a Branch & Bound and in a Filtered Beam Search procedures. Two lowerbounds are developed for the Branch & Bound and four bounds for the Filtered Beam Search. Some properties of the original problem and an efficient decomposition method to solve the LP model derived from the mixed-integer problem are presented. Many testproblems with up to 120 jobs and 6 machines has been used to show the performance of the proposed method