Heuristica

Disponível somente no TrabalhosFeitos
  • Páginas : 39 (9641 palavras )
  • Download(s) : 0
  • Publicado : 22 de abril de 2013
Ler documento completo
Amostra do texto
Produção, v. 22, n. 4, p. 766-777, set./dez. 2012 http://dx.doi.org/10.1590/S0103-65132012005000020

Uma heurística híbrida para minimizar custos com antecipação e atraso do sequenciamento da produção em uma máquina
Puca Huachi Vaz Pennaa*, Marcone Jamilson Freitas Souzab, Frederico Augusto de Cezar Almeida Gonçalvesc, Luiz Satoru Ochid
*puca@iceb.ufop.br, UFOP, Brasil marcone@iceb.ufop.br,UFF, Brasil c fred@nti.ufop.br, CEFET-MG, Brasil d satoru@ic.uff.br, UFF, Brasil
a b

Resumo
Este trabalho tem seu foco no problema de sequenciamento em uma máquina com penalidades por antecipação e atraso da produção. São considerados tempos de preparação da máquina dependentes da sequência de produção, bem como a existência de janelas de entrega distintas. Para resolução do problema,desenvolveu-se um algoritmo heurístico de 3 fases, nomeado GTSPR. A primeira fase baseada em GRASP é descida em vizinhança variável para a geração da solução inicial, a segunda fase baseada em busca tabu para refinamento da solução, e por fim a reconexão por caminhos como estratégia de pós-otimização, na terceira fase. Para cada sequência gerada pela heurística é utilizado um algoritmo de tempo polinomialpara determinar a data ótima de início de processamento de cada tarefa. Os resultados computacionais mostraram que o algoritmo GTSPR supera outros algoritmos da literatura, tanto com relação à qualidade da solução final quanto em relação à variabilidade dessas soluções.

Palavras-chave
Sequenciamento em uma máquina. GRASP. Busca tabu. Descida em vizinhança variável. Reconexão por caminhos.1. Introdução
De acordo com França Filho (2007), o estudo de problemas de programação de tarefas envolvendo penalizações pela antecipação e pelo atraso é mais recente que aquele voltado para problemas em que o objetivo envolve uma função não decrescente do instante de conclusão do processamento da tarefa, tais como tempo médio de fluxo, soma ponderada de atrasos e makespan (momento em que terminaa execução da última tarefa). Para estes, custos mais elevados decorrem apenas do adiamento da conclusão das tarefas. Entretanto, com a filosofia just-in-time adotada por muitas empresas, o foco atual é penalizar também a conclusão das tarefas antes do instante em que elas são requeridas. Isso é justificado pelo fato de que concluir uma tarefa antecipadamente pode resultar em custos financeirosextras pela necessidade antecipada de capital e/ou espaço para armazenamento e/ou de outros recursos para manter e gerenciar o estoque. Com relação às entregas, são encontrados na literatura 3 tipos de problemas: a) datas de entrega comuns (common due date), b) datas de entrega distintas (distinct due dates) e c) janelas de entrega distintas (distinct due windows). No primeiro tipo, existe umaúnica data para entregar todas as tarefas, enquanto no segundo há uma data de entrega específica associada a cada tarefa. No terceiro tipo, há um período para a conclusão de cada tarefa. Segundo Wan e Yen (2002), este último aparece em situações de incertezas ou tolerâncias com relação às datas de entrega e não há custos se as tarefas forem concluídas dentro da janela de entrega.
*UFOP, Ouro Preto,MG, Brasil Recebido 05/05/2009; Aceito 25/07/2011

Penna, P. H. V. et al. Uma heurística híbrida ... produção em uma máquina. Produção, v. 22, n. 4, p. 766-777, set./dez. 2012

767

Para problemas de produção envolvendo penalizações pela antecipação e pelo atraso com datas comuns de entrega, há muitas propriedades que podem ser consideradas nos algoritmos de solução e que permitem uma reduçãodo esforço computacional na exploração do espaço de busca. Por exemplo, de acordo com Baker e Scudder (1990), se Ci representa a data de conclusão da tarefa i e f (Ci ), o valor da função custo relativo à tarefa i, então na sequência ótima, os pontos (Ci; f (Ci )) formam um V (diz-se que a sequência é V-shaped ). Em outras palavras, na sequência ótima, as tarefas antecipadas devem ser...
tracking img