Modelo de fluxo em arcos para o problema de programação de tarefas em máquinas paralelas idênticas

• Ano de defesa: 2024
• Autor(a) principal: Sganzerla, Alisson Michel
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Santa Maria; Brasil; Engenharia de Produção; UFSM; Programa de Pós-Graduação em Engenharia de Produção; Centro de Tecnologia
• Palavras-chave em Português: Problema de programação de tarefas; Máquinas paralelas idênticas; Programação inteira mista; Fluxo em arcos; Makespan; Job scheduling problem; Identical parallel machines; Mixed-integer programming; Arc-flow; CNPQ::ENGENHARIAS::ENGENHARIA DE PRODUCAO
• Link de acesso: http://repositorio.ufsm.br/handle/1/33986

An arc-flow-based model is proposed to address the task scheduling problem on identical parallel machines. The objective of the problem is to minimize the time instant in which the last task is completed, known in the specialized literature as makespan. The model uses a graph structure to define the decision variables, in which the vertices represent the discretization of the task processing times. In this approach, the value of makespan is determined by the index associated with the vertex in which the flow starts in the graph. The proposed strategy reverses the conventional direction of the flow, defining the zero vertex as the final destination, instead of being the origin point. In the experiments performed with instances from the literature, the proposed model demonstrated less sensitivity to the quality of the bounds when compared to the reference model. Using the commercial solver CPLEX v20.01, the model presented a computational time approximately 400% lower in scenarios with weak bounds and approximately 100% lower in scenarios with strong bounds. Additionally, a new set of instances is proposed to identify features that influence the performance of arc-flow-based models.