SEQUENCE DEPENDENT PARALLEL MACHINE SCHEDULING USING PARALLEL ANT COLONY OPTIMIZATION WITH GRAPHICS HARDWARE ACCELERATION

摘要

This paper studies the effectiveness of using parallel Ant Colony Optimization for sequence dependent parallel machine scheduling on a Graphics Processing Unit (GPU) hardware platform. Parallel machine scheduling is a traditional NP-hard combinatorial optimization problem. In this research, a hybrid ant colony optimization method that combines the 'Apparent Tardiness Cost with Setups' (ATCS) dispatching rule with massive ants is proposed to solve the parallel machine scheduling problem quickly and efficiently. The computational results demonstrate that the proposed method is effective and solve the problems order of magnitude faster with a GPU accelerated implementation.