Adaptive Artificial Intelligence Scheduling Methods for Large-Scale, Stochastic, Industrial Applications

1 Problem Statement

Many real-world industrial problems are NP-hard, in particular, in the area of planning and scheduling. This is bad news, as it is considered unlikely that an algorithm whose running time is polynomial in the size of the input exists [Gasarch, 2019]. As we don't have such an algorithm to compute goodquality solutions in an acceptable time, we can apply combinatorial optimization techniques such as constraint, mixedinteger, or answer set programming. While such methods can successfully perform small problem instances, they often fail to scale up to large industrial instances.

A weakness of general problem-solving techniques is their generic approach, which does not exploit the specificities of a problem domain and instead applies rigid search methods independently of instance characteristics to derive information about the instance during solving without reusing it. Hence, traditional combinatorial optimization techniques cannot take advantage of the similarities between instances of industrial scheduling problems. In particular, factories are rather static entities in which machines, workers, production capacity, and produced goods are often very similar from one schedule to another.

Moreover, recurring planning and scheduling tasks are often linked, e.g., when an existing schedule needs to be changed or extended in view of specific events like operational disruptions, new production orders, etc. Traditional techniques do not consider scheduling as a continuous task. They assume instances to be deterministic and independent of each other, limiting their modeling and solving capacities to coarse abstractions of the real world. In practice, however, factories handle many stochastic events such as the processing times of jobs, varying relative to worker skills, operational and transport delays, etc., or machine breakdowns [Hassoun et al., 2019]. Finally, traditional combinatorial optimization techniques only benefit little from the high parallelism capacities of modern CPUs. The improvements due to allocating more CPUs are often marginal and absorbed by some inherently sequential bottleneck tasks like, e.g., pre-solving in constraint programming 1 . As with mixed-integer programming solvers, using a single CPU can sometimes result in better solutions than parallel solving on multiple CPUs 2 . Such behavior is problematic as modern CPUs boost computing performance through high concurrency, exploiting an increasing number of cores [Sutter, 2005]. Reinforcement Learning (RL) is an area of Machine Learning (ML) where an autonomous agent operates in an environment and learns, based on experimentation, how to optimize a quantitative reward over time. At each iteration, the agent observes the environment, selects an action, performs it, and receives a reward that corresponds to the impact of the actions taken on the desired outcome. For any state, the agent then aims to identify the action that maximizes the expected cumulative rewards for the given task. Such a mapping from states to actions, called policy, can be viewed as a heuristic for achieving a desirably high reward at the end of an episode. Recently, the combination of RL with deep learning (DRL) has been the source of breakthroughs in Artificial Intelligence. These success stories include winning against the world's best GO player [Silver and et al., 2016], super-human performance on Atari's games [Mnih and et al., 2013], and beating human professional players on the complex, information-imperfect, realtime game Dota2 [Berner and et al., 2019]. In view of such showcases, researchers soon recognized the potential of DRL for practically important Combinatorial Optimization Problems (COPs) [Bengio et al., 2021].

1 https://github.com/google/or-tools/issues/1588

2 https://gurobi.com/documentation/9.1/refman/threads.html

2 Contributions

In [Tassel and Rbaia, 2021], we initially leverage problem properties and propose a decomposition of the Aircraft Routing and Maintenance Planning problem. We propose a multishot Answer Set Programming (ASP) model which incrementally increases the allowed on-ground time between two flights at each iteration. As a result, compared to the original, single-shot ASP model, we found solutions of 40% lower cost while dividing the runtime by 3.

In [Tassel et al., 2021], we designed an optimized reinforcement learning environment for the job-shop scheduling problem [Taillard, 1993]. We could outperform state-of-theart reinforcement learning approaches when training a simple PPO agent with a multi-layer perceptron network. However, compared to traditional approaches such as Constraint Programming (CP), we could not improve their performance. The state-space is instance dependent (i.e., depends on the number of jobs to schedule) which can reduce the applicability of our approach.

In [Kov´acs et al., 2021], we developed a heuristic and an Integer Linear Programming (ILP) and CP model to solve a large-scale, industrial Resource-Constrained Project Scheduling Problem (RCPS). Compared to previous RCPS approaches, focusing on small academic benchmarks of less than 100 jobs to allocate, our meta-heuristic combining a heuristic and a CP model could solve industrial instances with more than 6000 jobs. This work has been done in collaboration with an industrial partner.

In [Tassel et al., 2022], we proposed a new and efficient Markov Decision Process (MDP) formulation for scheduling problems, where the state-transition function considers sequences rather than a fixed number of actions. Closely related to dispatching heuristics. We also proposed a training approach using Evolution Strategies to train a neural network to dispatch jobs. Combined with a Beam-Search solution generator, it provides better results than the previously proposed meta-heuristic while reducing the time needed by a factor of 60.

In [Kov´acs et al., 2022], we developed a realistic simulation of a semiconductor factory. This work provides a scalable, open-source tool for simulating semiconductor factories and encouraging the development of new scheduling methods.

3 Conclusion

During the first two years of my Ph.D., I focused on developing adaptive scheduling methods to leverage challenging industrial scheduling problems. My recent work focused on reinforcement learning and simulation produced encouraging results. In future works, I want to further improve the methods I have already developed and combine them with traditional scheduling techniques such as CP.