An Ant Colony Optimization Algorithm for Scheduling Parallel Machines with Sequence-Dependent Setup Costs

The paper addresses the problem of scheduling preemptive jobs on parallel unrelated machines in the presence of renewable resource constraints and sequence-dependent setup costs. The objective is to minimize the weighted sum of makespan and setups. The problem is known to be NP-hard. To solve this problem, a heuristic is proposed which uses column generation technique and an ant colony optimization algorithm. The results of a computational experiment indicate that the heuristic is able to produce good results in reasonable computation time.

Artykuł dotyczy zagadnienia szeregowania zadań podzielnych na równoległych dowolnych maszynach z uwzględnieniem ograniczeń na dostępność zasobów odnawialnych oraz kosztów przezbrojeń zależnych od kolejności wykonywania zadań. Celem jest minimalizacja ważonej sumy czasu trwania harmonogramu i przezbrojeń. Zagadnienie należy do klasy problemów NP-trudnych. W celu jego rozwiązania, zaproponowany został algorytm heurystyczny, wykorzystujący technikę generacji kolumn, oraz algorytm mrówkowy. Wyniki eksperymentu obliczeniowego wskazują, że algorytm ten jest zdolny dostarczyć dobrej jakości wyniki w rozsądnym czasie.