Adaptive population-based simulated annealing for resource constrained job scheduling with uncertainty

Abstract

Transporting ore from mines to ports is of significant interest in mining supply chains. These operations are commonly associated with growing costs and a lack of resources. Large mining companies are interested in optimally allocating resources to reduce operational costs. This problem has been previously investigated as resource constrained job scheduling (RCJS). While a number of optimisation methods have been proposed to tackle the deterministic problem, the uncertainty associated with resource availability, an inevitable challenge in mining operations, has received less attention. RCJS with uncertainty is a hard combinatorial optimisation problem that is challenging for existing optimisation methods. We propose an adaptive population-based simulated annealing algorithm that can overcome existing limitations of methods for RCJS with uncertainty, including pre-mature convergence, excessive number of hyper-parameters, and the inefficiency in coping with different uncertainty levels. This new algorithm effectively balances exploration and exploitation, by using a population, modifying the cooling schedule in the Metropolis-Hastings algorithm, and using an adaptive mechanism to select perturbation operators. The results show that the proposed algorithm outperforms existing methods on a benchmark RCJS dataset considering different uncertainty levels. Moreover, new best known solutions are discovered for all but one problem instance across all uncertainty levels.

KEYWORDS:

• Resource constrained job scheduling
• uncertainty
• simulated annealing
• adaptive perturbation
• mining

Disclosure statement

No potential conflict of interest was reported by the author(s).

Data availability statement

The authors confirm that the data supporting the findings of this study are available within the article.

Notes

1 https://www.minerals.org.au/news/mining-largest-contributor-australian-economy-2019-20.

2 https://www.austrade.gov.au/ArticleDocuments/2814/Mining-software-and-specialised-technologies-Industry-capability-report.pdf.aspx.

3 Benchmark datasets obtained from the project scheduling problem library (PSPLIB) (Kolisch and Sprecher 1997).

4 We refer the reader to the study by Thiruvady et al. (2022) for a detailed discussion of uncertainty in respect to this problem.

5 Note, evolutionary algorithms have been investigated for RCJSU (Thiruvady et al. 2022), but have not proved successful. Hence, we do not directly compare APSA to these approaches in this study.

6 https://github.com/andreas-ernst/Mathprog-ORlib/blob/master/data/RCJS_Instances.zip consists of problem instances for RCJS. The resource usage within the problem instances is modified to generate problem instances for RCJSU (Thiruvady et al. 2022).

7 These settings are obtained by considering resource utilisation and complexity observed from the real-world situations investigated in Singh and Ernst (2011).

8 https://confluence.apps.monash.edu/display/monarch/MonARCH+Home.

9 Full details of the algorithm can be found in Singh and Ernst (2011), and due to space limitations, we do not provide the full algorithm or its description here.

Additional information

Notes on contributors

Dhananjay Thiruvady

Dhananjay Thiruvady is Associate Head of School (Industry Research) and Senior Lecturer (Mathematics and Optimisation) at the School of IT, Deakin University. He received his PhD in Optimisation from Monash University, Australia, in 2012. His expertise is in developing methods derived from artificial intelligence (constraint programming, nature-based meta-heuristics, Bayesian networks) and mathematical programming. He works at the interface of academia and industry and has applied the techniques he has developed to mining, scheduling, health and biosecurity. He has published over 60 journal and conference papers in high-ranked venues such as IEEE Transactions on Evolutionary Computation, International Journal of Production Research, Computers and Operations Research and International Journal of Production Economics. He serves on the program committees of conferences such as Genetic and Evolutionary Computation Conference and the Australasian Data Mining Conference.

Su Nguyen

Su Nguyen is a Senior Lecturer (AI and Analytics) at RMIT University, Australia. He received his Ph.D. degree in Artificial Intelligence and Operations Research from Victoria University of Wellington (VUW), Wellington, New Zealand, in 2013. His expertise includes simulation-optimisation, evolutionary computation, automated algorithm design, interfaces of artificial intelligence and operations research, and their applications in logistics, energy, and transportation. Nguyen has a strong track record in developing simulation models, simulation-based decision support tools, and simulation-optimisation algorithms for industry applications. He has 70+ publications in top peer-reviewed journals and conferences in computational intelligence and operations research. His current research focuses on hybrid intelligence systems that combine the power of modern artificial intelligence technologies and operations research methodologies. He was the chair (2014-2018) of IEEE task force on Evolutionary Scheduling and Combinatorial Optimisation and is a member of IEEE CIS Data Mining and Big Data technical committee. He delivered tutorials about evolutionary simulation-optimisation and AI-based visualisation at Parallel Problem Solving from Nature Conference (2018), IEEE World Congress on Computational Intelligence (2020), and Genetic and Evolutionary Computation Conference (2022).

Yuan Sun

Yuan Sun is a Lecturer in Business Analytics and Artificial Intelligence at La Trobe University, Australia. He received his BSc in Applied Mathematics from Peking University, China, and his PhD in Computer Science from The University of Melbourne, Australia. His research interest is on artificial intelligence, machine learning, operations research, and evolutionary computation. He has contributed significantly to the emerging research area of leveraging machine learning for combinatorial optimisation. His research has been published in top-tier journals and conferences such as IEEE TPAMI, IEEE TEVC, EJOR, NeurIPS, ICLR, VLDB, ICDE, and AAAI.

Fatemeh Shiri

Fatemeh Shiri is a research fellow in the Vision and Language discipline group at the Faculty of IT, Monash University. She completed her studies at the Australian National University and Data61-CSIRO, where she developed deep learning approaches for computer vision tasks and time-series data. She has a strong background in computer vision, natural language processing, and machine learning, and has published in high-ranking conferences and journals, including IEEE Transactions on Pattern Analysis and Machine Intelligence and International Journal of Computer Vision. She has collaborated extensively with industry partners, particularly in projects involving natural language processing with DSTG (Defence Science and Technology Group).

Nayyar Zaidi

Nayyar Zaidi is a member of Centre for Cyber Resilience and Trust (CREST) at Deakin University and leads AI activities of the group. He works as Sr. Lecturer at Deakin University, Burwood, Australia. Dr. Zaidi is a distinguished researcher in Machine Learning and Artificial Intelligence, and has a track record of publishing in top journals such as 'Journal of Machine Learning Research', 'Springer Machine Learning', 'Springer DMDK', etc. His pure research constitutes topics in ‘data generation’, ‘robust machine learning’, ‘large-scale machine learning’, and ‘effective feature engineering’. His applied research is focussed on ‘network security anomaly detection’, ‘human dialogue evaluation, ‘financial risk management’, etc. He has published over 40 peer-reviewed articles and serves as program committee member for major conferences such as IEEE ICDM, KDD, IJCAI, SDM, PAKDD and many others.

Xiaodong Li

Xiaodong Li received his Ph.D. degree in Artificial Intelligence from University of Otago, Dunedin, New Zealand. He is a professor in Artificial Intelligence currently with the School of Computing Technologies, RMIT University, Melbourne, Australia. His research interests include machine learning, evolutionary computation, data mining/analytics, multiobjective optimisation, multimodal optimisation, large-scale optimisation, deep learning, math-heuristic methods, and swarm intelligence. He served as an Associate Editor of journals including IEEE Transactions on Evolutionary Computation, Swarm Intelligence (Springer), and International Journal of Swarm Intelligence Research. He is a founding member of IEEE CIS Task Force on Swarm Intelligence, a former vice-chair of IEEE Task Force on Multi-modal Optimization, and a former chair of IEEE CIS Task Force on Large Scale Global Optimization. He is the recipient of 2013 ACM SIGEVO Impact Award and 2017 IEEE CIS ‘IEEE Transactions on Evolutionary Computation Outstanding Paper Award’. He is an IEEE Fellow, and an IEEE CIS Distinguished Lecturer (2024–2026).