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

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 - δ) Σ C j + δ . 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.