Formulações para o problema do flow shop em duas máquinas com penalidades por atraso nas tarefas

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorBarboza, Eduardo Uchoa-
Autor(es): dc.contributorCPF:85462487922-
Autor(es): dc.contributorhttp://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4721785E2-
Autor(es): dc.contributorPessoa, Artur Alves-
Autor(es): dc.contributorCPF:78134500221-
Autor(es): dc.contributorhttp://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4797569Z6-
Autor(es): dc.contributorRodrigues, Rosiane de Freitas-
Autor(es): dc.contributorCPF:02862839728-
Autor(es): dc.contributorhttp://lattes.cnpq.br/8358219976594707-
Autor(es): dc.creatorGonçalves, José Mauricio Brasil-
Data de aceite: dc.date.accessioned2024-07-11T18:04:27Z-
Data de disponibilização: dc.date.available2024-07-11T18:04:27Z-
Data de envio: dc.date.issued2021-03-10-
Data de envio: dc.date.issued2009-11-10-
Data de envio: dc.date.issued2021-03-10-
Data de envio: dc.date.issued2009-09-25-
Fonte completa do material: dc.identifierhttps://app.uff.br/riuff/handle/1/18610-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/762997-
Descrição: dc.descriptionScheduling problems are very common in manufacturing and services industries. Scheduling deals with the allocation of scarce resources to jobs over time. The goal is optimizing one or more objectives, translating into the best order in with jobs must be processed by each machine. Many of scheduling problems belong to the NP-hard class of problems, this being the case of the problem studied here. The goal is to propose integer programming formulations for the deterministic two machine flow shop problem, with penalties on the jobs tardiness. In the three-field notation this problem is denoted as F2 | | Σw T . The fact of seeking to minimize the weighted sum of jobs tardiness makes the problem much more difficult when compared to the famous problem of minimizing the completion time of the last job to leave the system (the makespan), denoted as F2 | | Cmax (it can be solved in polynomial time by Johnson´s algorithm). Formulations were tested with binary variables x (that assume value one when job j completes at machine i at time t) and a formulation with binary variables x (that assume value one when job j leaves the system at time t). Computational experiments with instances with up to 50 jobs have shown that the formulation with variables obtained initial dual limits closer to the optimal value of the objective function. Finally, it is also proposed a more compact formulation for the problem, not using the index t in the decision variables and a local search heuristic for solving the problem and heuristics that support the branch and bound algorithms to find a good primal bounds.-
Descrição: dc.descriptionProblemas de escalonamento são muito comuns nos ambientes de produção de bens e prestação de serviços. Referem-se à alocação de recursos escassos a tarefas ao longo de determinados períodos de tempo. A meta consiste em otimizar um ou mais objetivos, traduzindo-se na melhor ordem que as tarefas devem ser processadas por cada uma das máquinas. Muito dos problemas de escalonamento enquadram-se na categoria NP - difícil, sendo o caso do problema desta pesquisa. Este estudo tem por objetivo propor formulações de programação inteira para o problema de escalonamento determinístico Flow shop com duas máquinas onde existem penalidades por atraso nas tarefas. Na notação de três campos tem-se: F2 | | Σ. O fato de buscar a minimização do somatório ponderado dos atrasos das tarefas, faz com que o problema apresente complexidade computacional superior quando comparado ao famoso problema de minimização do tempo de finalização da última tarefa a deixar o sistema: F2 | | Cmax (sendo este último resolvido em tempo polinomial pelo algoritmo de Johnson). Foram testadas formulações com variáveis binárias (que assumem valor unitário se a tarefa j finaliza seu processamento na máquina i no tempo t) e variáveis binárias (que assumem valor unitário se a tarefa j tem seu processamento finalizado na segunda máquina no tempo t). Em testes elaborados com instâncias de até cinqüenta tarefas, observouse que a formulação com a variável obteve limites duais iniciais mais próximos do valor ótimo da função objetivo. Por último, foi também proposta uma formulação mais compacta para o problema, não utilizando o índice t nas variáveis de decisão, além de uma heurística de busca local para solução do problema e heurísticas que apóiam o algoritmo de branch and bound a encontrar uma solução viável inicial.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Publicador: dc.publisherPrograma de Pós-graduação em Engenharia de Produção-
Publicador: dc.publisherEstratégia-Apoio Logístico-Tecnologia e Trabalho-
Direitos: dc.rightsAcesso Aberto-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectEngenharia de produção-
Palavras-chave: dc.subjectEscalonamento de tarefa-
Palavras-chave: dc.subjectProgramação inteira-
Palavras-chave: dc.subjectPesquisa operacional-
Palavras-chave: dc.subjectProblemas de escalonamento-
Palavras-chave: dc.subjectFormulações-
Palavras-chave: dc.subjectScheduling problems-
Palavras-chave: dc.subjectFormulations-
Palavras-chave: dc.subjectInteger programming-
Palavras-chave: dc.subjectCNPQ::ENGENHARIAS::ENGENHARIA DE PRODUCAO-
Título: dc.titleFormulações para o problema do flow shop em duas máquinas com penalidades por atraso nas tarefas-
Título: dc.titleFormulations for the two machine flow shop problem with weigthed tardiness-
Tipo de arquivo: dc.typeDissertação-
Aparece nas coleções:Repositório Institucional da Universidade Federal Fluminense - RiUFF

Não existem arquivos associados a este item.