IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v242y2016i2d10.1007_s10479-014-1577-7.html
   My bibliography  Save this article

Parallel ant colony optimization for resource constrained job scheduling

Author

Listed:
  • Dhananjay Thiruvady

    (Monash University
    CSIRO Mathematics)

  • Andreas T. Ernst

    (CSIRO Mathematics)

  • Gaurav Singh

    (CSIRO Mathematics)

Abstract

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.

Suggested Citation

  • Dhananjay Thiruvady & Andreas T. Ernst & Gaurav Singh, 2016. "Parallel ant colony optimization for resource constrained job scheduling," Annals of Operations Research, Springer, vol. 242(2), pages 355-372, July.
    • Handle: RePEc:spr:annopr:v:242:y:2016:i:2:d:10.1007_s10479-014-1577-7
    DOI: 10.1007/s10479-014-1577-7
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-014-1577-7
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10479-014-1577-7?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Brucker, Peter & Drexl, Andreas & Mohring, Rolf & Neumann, Klaus & Pesch, Erwin, 1999. "Resource-constrained project scheduling: Notation, classification, models, and methods," European Journal of Operational Research, Elsevier, vol. 112(1), pages 3-41, January.
    2. Valls, Vicente & Quintanilla, Sacramento & Ballestin, Francisco, 2003. "Resource-constrained project scheduling: A critical activity reordering heuristic," European Journal of Operational Research, Elsevier, vol. 149(2), pages 282-301, September.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Sakineh Lakzaei & Donya Rahmani & Babak Mohamadpour Tosarkani & Sepideh Nasiri, 2023. "Integrated optimal scheduling and routing of repair crew and relief vehicles after disaster: a novel hybrid solution approach," Annals of Operations Research, Springer, vol. 328(2), pages 1495-1522, September.
    2. Kannan Govindan, 2016. "Evolutionary algorithms for supply chain management," Annals of Operations Research, Springer, vol. 242(2), pages 195-206, July.
    3. Schryen, Guido, 2020. "Parallel computational optimization in operations research: A new integrative framework, literature review and research directions," European Journal of Operational Research, Elsevier, vol. 287(1), pages 1-18.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Debels, Dieter & De Reyck, Bert & Leus, Roel & Vanhoucke, Mario, 2006. "A hybrid scatter search/electromagnetism meta-heuristic for project scheduling," European Journal of Operational Research, Elsevier, vol. 169(2), pages 638-653, March.
    2. Valls, Vicente & Ballestin, Francisco & Quintanilla, Sacramento, 2005. "Justification and RCPSP: A technique that pays," European Journal of Operational Research, Elsevier, vol. 165(2), pages 375-386, September.
    3. Weglarz, Jan & Józefowska, Joanna & Mika, Marek & Waligóra, Grzegorz, 2011. "Project scheduling with finite or infinite number of activity processing modes - A survey," European Journal of Operational Research, Elsevier, vol. 208(3), pages 177-205, February.
    4. D. Debels & M. Vanhoucke, 2005. "A Decomposition-Based Heuristic For The Resource-Constrained Project Scheduling Problem," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/293, Ghent University, Faculty of Economics and Business Administration.
    5. Valls, Vicente & Ballestin, Francisco & Quintanilla, Sacramento, 2008. "A hybrid genetic algorithm for the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 185(2), pages 495-508, March.
    6. M. Vanhoucke, 2007. "A genetic algorithm to investigate the trade-off between project lead time and net present value," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 07/456, Ghent University, Faculty of Economics and Business Administration.
    7. Coelho, José & Vanhoucke, Mario, 2011. "Multi-mode resource-constrained project scheduling using RCPSP and SAT solvers," European Journal of Operational Research, Elsevier, vol. 213(1), pages 73-82, August.
    8. Dieter Debels & Mario Vanhoucke, 2007. "A Decomposition-Based Genetic Algorithm for the Resource-Constrained Project-Scheduling Problem," Operations Research, INFORMS, vol. 55(3), pages 457-469, June.
    9. Thiruvady, Dhananjay & Singh, Gaurav & Ernst, Andreas T. & Meyer, Bernd, 2013. "Constraint-based ACO for a shared resource constrained scheduling problem," International Journal of Production Economics, Elsevier, vol. 141(1), pages 230-242.
    10. Debels, D. & Vanhoucke, M., 2006. "Meta-Heuristic resource constrained project scheduling: solution space restrictions and neighbourhood extensions," Vlerick Leuven Gent Management School Working Paper Series 2006-18, Vlerick Leuven Gent Management School.
    11. Tseng, Lin-Yu & Chen, Shih-Chieh, 2006. "A hybrid metaheuristic for the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 175(2), pages 707-721, December.
    12. Konstantinos G. Zografos & Michael A. Madas & Konstantinos N. Androutsopoulos, 2017. "Increasing airport capacity utilisation through optimum slot scheduling: review of current developments and identification of future needs," Journal of Scheduling, Springer, vol. 20(1), pages 3-24, February.
    13. Asbach, Lasse & Dorndorf, Ulrich & Pesch, Erwin, 2009. "Analysis, modeling and solution of the concrete delivery problem," European Journal of Operational Research, Elsevier, vol. 193(3), pages 820-835, March.
    14. Andrzej Kozik, 2017. "Handling precedence constraints in scheduling problems by the sequence pair representation," Journal of Combinatorial Optimization, Springer, vol. 33(2), pages 445-472, February.
    15. Xiong, Jian & Leus, Roel & Yang, Zhenyu & Abbass, Hussein A., 2016. "Evolutionary multi-objective resource allocation and scheduling in the Chinese navigation satellite system project," European Journal of Operational Research, Elsevier, vol. 251(2), pages 662-675.
    16. Rolf H. Möhring & Andreas S. Schulz & Frederik Stork & Marc Uetz, 2003. "Solving Project Scheduling Problems by Minimum Cut Computations," Management Science, INFORMS, vol. 49(3), pages 330-350, March.
    17. Ilkyeong Moon & Sanghyup Lee & Moonsoo Shin & Kwangyeol Ryu, 2016. "Evolutionary resource assignment for workload-based production scheduling," Journal of Intelligent Manufacturing, Springer, vol. 27(2), pages 375-388, April.
    18. Ranjbar, Mohammad & De Reyck, Bert & Kianfar, Fereydoon, 2009. "A hybrid scatter search for the discrete time/resource trade-off problem in project scheduling," European Journal of Operational Research, Elsevier, vol. 193(1), pages 35-48, February.
    19. Dorndorf, Ulrich & Drexl, Andreas & Nikulin, Yury & Pesch, Erwin, 2005. "Flight gate scheduling: State-of-the-art and recent developments," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 584, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    20. Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre (Ed.), 2000. "Jahresbericht 1999," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 522, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:annopr:v:242:y:2016:i:2:d:10.1007_s10479-014-1577-7. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.