Programação de tarefas em um flow shop. / Flow shop jobscheduling

AUTOR(ES)
DATA DE PUBLICAÇÃO

2009

RESUMO

Este trabalho trata de um problema de programação de tarefas em ambiente flow shop com algumas características específicas que, juntas, o diferenciam dos problemas usuais. Há N tarefas a serem processadas por M máquinas independentes e cada tarefa tem seu roteiro particular ao longo da oficina (shop), não passando necessariamente por todas as máquinas; cada tarefa deve ser concluída dentro de um respectivo intervalo de tempo, designado de janela de tempo, e há punições por adiantamento e atraso na conclusão da tarefa. O desempenho da programação é medido pela soma das punições por adiantamento e atraso. Trata-se de um problema de natureza combinatória, pertencente à classe NP-Difícil, para o qual, no limite, há (N !)^M alternativas. Neste trabalho, propõe-se um modelo matemático para representação do problema; para sua resolução é utilizado o pacote de programação linear mista inteira CPLEX; dada a dificuldade da obtenção de solução exata para as instâncias maiores, são propostas heurísticas para resolução do problema. São apresentados também procedimentos combinados, utilizando uma solução inicial gerada por heurística e o modelo matemático, quer usando a estrutura geral de ramificação do CPLEX, quer usando a técnica de ramificação local (Local Branching).

ASSUNTO(S)

heurística operations research mathematical model heuristics pesquisa operacional (otimização) modelos matemáticos

ACESSO AO ARTIGO

Documentos Relacionados