Parallel Ant Colony Optimization for Flow Shop Scheduling Subject to Limited Machine Availability

摘要

In this paper, parallel ant colony algorithm (PAC) and parallel ant colony with local search algorithm (PACwLS) are presented and applied to Permutation Flowshop Scheduling Problem subject to limited machine availability. The objective is to minimize total flowtime criterion. This problem is proved to be NP-complete in a strong sense for more than one machine even when machines are always available. PAC and PACwLS are based on the classical ant colony algorithm, but are implemented and adapted on parallel computer systems with Message Passing Interface involving the communications and collaborations of multiple computing nodes. Computational experiments show that by comparing with monte carlo algorithm, both PAC and PACwLS ourperform monte carlo algorithm, and PACwLS consistently outperforms PAC and converges faster than both PAC and monte carlo algorithm.