Applications of Max-Plus Algebra to Scheduling

Hazem Al Bermanei

Research output: Types of ThesisDoctoral ThesisMonograph


Max-plus algebra provides mathematical theory and techniques for solving nonlinear problems that can be given the form of linear problems, when arithmetical addition is replaced by the operation of maximum and arithmetical multiplication is replaced by addition. Problems of this kind are sometimes of a managerial nature, arising in areas such as manufacturing, transportation, allocation of resources and information processing technology. Max-plus algebra also provides the linear algebraic background to the rapidly developing field of tropical mathematics.

The aim of this thesis is to provide an introductory text to max-plus algebra and to present results on advanced topics and, in particular, how it is useful in applications. An overview of the basic notions of the max-plus algebra and max-plus linear discrete event systems (DES) is presented.

Train networks can be modelled as a directed graph, in which nodes correspond to arrivals and departures at stations, and arcs to traveling times. A particular difficulty is represented by meeting conditions in a single-track railway system. The stability and sensitivity of the timetable is analyzed, and different types of delays and delay behavior are discussed. Interpretation of the recovery matrix is also done. A simple train network with real-world background is used for illustration. Compared to earlier work, which typically includes numerical optimization, this study is fully done by using max-plus algebra.

In this thesis, the scheduling of production systems consisting of many stages and different units is considered, where some of the units can be used for various stages. If a production unit is used for various stages cleaning is needed in between, while no cleaning is needed between stages of the same type. Cleaning of units takes a significant amount of time, which is considered in the scheduling. The goal is to minimize the total production time, and such problems are often solved by using numerical optimization. In this thesis, the possibilities for using max-plus for the scheduling are investigated. Structural decisions, such as choosing one unit over another, proved to be difficult. Scheduling of a small production system consisting of 6 stages and 6 units is used as a case study.

Traffic systems, computer communication systems, production lines, and flows in networks are all based on discrete event systems and, thus, can be conveniently described and analyzed by means of max-plus algebra. Max-plus formalism can be used for modeling of train network and production systems.
Original languageEnglish
Place of PublicationÅbo
Print ISBNs 978-951-765-982-6
Electronic ISBNs978-951-765-983-3
Publication statusPublished - 2021
MoE publication typeG4 Doctoral dissertation (monograph)


Dive into the research topics of 'Applications of Max-Plus Algebra to Scheduling'. Together they form a unique fingerprint.

Cite this