Modeling and scheduling an autonomous sorting system using a switching max-plus linear model

Abstract

Sorting systems form an example of event driven systems. These types of systems are referred to as discrete event systems (DES), and they consist of jobs that need to be performed at available resources. In an autonomous sorting system, jobs consist of robots receiving and delivering parcels at the correct locations. With scheduling, optimal allocation of the jobs to those resources over time is computed, where the decisions that need to be made are routing, ordering and synchronization. The behaviour of DES is often described by non-linear models, but max-plus linear (MPL) systems are a class of DES that can be described by a model that is linear in the max-plus algebra. This algebra uses two operators maximization and addition. Allowing different routes and switching between orders of jobs extends an MPL system to a switching max-plus linear (SMPL) system. Robots in a sorting system often have many routes to choose from, and need to make order choices with respect to other robots in the system.

In this thesis, a general SMPL model is made for the autonomous sorting system at software company Prime Vision, which can be applied to any sorting area design. The solution to the scheduling problem for the model results in a time schedule for the active robots at the correct locations in the sorting area, as well as the optimal decisions on routing, ordering and synchronization. The optimization problem is solved with a model predictive scheduling (MPS) approach and recast as a mixed integer linear programming (MILP) problem. The model is created in Python and the optimization problem is solved with Gurobi. The resulting schedule is visualized with a simulation, in which the decisions of the robots are clearly shown. An idea for implementation of the optimization into the sorting system is given as well.