Parallel ant colony optimization for resource constrained job scheduling.

*(English)*Zbl 1350.90013Summary: In mining supply chains, large combinatorial optimization problems arise. These are NP-hard and typically require a large number of computing resources to solve them. In particular, the run-time overheads can become increasingly prohibitive with increasing problem sizes. Parallel methods provide a way to manage such run-time issues by utilising several processors in independent or shared memory architectures. However it is not obvious how to adapt serial optimisation algorithms to perform best in a parallel environment. Here, we consider a resource constrained scheduling problem which is motivated in mining supply chains and present two popular meta-heuristics, ant colony optimization (ACO) and simulated annealing and investigate how best to parallelize these methods on a shared memory architecture consisting of several cores. ACO’s solution construction framework is inherently parallel allowing a relatively straightforward parallel implementation. However, for best performance, ACO needs an element of local search. This significantly complicates the paralellization. Several alternative schemes for parallel ACO with elements of local search are considered and evaluated empirically. We find that ACO with local search is the most effective single-threaded algorithm. The best parallel implementation can obtain similar quality results to the serial method in significantly less elapsed time.

##### MSC:

90B06 | Transportation, logistics and supply chain management |

90C27 | Combinatorial optimization |

90C59 | Approximation methods and heuristics in mathematical programming |

##### Keywords:

ant colony optimization; resource constrained job scheduling; parallel ant colony optimization; simulated annealing
PDF
BibTeX
XML
Cite

\textit{D. Thiruvady} et al., Ann. Oper. Res. 242, No. 2, 355--372 (2016; Zbl 1350.90013)

Full Text:
DOI

##### References:

[1] | Aarts, EHL; Korst, JHM; Laarhoven, PJM; Lenstra, JK (ed.), Simulated annealing, 91-120, (1997), Local Search in Combinatorial Optimization · Zbl 0905.90140 |

[2] | Ballestin, F; Trautmann, N, An iterated-local-search heuristic for the resource-constrained weighted earliness-tardiness project scheduling problem, International Journal of Production Research, 46, 6231-6249, (2008) · Zbl 1154.90353 |

[3] | Bertsimas, D; Tsitsiklis, J, Simulated annealing, Statistical Science, 8, 10-15, (1993) |

[4] | Blum, C; Roli, A, Metaheuristics in combinatorial optimization: overview and conceptual comparison, ACM Computing Surveys, 35, 268-308, (2003) |

[5] | Brucker, P; Drexl, A; Mohring, R; Neumann, K; Pesch, E, Resource-constrained project scheduling: notation, classification, models, and methods, European Journal of Operational Research, 112, 3-41, (1999) · Zbl 0937.90030 |

[6] | Chang, YL; Chen, KS; Huang, B; Chang, WY; Benediktsson, J; Chang, L, A parallel simulated annealing approach to band selection for high-dimensional remote sensing images, IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 4, 579-590, (2011) |

[7] | Czech, ZJ., Czarnas, P. (2002). Parallel simulated annealing for the vehicle routing problem with time windows. In 10th Euromicro workshop on parallel, distributed and network-based processing, pp. 376-383. |

[8] | Dagum, L; Menon, R, Openmp: an industry standard API for shared-memory programming, Computational Science Engineering, IEEE, 5, 46-55, (1998) |

[9] | Delisle, P., Krajecki, M., Gravel, M., Gagné, C. (2001). Parallel implementation of an ant colony optimization metaheuristic with OpenMP. In International conference on parallel architectures and compilation techniques, proceedings of the 3rd European workshop on OpenMP (EWOMP’01). · Zbl 1225.90162 |

[10] | Dorigo, M. (1992). Optimization, learning and natural algorithms. PhD thesis, Dip. Elettronica. · Zbl 1168.90660 |

[11] | Dorigo, M; Gambardella, LM, Ant colony system: A cooperative learning approach to the traveling salesman problem, IEEE Transactions On Evolutionary Computation, 1, 53-66, (1997) |

[12] | Dorigo, M., & Stűtzle, T. (2004). Ant colony optimization. Cambridge, Massachusetts: MIT Press. · Zbl 1092.90066 |

[13] | Ellabib, I; Calamai, P; Basir, O, Exchange strategies for multiple ant colony system, Information Sciences, 177, 1248-1264, (2007) |

[14] | Ernst, AT., Singh, G. (2012). Lagrangian particle swarm optimization for a resource constrained machine scheduling problem. In 2012 IEEE congress on evolutionary computation (CEC), pp. 1-8. · Zbl 1154.90353 |

[15] | Kirkpatrick, S; Gelett, C; Vecchi, M, Optimization by simulated annealing, Science, 220, 221-230, (1983) · Zbl 1225.90162 |

[16] | Ling, C., Hai-Ying, S., Shu, W. (2012). A parallel ant colony algorithm on massively parallel processors and its convergence analysis for the travelling salesman problem. Information Sciences, 199:31-42. doi:10.1016/j.ins.2012.02.055, WOS: 000304221600003. · Zbl 1248.90076 |

[17] | Onbaşoğlu, E; Özdamar, L, Parallel simulated annealing algorithms in global optimization, Journal of Global Optimization, 19, 27-50, (2001) · Zbl 1168.90660 |

[18] | Ram, JD; Sreenivas, TH; Subramaniam, GK, Parallel simulated annealing algorithms, Journal of Parallel Distributed Computing, 37, 207-212, (1996) |

[19] | Randall, M; Lewis, A, A parallel implementation of ant colony optimization, Journal of Parallel and Distributed Computing, 62, 1421-1432, (2002) · Zbl 1063.68095 |

[20] | Singh, G; Ernst, AT, Resource constraint scheduling with a fractional shared resource, Operations Research Letters, 39, 363-368, (2011) · Zbl 1235.90067 |

[21] | Singh, G., Weiskircher, R. (2008). Collaborative resource constraint scheduling with a fractional shared resource. In 2008 IEEE/WIC/ACM international conference on web intelligence and intelligent agent technology, IEEE, Vol. 2, pp. 359-365. |

[22] | Singh, G; Weiskircher, R, A multi-agent system for decentralised fractional shared resource constraint scheduling, Web Intelligence and Agent Systems, 9, 99-108, (2011) |

[23] | Stűtzle, T., López-Ibáñez, M., & Dorigo, M. (2010). A concise overview of applications of ant colony optimization. London: Wiley. |

[24] | Thiruvady, D; Singh, G; Ernst, AT; Meyer, B, Constraint-based ACO for a shared resource constrained scheduling problem, International Journal of Production Economics, 141, 230-242, (2012) |

[25] | Valls, V; Quintanilla, S; Ballestin, F, Resource-constrained project scheduling: A critical activity reordering heuristic, European Journal of Operational Research, 149, 282-301, (2003) · Zbl 1032.90011 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.