Parallel Ant Colony Optimization for Flow Shop Scheduling Subject to Limited Machine Availability
| Autor: | Jun Xiong Huang, Yumei Huo |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Mathematical optimization
Schedule 021103 operations research Job shop scheduling business.industry Computer science Ant colony optimization algorithms Computer Science::Neural and Evolutionary Computation Monte Carlo method 0211 other engineering and technologies Approximation algorithm 02 engineering and technology Flow shop scheduling Ant colony ComputingMethodologies_ARTIFICIALINTELLIGENCE 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Local search (optimization) Algorithm design business Monte Carlo algorithm |
| Zdroj: | IPDPS Workshops |
| DOI: | 10.1109/ipdpsw.2016.151 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|