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

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

Smeets, Lucy (TU Delft Mechanical, Maritime and Materials Engineering; TU Delft Delft Center for Systems and Control)

van den Boom, A.J.J. (mentor)
Ruijs, Mart (mentor)
Laurenti, L. (graduation committee)

Delft University of Technology

Mechanical Engineering | Systems and Control

2022-07-14

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.

max-plus algebra
switching max-plus linear system
model predictive scheduling
autonomous sorting system
mixed integer linear programming
Gurobi
Python
discrete event systems
optimization
simulation

http://resolver.tudelft.nl/uuid:a7befb8f-3206-432b-b41f-c10870730f29

2024-06-28

Student theses

master thesis

© 2022 Lucy Smeets