Scheduling using max-plus algebra

Abstract

In industry, discrete models can be used to describe and analyze a class of event driven systems. These so called discrete event systems (DESs) contain a finite number of resources that are shared by different users called jobs. All of these resources and jobs contribute to the achievement of some common goal. Deciding on how to allocate a set of jobs to limited resources over time in an optimal way is called scheduling, where the basic types of control decisions are routing, ordering and synchronization. The scheduling of DESs is crucial in many applications, such as railway networks, production systems, baggage handling, legged locomotion, container handling and paper handling in printers. Most of the models that describe the behavior of DESs are nonlinear in the conventional algebra that uses addition and multiplication operators. There is however a class of DESs that can be described by a model that is linear in the max-plus algebra, which uses maximization and addition as its main operators. In such a max-plus linear (MPL) system the model structure is fixed, whereby changes in the structure of the system cannot be modeled. However, the model dynamics can be influenced by allowing switching between different modes. An MPL system where switching is allowed is called a switching max-plus linear (SMPL) system. By switching to another mode, the route, order and/or synchronization is changed. A general framework on how to model these SMPL systems is obtained, where the topology graph is used. A topology graph of a system describes all possible connections between resources but does not tell which route or order is chosen. The routes can all be constructed by assigning max-plus binary control variables to each arc. By looking at the number of incoming arcs specific ordering constraints for each node are obtained. A problem that remains are circuits where a job can re-enter multiple times. These circuits result in duplicated nodes whereby the ordering constraints change. The method on how to model such circuits is described. Once the model is obtained, the scheduling problem always results in finding the optimal max-plus binary variables related to routing and ordering. This control problem is solved by using a Model Predictive Control (MPC) strategy, which is recast as a Mixed Integer Linear Programming problem. Using the general framework, a simple and more complex baggage handling system is modeled and controlled. Adding a due date reference for the complex baggage handling system shows that the bags arrive in time. Also the switching between different cycles can clearly be seen.