Informações:

Publicações do PESC

Título
Mathematical Modeling for the Job Shop Scheduling Problem with Realistic Constraints
Linha de pesquisa
Otimização
Tipo de publicação
Dissertação de Mestrado
Número de registro
Data da defesa
19/12/2023
Resumo

O problema do job shop flexível determina a programação da fabricação, considerando diferentes tarefas e máquinas. Devido à generalidade e complexidade de diferentes linhas e processos de produção, os modelos para esse problema costumam ser relativamente específicos e restritos. Este trabalho considera o problema de job shop flexível com restrições mais realistas, como horários de início mínimos, diferentes funções objetivo e o uso de Grafos Acíclicos Direcionados (GADs) para representar restrições de precedência entre operações de um mesmo job. Quatro modelos de Programação Inteira Mista (PIM) são propostos para capturar tais cenários, e são resolvidos pelo método de branch-and-bound clássico. No primeiro conjunto de experimentos, um software de simulação a eventos discretos, que lida com vários tipos de problemas de programação de produção e possui um núcleo heurístico, é usado para comparar a qualidade das soluções obtidas. No segundo conjunto de experimentos, o mesmo software é utilizado para gerar soluções viáveis a serem utilizadas pelo solucionador matemático. São avaliadas instâncias de referência, sintéticas e outras baseadas em casos do mundo real. O primeiro conjunto de experimentos numéricos indica que as soluções dos modelos de PIM propostos superam as soluções heurísticas em todos os casos testados. O segundo conjunto de experimentos numéricos indica que a resolução dos modelos pode ser afetada através de melhorias nas soluções dual e primal encontradas ao longo da resolução dos modelos.

Abstract

The flexible job shop problem determines manufacturing scheduling taking into account different tasks and machines. Due to the generality and complexity of different production lines and processes, models for this problem are often relatively specific and restricted to a production line. This paper considers the flexible job shop problem with more realistic constraints such as minimum start times, different objective functions and the use of a Directed Acyclic Graph (DAG) to represent precedence constraints between operations in the same job. Four Mixed Integer Programming (MIP) models are proposed to capture these scenarios and benchmark instances are solved using the classical branch-and-bound method. A discrete event simulation software which handles various types of production scheduling problems and has a heuristic core to generate viable solutions is used to compare the quality of the solutions obtained via MIP. In the second scenario, the viable solutions generated by the simulation software are used as initial solutions by the mathematical solver. Reference, synthetic and other instances based on real-world cases are evaluated. The first set of numerical experiments indicate that the solutions obtained from the proposed MIP models outperform the heuristic solutions in all the cases evaluated. The second set of numerical experiments indicate that the MIP models are affected through improvements in the dual and primal solutions found throughout the execution of the branch-and-bound method.

Arquivo
Topo