Banca de DEFESA: BRUNO FERREIRA ROSA
Uma banca de DEFESA de DOUTORADO foi cadastrada pelo programa.DISCENTE : BRUNO FERREIRA ROSA
DATA : 27/10/2017
HORA: 09:00
LOCAL: Auditório do Prédio 12 Campus II, CEFET-MG Av. Amazonas, 7675 - Nova Gameleira
TÍTULO:
Problemas de programação de tarefas em uma máquina com janelas de conclusão e Penalidades por Atnecipação e Atraso:Algoritmos e Fromulações.
PALAVRAS-CHAVES:
Programação de Tarefas, Janelas de Conclusão, Preparação da Máquina, Inserção de Tempos Ociosos, Formulações Matemáticas, Heurísticas de Separação.
PÁGINAS: 115
RESUMO:
Este trabalho trata o problema de programação de tarefas em uma máquina com janelas de conclusão distintas e tempos de preparação da máquina dependentes da sequência de execução das tarefas, denominado SMSPETP-SDS. O objetivo é minimizar a soma ponderada das antecipações e dos atrasos na conclusão das tarefas. Em termos práticos, as penalidades por antecipação são decorrentes de custos gerados pela necessidade de estocagem, enquanto as penalidades por atraso são consequências de multas contratuais. O SMSPETP-SDS possui muitas aplicações em indústrias metalúrgicas, têxteis, químicas, entre outras. Além do grande número de aplicações, é um problema difícil de ser resolvido na otimalidade, visto pertencer à classe NP-difícil. A união entre a aplicabilidade e a dificuldade de encontrar uma solução ótima motiva o desenvolvimento de algoritmos eficientes para resolvê-lo. Apesar disso, o problema de programação de tarefas com as características consideradas neste trabalho ainda não recebeu a devida atenção. Embora existam na literatura formulações matemáticas que representam o SMSPETP-SDS, elas não são eficientes e o SMSPETP-SDS tem sido tratado somente por meio de procedimentos heurísticos que dividem o problema em dois subproblemas: determinar a melhor programação de uma dada sequência de tarefas, considerando-se a possibilidade de inserção de tempos ociosos entre a execução de tarefas consecutivas; e determinar uma seqüência de tarefas que, associada à sua programação ótima, minimize a soma das penalidades geradas pelas tarefas. Neste trabalho, o SMSPETP-SDS é tratado sob uma perspectiva ainda não considerada na literatura. Inicialmente é proposto um novo algoritmo de programação ótima de uma dada sequência de tarefas. Esse algoritmo, de complexidade O(n2), é utilizado nos algoritmos heurísticos propostos para resolver o problema de sequenciamento das tarefas. Esse algoritmo de programação ótima também é utilizado em um algoritmo exato de enumeração implícita para o caso particular com tempos de preparação da máquina independentes da sequência de execução das tarefas, denominado SMSPETP-SIS. O algoritmo de enumeração implícita proposto faz uso de resultados teóricos desenvolvidos exclusivamente para o SMSPETP-SIS. Em um segundo momento, propõem-se várias formulações matemáticas para o SMSPETP-SDS. Um horizonte de planejamento para a execução de cada tarefa é proposto a um de ser utilizado na determinação dos parâmetros de entrada dessas formulações. Por último, são propostas novas famílias de restrições válidas para as formulações baseadas em variáveis indexadas no tempo, bem como algoritmos de separação para essas famílias. Experimentos computacionais mostram que: o algoritmo de programação ótima de uma dada sequência de execução das tarefas proposto é mais rápido que o algoritmo até então utilizado para esse um; os algoritmos heurísticos propostos para o problema de sequenciamento das tarefas são melhores que dois algoritmos da literatura na maioria dos problemas-teste considerados; o algoritmo de enumeração implícita é uma boa alternativa para a resolução exata do SMSPETP-SIS; e os limites inferiores construídos com os algoritmos de separação propostos são muito melhores que as soluções das respectivas relaxações lineares das formulações matemáticas apresentadas
MEMBROS DA BANCA:
Externo à Instituição - DÉBORA PRETTI RONCONI - USP
Interno - ELISANGELA MARTINS DE SA
Interno - FLAVIO VINICIUS CRUZEIRO MARTINS
Externo à Instituição - LUIZ SATORU OCHI - UFRJ
Interno - MARCONE JAMILSON FREITAS SOUZA - UFRJ
Externo à Instituição - PHILIPPE YVES PAUL MICHELON - UDPV
Interno - SERGIO RICARDO DE SOUZA