Problemas de programação de tarefas com janelas de conclusão e penalidades por antecipação e atraso: algoritmos e formulações

Página do item simplificado
dc.contributor.advisorMichelon, Philippe Yves Paul
dc.contributor.advisor-coSouza, Sérgio Ricardo de
dc.contributor.advisor-coLatteshttp://lattes.cnpq.br/3677015295211434
dc.contributor.advisorLatteshttp://lattes.cnpq.br/6925570277196451
dc.contributor.authorRosa, Bruno Ferreira
dc.contributor.authorLatteshttp://lattes.cnpq.br/9733200718349659
dc.contributor.refereeSouza, Sérgio Ricardo de
dc.contributor.refereeSouza, Marcone Jamilson Freitas
dc.contributor.refereeMichelon, Philippe Yves Paul
dc.contributor.refereeRonconi, Débora Pretti
dc.contributor.refereeOchi, Luiz Satoru
dc.contributor.refereeSouza, Maurício Cardoso de
dc.contributor.refereeFrança Filho, Moacir Felizardo de França
dc.contributor.refereeSá, Elisângela Martins de
dc.contributor.refereeMartins, Flávio Vinícius Cruzeiro
dc.date.accessioned2025-05-20T23:40:13Z
dc.date.available2025-05-20T23:40:13Z
dc.date.issued2017-10-27
dc.description.abstractEste 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 exe- cuçã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. O SMSPETP-SDS tem sido tratado basicamente 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 sequê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 heu- rí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 exe- cuçã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 SMSPET P-SDS. Um horizonte de planejamento para a execução de cada tarefa é proposto a fim 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 pro- posto é mais rápido que o algoritmo até então utilizado para esse fim; 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 SMSPET P-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 line ares das formulações matemáticas apresentadas.
dc.description.abstractotherThis work addresses the single machine scheduling problem with distinct completion win- dows and sequence dependent setup times (SMSPET P-SDS). The objective is to minimize the total weighted earliness and tardiness. In the practice, earliness penalties are due to costs generated by the need of stockpiling, while tardiness penalties are consequences of contrac- tual penalties. SMSPET P-SDS has many applications in JIT manufacturing, semi-conductor manufacturing, chemical processing, PERT/CPM scheduling, and video on demand services, among others. In addition, SMSPETP-SDS is an NP-hard problem. The applicability of the SMSPETP-SDS coupled with the difficulty of finding an optimal solution motivates the deve- lopment of efficient algorithms to it. Nevertheless, the job scheduling problem with the charac- teristics considered in this work has not received the deserved attention. The SMSPET P-SDS has been treated basically by heuristic procedures that divide the problem into two subpro- blems: sequencing the jobs, and determining the optimal time for completion of each job in a given sequence (or inserting idle time between jobs in the sequence) in order to minimize the total penalties generated. In this work, the SMSPETP-SDS is treated from a perspective not yet considered in the literature. First, a new O(n2) optimal scheduling algorithm is proposed. This algorithm is used in proposed heuristic algorithms to solve the job sequencing problem. The optimal scheduling algorithm is also used in an exact algorithm, based on implicit enu- meration, for the special case with sequence-independent setup times (SMSPETP-SIS). The proposed implicit enumeration algorithm takes advantage of theoretical results generated for the SMSPETP-SIS. In a second moment, several mathematical formulations are proposed for the SMSPETP-SDS. In order to determine the input parameters of these formulations, a plan- ning horizon for the processing of each job is proposed. Finally, new valid constraints families for the formulations based on time-indexed variables, as well as separation algorithms for these families, are proposed. Computational experiments show that: the new algorithm for the opti- mal scheduling of a given job sequence is more efficient than the only other equivalent algorithm found in the literature; the proposed heuristic algorithms for the job sequencing problem are better than two algorithms of the literature in most of the instances considered; the implicit enumeration algorithm is a good alternative to the exact resolution of SMSPETP-SIS; and the lower bounds generated with the proposed separation algorithms are much better than the solutions of the respective linear relaxations of the presented mathematical formulations.
dc.description.sponsorshipCEFET-MG, UAPV, CNPq, UFOP.
dc.identifier.urihttps://repositorio.cefetmg.br//handle/123456789/1545
dc.language.isopt
dc.publisherCentro Federal de Educação Tecnológica de Minas Gerais
dc.publisher.countryBrasil
dc.publisher.initialsCEFET-MG
dc.publisher.programPrograma de Pós-Graduação em Modelagem Matemática e Computacional
dc.subjectProgramação heurística
dc.subjectAlgoritmos
dc.subjectFormulação
dc.titleProblemas de programação de tarefas com janelas de conclusão e penalidades por antecipação e atraso: algoritmos e formulações
dc.typeDissertação

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
Problemas de programação de tarefas com janelas de conclusão e penalidades por antecipação e atraso algoritmos e formulações.pdf
Tamanho:
1.92 MB
Formato:
Adobe Portable Document Format
Baixar
Licença do Pacote
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
1.39 KB
Formato:
Item-specific license agreed to upon submission
Descrição:
Baixar

Coleções

Mestrado em Modelagem Matemática e Computacional