Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/261049
Type: TESE
Title: Programação em maquinas paralelas não-relacionadas, sujeitas a divisão de tarefas
Author: Coelho, Marco Antonio Freitas do Egito
Advisor: França, Paulo Morelato, 1949-
Abstract: 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 aqui

Abstract: 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 to process 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 lower bounds 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 test problems with up to 120 jobs and 6 machines has been used to show the performance of the proposed methods
Subject: Programação heurística
Otimização combinatória
Planejamento da produção
Pesquisa operacional
Language: Português
Editor: [s.n.]
Date Issue: 1996
Appears in Collections:FEEC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Coelho_MarcoAntonioFreitasdoEgito_D.pdf6.88 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.