• Portal do Governo Brasileiro

Plataforma Sucupira

Dados do Trabalhos de Conclusão

UNIVERSIDADE FEDERAL DE SANTA MARIA
ENGENHARIA DE PRODUÇÃO (42002010004P4)
MODELO DE FLUXO EM ARCOS PARA O PROBLEMA DE PROGRAMAÇÃO DE TAREFAS EM MÁQUINAS PARALELAS IDÊNTICAS
ALISSON MICHEL SGANZERLA
DISSERTAÇÃO
17/12/2024

Um modelo de fluxo em arcos é proposto para o problema de programação de tarefas em máquinas paralelas idênticas, com o objetivo de minimizar o tempo de conclusão da última tarefa, conhecido como makespan. O modelo utiliza uma estrutura em grafo para definir as variáveis de decisão, em que os vértices representam a discretização do tempo de processamento das tarefas. Nesse modelo, o makespan é obtido a partir do índice do vértice inicial do fluxo no grafo. Essa abordagem inverte a direção usual do fluxo, definindo o vértice zero como destino final, em vez do ponto de origem. Nos experimentos realizados com instâncias da literatura, o desempenho do modelo proposto mostrou-se menos sensível à qualidade dos limitantes aplicados ao makespan. O tempo médio de resolução com o resolvedor CPLEX v20.01 variou entre 3,60 e 2,24 segundos para diferentes qualidades de limitantes, enquanto o modelo da literatura, utilizado como referência, apresentou tempos entre 18,04 e 4,51 segundos nas mesmas condições. No caso de limitantes fracos, o modelo proposto apresenta um tempo computacional de resolução, em média, 400% inferior ao tempo computacional do modelo de referência; com limitantes fortes, essa diferença reduz-se para aproximadamente 100%. Adicionalmente, experimentos foram realizados em um conjunto de instâncias proposto neste trabalho para identificar as características que impactam o desempenho do modelo de fluxo em arcos.

Problema de programação de tarefas;Máquinas paralelas idênticas;Makespan;Programação inteira mista;Fluxo em arcos
An arc flow model is proposed for the problem of scheduling tasks on identical parallel machines to minimize the completion time of the last task, known as the makespan. The model uses a graph structure to define the decision variables, in which vertices represent the discretization of task processing times. In this model, the makespan is obtained from the index of the initial vertex of the flow in the graph. This approach reverses the usual flow direction, setting the zero vertex as the final destination rather than the starting point. In experiments conducted with instances from the literature, the performance of the proposed model was shown to be less sensitive to the quality of the bounds applied to the makespan. The average resolution time with the CPLEX v20.01 solver ranged between 3.60 and 2.24 seconds for different bound qualities, while the reference model from the literature presented times between 18.04 and 4.51 seconds under the same conditions. For weak bounds, the proposed model achieves a computational resolution time on average 400% lower than that of the reference model; with strong bounds, this difference reduces to approximately 100%. Additionally, experiments were performed on a set of instances proposed in this work to identify the characteristics impacting the performance of the arc flow model.
Job scheduling problem;Identical parallel machines;Makespan;Mixed-integer programming;Arc-flow
1
61
PORTUGUES
UNIVERSIDADE FEDERAL DE SANTA MARIA
O trabalho não possui divulgação autorizada

Contexto

Gerência da Produção
MÉTODOS QUANTITATIVOS PARA TOMADA DE DECISÃO
AMBIENTE PARA METACOMPUTAÇÃO COM SUPORTE PARA ALGORITMOS EVOLUTIVOS CORE+EVO

Banca Examinadora

OLINTO CESAR BASSI DE ARAUJO
DOCENTE - PERMANENTE
Sim
Nome Categoria
GUILHERME DHEIN Participante Externo
ALVARO LUIZ NEUENFELDT JUNIOR Docente - PERMANENTE
OLINTO CESAR BASSI DE ARAUJO Docente - PERMANENTE

Vínculo

CLT
Empresa Privada
Empresas
Sim
Plataforma Sucupira
Capes UFRN RNP
  • Compatibilidade
  • . . .
  • Versão do sistema: 3.85.3
  • Copyright 2022 Capes. Todos os direitos reservados.

Nós usamos cookies para melhorar sua experiência de navegação no portal. Ao utilizar o gov.br, você concorda com a política de monitoramento de cookies. Para ter mais informações sobre como isso é feito, acesse Política de cookies.Se você concorda, clique em ACEITO.

Politica de Cookies

O que são cookies?

Cookies são arquivos salvos em seu computador, tablet ou telefone quando você visita um site.Usamos os cookies necessários para fazer o site funcionar da melhor forma possível e sempre aprimorar os nossos serviços. Alguns cookies são classificados como necessários e permitem a funcionalidade central, como segurança, gerenciamento de rede e acessibilidade. Estes cookies podem ser coletados e armazenados assim que você inicia sua navegação ou quando usa algum recurso que os requer.

Cookies Primários

Alguns cookies serão colocados em seu dispositivo diretamente pelo nosso site - são conhecidos como cookies primários. Eles são essenciais para você navegar no site e usar seus recursos.
Temporários
Nós utilizamos cookies de sessão. Eles são temporários e expiram quando você fecha o navegador ou quando a sessão termina.
Finalidade
Estabelecer controle de idioma e segurança ao tempo da sessão.

Cookies de Terceiros

Outros cookies são colocados no seu dispositivo não pelo site que você está visitando, mas por terceiros, como, por exemplo, os sistemas analíticos.
Temporários
Nós utilizamos cookies de sessão. Eles são temporários e expiram quando você fecha o navegador ou quando a sessão termina.
Finalidade
Coletam informações sobre como você usa o site, como as páginas que você visitou e os links em que clicou. Nenhuma dessas informações pode ser usada para identificá-lo. Seu único objetivo é possibilitar análises e melhorar as funções do site.

Você pode desabilitá-los alterando as configurações do seu navegador, mas saiba que isso pode afetar o funcionamento do site.

Chrome

Firefox

Microsoft Edge

Internet Explorer