Otimização por colônia de formigas para o problema de sequenciamento de tarefas em uma única máquina com terceirização permitida An ant colony optimization approach for the single machine scheduling problem with outsourcing allowed

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.This paper considers the problem of scheduling a set of tasks on a single machine environment with outsource allowed. This multicriteria problem, defined as 1 / Budget / (1 - δ) Σ Cj + δ. OC, aims to minimize the weighted sum of total outsourcing costs and the sum of individual completion times. To solve this problem, a two-stage method is proposed: the first stage orders the tasks using the SPT (Shortest Processing Time) rule. The second stage uses an ACO (Ant Colony Optimization) algorithm to decide whether the job will be outsourced by using four problem-specific variations: i) a graph-representation of scheduling problems for scheduling problems with outsourcing allowed; ii) a pre-selection rule that guarantees the viability of the solution; iii) a new problem-specific visibility rule; and iv) a local search strategy. The implementation of this method produces better results than those obtained by Lee and Sung (2008a), the only paper found in the literature that deals with this problem. Moreover, the local search procedure was able to improve the results for medium and large problem sets.