Pre-prints
Published works
Short-term scheduling of production fleets in underground mines using CP-based LNS,
Max Åstrand, Mikael Johansson, Hamid Reza Feyzmahdavian
CPAIOR 2021: Integration of Constraint Programming, Artificial Intelligence, and Operations Research
Expand abstract
Coordinating the mobile production fleet in underground mines becomes increasingly important as the machines are more and more automated. We present a scheduling approach that applies to several of the most important production methods used in underground mines. Our algorithm combines constraint programming with a large neighborhood search strategy that dynamically adjusts the neighborhood size. The resulting algorithm is complete and able to rapidly improve constructed schedules in practice. In addition, it has important benefits when it comes to the acceptance of the approach in real-life operations. Our approach is evaluated on public and private industrial problem instances representing different mines and production methods. We find significant improvements over the current industrial practice.
Automatic closed-loop scheduling in underground mining using discrete event simulation,
B. Skawina, M. Åstrand, F. Sundqvist, J. Greberg, A. Salama, P. Ekbeck
Journal of the Southern African Institute of Mining and Metallurgy 2021
Expand abstract
Today’s mining operations require fast reporting and rapid rescheduling based on updated information. An automatic mine scheduling system could not only quickly reschedule but also propose alternative solutions. To avoid the financial and physical risks associated with testing such a system directly in operation, it could be first evaluated via discrete event simulation models. This would offer a safe environment to evaluate different operating rules and algorithms. In this study, this is achieved by integrating automatic scheduling software with a discrete event simulation model.
Short-term Underground Mine Scheduling: An Industrial Application of Constraint Programming (doctoral thesis),
Max Åstrand
KTH Royal Institute of Technology 2021
Expand abstract
The mining industry is facing a surge in automation in the pursuit of safe and profitable operations. As the excavation process is increasingly automated, today’s mining companies seek to optimize the coordination of the now automated mining activities. This coordination is called short-term mine scheduling, and it is the process of allocating resources and determining feasible start and end times for the upcoming mining activities. Unfortunately, current industrial practice relies heavily on manual labor, making the performance critically dependent on the expertise of the individual scheduler. In this thesis, we study how to automate the short-term mine scheduling process to increase the efficiency in a vital part of the underground mine planning chain.
First, the short-term underground mine scheduling problem is detailed, and the surrounding operational context is clarified. Central aspects of the excavation process are shown to be adequately described by a scheduling abstraction known as a hybrid flow shop. We demonstrate that some popular mine production methods can be considered rich variants of a k-stage hybrid flow shop exhibiting a mix of interruptible and uninterruptible activities, sequence-dependent setup times, and sharing of machines between stages.
An approach based on constraint programming is then presented that can be used for short-term scheduling in underground mines. For mines that have vast underground road networks, it is important to consider the travel times needed for the mobile machines between subsequent activities. The proposed extension of the first approach can unfortunately only solve small instances in reasonable computation times. To solve industrially relevant problem sizes, we introduce a second approach. The second approach does not solve the interruptible scheduling problem directly; instead, it solves a related uninterruptible problem and transforms the solution back to the original time domain. It is significantly faster than the first approach and can be used to solve larger instances, even when including travel times. The second approach is also extended to support more general mining scenarios that cannot be described as hybrid flow shops.
To improve the quality of the schedules, we introduce a domain-specific neighborhood definition that is used in large neighborhood search. Initially, different fixed neighborhood sizes are investigated. Upon observing that there is no clear dominant strategy, we propose an algorithm for dynamically adjusting the size of the explored neighborhoods. The constructed schedules are improved rapidly using the proposed algorithm, which also introduces local optimality properties that are beneficial when it comes to industrial acceptance. For all models and methods presented in this thesis, we perform extensive numerical evaluations on problem instances derived from operational underground mines.
This thesis is concluded by presenting practical experiences from automating the short-term scheduling process in underground mines. Assumptions and design choices are motivated by earlier experiences from using simpler scheduling algorithms. Finally, senior mine schedulers from two different mine sites assess the real-life applicability of the final scheduling approach.
A Neighborhood Selection Strategy for Production Scheduling using CP and LNS,
Max Åstrand, Mikael Johansson,
2020 25th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA)
Expand abstract
High-quality production scheduling is increasingly important in modern industry operations. We study a class of scheduling problems where jobs take place at predefined locations, as is common in mining, forestry and logistics. The proposed neighborhood selection algorithm is able to find high- quality solutions fast and guarantees that a globally optimal solution is eventually found. Preliminary results are promising.
Underground mine scheduling of mobile machines using Constraint Programming and Large Neighborhood Search,
Max Åstrand, Mikael Johansson, Alessandro Zanarini,
Computers & Operations Research 2020
Expand abstract
Manual short-term scheduling in underground mines is a time-consuming and error-prone activity. In this work, we present a Constraint Programming approach capable of automating the short-term scheduling process in a cut-and-fill mine. The approach extends previous work by accounting for fleet travel times, and thus captures an important aspect of the real-world machine scheduling problem. We introduce two models: one that directly solves the original interruptible scheduling problem, and one that is based on solving a related uninterruptible scheduling problem and transforming its solution back to the original domain. Large Neighborhood Search is also employed with a domain-specific neighborhood definition that helps to find high-quality schedules faster. Problem instances derived from an operational mine are used to demonstrate the efficacy of our approach.
A System for Underground Road Condition Monitoring,
Max Åstrand, Erik Jakobsson, Martin Lindfors, John Svensson,
International Journal of Mining Science and Technology 2020
Expand abstract
Poor road conditions in underground mine tunnels can lead to decreased production efficiency and increased wear on production vehicles. A prototype system for road condition monitoring is presented in this paper to counteract this. The system consists of three components i.e. localization, road monitoring, and scheduling. The localization of vehicles is performed using a Rao-Blackwellized extended particle filter, combining vehicle mounted sensors with signal strengths of WiFi access points. Two methods for road monitoring are described: a Kalman filter used together with a model of the vehicle suspension system, and a relative condition measure based on the power spectral density. Lastly, a method for taking automatic action on an ill-conditioned road segment is proposed in the form of a rescheduling algorithm. The scheduling algorithm is based on the large neighborhood search and is used to integrate road service activities in the short-term production schedule while minimizing introduced production disturbances. The system is demonstrated on experimental data collected in a Swedish underground mine. See also: short video!
Poster: Short-term Mine Scheduling using Constraint Programming,
Max Åstrand, Mikael Johansson, Alessandro Zanarini,
WASP Winter Conference 2020
Expand abstract
Manual short-term scheduling in underground mines is a time-consuming and error prone activity. We use Constraint Programming to automate the scheduling process: deciding what to do where and when. We extend previous work by including fleet travel times, and by introducing a new model based on solving a related scheduling problem and transforming its solution back to the original domain. In addition, a neighborhood definition is introduced to optimize using Large Neighborhood Search. Results show that the proposed method scales to realistic problem sizes, and that the solutions obtained are of high-quality.
Developing a Tool for Automatic Mine Scheduling ,
Kateryna Mishchenko, Max Åstrand, Mats Molander, Rickard Lindkvist, Torbjörn Viklund
28th International Symposium on Mine Planning & Equipment Selection (MPES2019)
Expand abstract
Presented is an automated short-term scheduling for underground mines which is an important part of the overall mining process. The presented algorithm is a constructive heuristics applied for scheduling of the production cycles of a cut-and-fill mine. The goal of the heuristics is to minimize the finishing times for each task. To achieve this, the tasks as scheduled as early as possible. The automated schedules were validated at the New Boliden mine both in offline and online tests and now the algorithm is going through later steps of product development. The main result is the creation of high quality schedules, outperforming existing manual ones in terms of both computational time and quality. The auto scheduler was tested and compared to manual scheduling. The results show a 10% increase in ore production and produce always feasible schedules with respect to all operational limitations. Thereat, the automated algorithms take minutes versus hours for manual scheduling.
Reinforcement Learning for Grinding Circuit Control in Mineral Processing ,
Mattias Hallén, Max Åstrand, Johannes Sikström, Martin Servin
2019 24th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA)
Expand abstract
Grinding, i.e. reducing the particle size of mined ore, is often the bottleneck of the mining concentrating process. Thus, even small improvements may lead to large increases in profit. The goal of the grinding circuit is two-sided; to maximize the throughput of ore, and minimize the resulting particle size of the ground ore within some acceptable range. In this work we study the control of a two-stage grinding circuit using reinforcement learning. To this end, we present a solution for integrating industrial simulation models into the reinforcement learning framework OpenAI Gym.We compare an existing PID controller, based on vast domain knowledge and years of hand-tuning, with a black-box algorithm called Proximal Policy Optimization on a calibrated grinding circuit simulation model. The comparison show that it is possible to control the grinding circuit using reinforcement learning. In addition, contrasting reinforcement learning from the existing PID control, the algorithm is able to maximize an abstract control goal: maximizing profit as defined by a profit function given by our industrial collaborator. In some operating cases the algorithm is able to control the plant more efficiently compared to existing control.
Short-term Underground Mine Scheduling: Constraint Programming in an Industrial Application (licentiate thesis),
Max Åstrand,
KTH Royal Institute of Technology 2018
Expand abstract
The operational performance of an underground mine depends critically on how the production is scheduled. Increasingly advanced methods are used to create optimized long-term plans, and simultaneously the actual excavation is getting more and more automated. Therefore, the mapping of long-term goals into tasks by manual short-term scheduling is becoming a limiting segment in the optimization chain. In this thesis we study automating the short-term mine scheduling process, and thus contribute to an important missing piece in the pursuit of autonomous mining. First, we clarify the fleet scheduling problem and the surrounding context. Based on this knowledge, we propose a flow shop that models the mine scheduling problem. A flow shop is a general abstract process formulation that captures the key properties of a scheduling problem without going into specific details. We argue that several popular mining methods can be modeled as a rich variant of a k-stage hybrid flow shop, where the flow shop includes a mix of interruptible and uninterruptible tasks, after-lags, machine unavailabilities, and sharing of machines between stages. Then, we propose a Constraint Programming approach to schedule the underground production fleet. We formalize the problem and present a model that can be used to solve it. The model is implemented and evaluated on instances representative of medium-sized underground mines. See feedback.
Fleet Scheduling in Underground Mines using Constraint Programming,
Max Åstrand, Mikael Johansson and Alessandro Zanarini
CPAIOR 2018: Integration of Constraint Programming, Artificial Intelligence, and Operations Research
Expand abstract
The profitability of an underground mine is greatly affected by the scheduling of the mobile production fleet. Today, most mine operations are scheduled manually, which is a tedious and error-prone activity. In this contribution, we present and formalize the underground mine scheduling problem, and propose a CP-based model for solving it. The model is evaluated on instances generated from real data. The results are promising and show a potential for further extensions.
Underground mine scheduling modeled as a flow shop: a review of relevant works and future challenges,
Max Åstrand, Mikael Johansson and Jenny Greberg,
Journal of the Southern African Institute of Mining and Metallurgy
Expand abstract
Planning and automation is increasingly important in modern mines. Sophisticated methods for long-term mine planning are often used, and the uprise of autonomous machines makes the actual operation more predictable. However, the interface between these two time scales, i.e. the scheduling of the mobile production fleet, is often limiting the ability to operate mines at maximum profitability. We show how scheduling the production fleet in an underground mine can be modeled as a flow shop. A flow shop is a general abstract process formulation that captures the key properties of a scheduling problem without going into specific details. Thus, the flow shop enables mine scheduling to reap the benefits of scheduling research from other industries. Further, we review recent results from the mining community and the flow shop community, and introduce scheduling methods used in these two fields. This work aims at providing value both to researchers from the mining community who want to leverage their skillset, but also to theoretical researchers by presenting the mining process as a potential application area. Lastly, we end the paper with a discussion of the results, and with some future challenges and opportunities facing the industry.
Surrogate Models for Design and Study of Underground Ventilation,
Max Åstrand, Kari Saarinen, Shiva Sander-Tavallaey,
IEEE Conference on Emerging Technologies and Factory Automation 2017
Expand abstract
Ventilation is vital for the production in an underground mine. Therefore, it is important to have efficient and accurate design tools in order to ensure and optimize the airflows in the mine. There are several commercial software for airflow simulation based on first principles. However, the computational cost of simulation together with integrational obstacles when connecting simulation to control strategies limits the benefit of these tools. In this paper an approach utilizing surrogate models as a complementary design tool is presented. It is shown that using surrogate models one can with rather low computational expense evaluate and benchmark different control strategies. It is also shown that the models can be used for identifying possible bottlenecks in the system in advance. Moreover, the use of surrogate models transfer the simulation into a development-friendly environment (such as Matlab). A test case is used based on a real underground mine ventilation design. Two types of surrogate models are fitted to process data; multiple least squares regression and a Gaussian process model. Sensitivity analysis on the surrogate shows the potential of using surrogate models for identifying bottlenecks. Furthermore, the surrogate is used to benchmark two different control strategies for mine ventilation.
Poster: Optimal Scheduling in Underground Mining,
Max Åstrand, Mikael Johansson, Kateryna Mishchenko,
WASP Winter Conference 2016
Expand abstract
Underground mining comprises a range of activities, from rock excavation tasks (such as drilling, charging and blasting) to support functions (including managing the inflow of water, ventilating blast fumes, and building the necessary infrastructure). Automation in underground mining has previously focused on fixed equipment such as mine hoists, crushers, and conveyor belts. For underground mines to reach high productivity automatic scheduling of the mobile production system must be considered.
Ventilation Performance Monitoring in Underground Mines,
Max Åstrand,
Umeå University, Department of Physics
Expand abstract
Ventilation of underground mines is a critical, complex and expensive activity. Removing pollutants from e.g. diesel equipment is important to ensure a safe and operable work environment in the mine. The energy consumption of ventilation for an underground mine typically comprises around 30-50% of the total energy consumption of underground mine operation. It is therefore vital that the performance of the ventilation system can be monitored and maintained as high as possible. The goal of this project is to develop methods and algorithms which are useful in this context. The methods are based on surrogate modeling, statistical process monitoring techniques, and model predictive control. The developed methods and algorithms are tested in two real mine case studies