Dynamic Optimization of Intralogistic Robot Scheduling

The employment of intralogistic robots in warehouses has become increasingly prevalent due to technological advancements; in fact, they enable more efficient logistic operations, increasing productivity and cost-effectiveness. The research community is showing a keen interest in the subject and directing its attention towards the implementation of risk-aware robots with planning capabilities. Nevertheless, to our knowledge, no one has yet investigated the application of the Dynamic Programming paradigm for the scheduling of tasks for intralogistic robots. Therefore, this dissertation focuses on addressing this topic, proposing various resolution methods for a stochastic dynamic scheduling problem, based on Dynamic Programming and its approximated versions. We find the paradigm particularly intriguing and deserving of further exploration because it resides between a static approach and a purely dynamic one: it promises a greater capacity to account for stochasticity than the former and surely appears less myopic than the latter. Although it is well-known that Dynamic Programming is enormously susceptible to the dimensions of the problem to which it is applied, we are convinced of its efficacy on modest-scale instances. Therefore, we consider its results on small scale problems as benchmarks to be compared with the solutions provided by approximate approaches, with the aim of demonstrating how the latter yield equally valuable outputs. Despite our foremost objective is to accurately solve the stochastic dynamic scheduling problem, it is also crucial to rapidly obtain solutions, especially when it comes to larger scale problems. In fact, an additional goal of ours is to illustrate that such efficiency is exclusively attainable through the application of Approximate Dynamic Programming, as opposed to the exact paradigm. However, we do not entirely dismiss exact Dynamic Programming: we partially exploit it to solve a more intricate version of the scheduling problem that incorporates prioritizing rules. The rationale behind the introduction of priorities is to closely align to real-world applications. To this aim, not only we employ resolution methods that use Dynamic Programming but also present some heuristics. The results of our thorough experiments allow us to conclude that the Approximate Dynamic Programming methods analysed in the dissertation perform admirably, outputting sub-optimal scheduling sequences that do not excessively deviate from the optimal ones obtained through the application of the exact Dynamic Programming paradigm. Some of the presented approaches even exhibit exceptionally fast execution times. Nonetheless, in our case, speed is a trait resulting from approximation, inevitably leading to a trade-off with lower performance. In fact, the determination of the most suitable method for solving an intralogistic robot scheduling problem is subjective. Among the several approaches we present, the decision on which to use is left to whom must address the real-life problem and is contingent on specific requirements related to speed and accuracy. In conclusion, our implemented methods represent a valid choice for solving single-agent dynamic scheduling problems subjected to risk. We contribute to the state of the art by providing a novel perspective for the planning of intralogistic robot scheduling, demonstrating that the Dynamic Programming paradigm and its approximate counterpart reveal suitable alternatives to standard resolution methods.