Abstract
Hybrid methods are highly effective means of solving combinatorial optimization problems and have become increasingly popular. In particular, integrations of exact and incomplete methods have proved to be effective where the hybrid takes advantage of the relative performance of each individual method. However, these methods often require significant run-times to determine good feasible solutions. One way of reducing run-times is to parallelize these algorithms. For large NP-hard problems, parallelization must be done with care, since changes to the algorithm can affect its performance in unpredictable ways. In this paper we develop two parallel variants of constraint-based ACO and test them on a problem arising in the Australian mining industry. We demonstrate that parallelization significantly reduces run times with each parallel variant providing advantages with respect to feasibility and solution quality.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The CP solver maintains all the constraints in the system. A job j is posted to the solver and either success or failure is returned.
References
Amdahl, G.M.: Validity of the single processor approach to achieving large scale computing capabilities. In: Proceedings of the April 18–20, 1967, Spring Joint Computer Conference, AFIPS 1967 (Spring), pp. 483–485. ACM, New York (1967)
Ballestín, F., Trautmann, N.: An iterated-local-search heuristic for the resource-constrained weighted earliness-tardiness project scheduling problem. Int. J. Prod. Res. 46, 6231–6249 (2008)
Blum, C.: Beam-ACO: hybridizing ant colony optimization with beam search: an application to open shop scheduling. Comput. Oper. Res. 32, 1565–1591 (2005)
Blum, C., Roli, A.: Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Comput. Surv. 35, 268–308 (2003)
Brucker, P., Drexl, A., Mohring, R., Neumann, K., Pesch, E.: Resource-constrained project scheduling: notation, classification, models, and methods. Eur. J. Oper. Res. 112, 3–41 (1999)
Chapman, B., Jost, G., van der Pas, R.: Using OpenMP: Portable Shared Memory Parallel Programming (Scientific and Engineering Computation). The MIT Press, Cambridge (2007)
Delisle, P., Krajecki, M., Gravel, M., Gagné, C.: Parallel implementation of an ant colony optimization metaheuristic with OpenMP. In: Proceedings of the 3rd European Workshop on OpenMP of International Conference on Parallel Architectures and Compilation Techniques (EWOMP 2001) (2001)
Ellabib, I., Calamai, P., Basir, O.: Exchange strategies for multiple ant colony system. Inf. Sci. 177(5), 1248–1264 (2007)
Ling, C., Hai-Ying, S., Shu, W.: A parallel ant colony algorithm on massively parallel processors and its convergence analysis for the travelling salesman problem. Inf. Sci. 199, 31–42 (2012). WOS: 000304221600003
López-Ibáñez, M., Blum, C., Thiruvady, D., Ernst, A.T., Meyer, B.: Beam-ACO based on stochastic sampling for makespan optimization concerning the TSP with time windows. In: Cotta, C., Cowling, P. (eds.) EvoCOP 2009. LNCS, vol. 5482, pp. 97–108. Springer, Heidelberg (2009). doi:10.1007/978-3-642-01009-5_9
Marriott, K., Stuckey, P.: Programming with Constraints. MIT Press, Cambridge (1998)
Pedemonte, M., Nesmachnow, S., Cancela, H.: A survey on parallel ant colony optimization. Appl. Soft Comput. 11(8), 5181–5197 (2011)
Randall, M., Lewis, A.: A parallel implementation of ant colony optimization. J. Parallel Distrib. Comput. 62(9), 1421–1432 (2002)
Ravishankar, M.K.: Parallel implementation of fast beam search for speaker-independent continuous speech recognition (1993)
Singh, G., Ernst, A.T.: Resource constraint scheduling with a fractional shared resource. Oper. Res. Lett. 39(5), 363–368 (2011)
Stűtzle, T., López-Ibáñez, M., Dorigo, M.: A Concise Overview of Applications of Ant Colony Optimization. Wiley, New York (2010)
Thiruvady, D., Blum, C., Meyer, B., Ernst, A.: Hybridizing beam-ACO with constraint programming for single machine job scheduling. In: Blesa, M.J., Blum, C., Gaspero, L., Roli, A., Sampels, M., Schaerf, A. (eds.) HM 2009. LNCS, vol. 5818, pp. 30–44. Springer, Heidelberg (2009). doi:10.1007/978-3-642-04918-7_3
Thiruvady, D., Ernst, A.T., Singh, G.: Parallel ant colony optimization for resource constrained job scheduling. Ann. Oper. Res. 242, 1–18 (2014)
Thiruvady, D., Meyer, B., Ernst, A.T.: Car sequencing with constraint-based ACO. In: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation, GECCO 2011, pp. 163–170. ACM, New York (2011)
Thiruvady, D., Singh, G., Ernst, A.T., Meyer, B.: Constraint-based ACO for a shared resource constrained scheduling problem. Int. J. Prod. Econ. 141(1), 230–242 (2013). Meta-heuristics for manufacturing scheduling and logistics problems
Valls, V., Quintanilla, S., Ballestín, F.: Resource-constrained project scheduling: a critical activity reordering heuristic. Eur. J. Oper. Res. 149, 282–301 (2003)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Cohen, D., Gómez-Iglesias, A., Thiruvady, D., Ernst, A.T. (2017). Resource Constrained Job Scheduling with Parallel Constraint-Based ACO. In: Wagner, M., Li, X., Hendtlass, T. (eds) Artificial Life and Computational Intelligence. ACALCI 2017. Lecture Notes in Computer Science(), vol 10142. Springer, Cham. https://doi.org/10.1007/978-3-319-51691-2_23
Download citation
DOI: https://doi.org/10.1007/978-3-319-51691-2_23
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-51690-5
Online ISBN: 978-3-319-51691-2
eBook Packages: Computer ScienceComputer Science (R0)