Otimização por colônia de formigas para o problema de sequenciamento de tarefas em uma única máquina com terceirização permitida

AUTOR(ES)

Tavares Neto, Roberto Fernandes, Godinho Filho, Moacir

FONTE

Gest. Prod.

DATA DE PUBLICAÇÃO

2013-03

RESUMO

Este artigo trata do problema de sequenciamento de tarefas em um ambiente de máquina única com possibilidade de terceirização. O problema apresentado busca minimizar a soma ponderada dos custos totais de terceirização e do somatório dos tempos de finalização de cada tarefa e é definido na literatura como 1 / Budget / (1 - δ) Σ Cj + δ. OC. Para esta resolução do referido problema, é proposto um método formado por dois estágios: no primeiro estágio, propõe-se que as tarefas sejam sequenciadas, utilizando-se a regra SPT (Shortest Processing Time - Menor Tempo de Processamento) para que se consiga a redução do espaço de busca no grafo gerado, enquanto que, no segundo estágio, é proposto um algoritmo baseado em ACO (Ant Colony Optimization - Otimização por Colônia de Formigas). O algoritmo aqui proposto incorpora ao ACO quatro características específicas do problema estudado, a saber: i) uma representação em forma de grafo para problemas de scheduling que envolvam terceirização, obtida por meio da aplicação do primeiro estágio do método; ii) uma regra de pré-seleção, que garante a viabilidade da solução; iii) uma nova regra de visibilidade específica para o problema; e iv) uma estratégia de busca local. Os resultados obtidos neste trabalho mostram que o algoritmo baseado em ACO desenvolvido é mais eficiente que o algoritmo de Lee e Sung (2008a) que foi o único trabalho encontrado na literatura que trata do problema em discussão. Adicionalmente, a busca local proposta melhorou o resultado para problemas de tamanho médio e grande.

ASSUNTO(S)

sequenciamento e programação de operações colônia de formigas terceirização

Documentos Relacionados

• Otimização bi-objetivo para o problema de sequenciamento de tarefas em uma maquina com tempos de preparação dependentes da sequencia
• Uma heurística de trocas para o problema de sequenciamento de tarefas em processadores uniformes
• Relaxação lagrangeana com fixação de variáveis aplicada ao problema de sequenciamento em uma máquina
• Proposta de solução de problemas de scheduling considerando possibilidade de terceirização usando a técnica de otimização por colônia de formigas
• Roteamento em redes embutidas utilizando otimização por colônia de formigas.