Applications of Max-Plus Algebra to Scheduling

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. ---------- Max-plusalgebran tillhandhåller matematisk teori och teknik för lösning av icke-linjära problem som kan ges linjär form genom att vanlig aritmetisk addition ersätts av maximumoperationen medan aritmetisk multiplikation ersätts av addition. Problem av detta slag är ofta av organisatorisk natur. De uppträder på områden som tillverkningsindustri, transport, resurstilldelning och informationsbehandling. Maxalgebran utgör även den linjär-algebraiska bakgrunden till det snabbt växande området tropisk matematik. Ändamålet med denna avhandling är att tillhandahålla en inledning till max-plusalgebran och presentera resultat av mer avancerad natur och i synnerhet visa hur den är användbar i tillämpningar. Grundbegreppen i max-plusalgebran och teorin för maxpluslinjära händelsedrivna system (Discrete Event Systems, DES) presenteras. Tågnätverk kan modelleras som en orienterad graf där noderna representerar ankomster till och avgångar från stationer, medan kanterna svarar mot restider mellan stationerna. En speciell svårighet innebär modelleringen av enspåriga tågsystem där tåg gående i olika riktningar måste mötas. En tågtidtabells stabilitet och känslighet diskuteras, liksom olika typer av förseningar och strategier för att korrigera dessa. Återställningsmatrisen presenteras och tolkningen av den diskuteras. Teorin illustreras med hjälp av ett enkelt tågnätverk med verklighetsbakgrund. En viktig tillämpning är tidsoptimeringen av produktionssystem bestående av många olika stadier och olika produktionsenheter (maskiner). Av enheterna kan en del användas för olika stadier i processen. I så fall måste de dock rengöras mellan de olika produktionsskedena. Däremot krävs ingen rengöring om enheten inte byter uppgift. Rengöringen tar en viss tid som måste beaktas i modelleringen. Målet är att minimera den totala produktionstiden. Detta har i litteraturen oftast gjorts med numerisk optimering. I denna avhandling har möjligheten att använda maxplusteknik undersökts. Strukturella beslut, såsom att besluta vid vilken tidpunktbyte av uppgift (och rengöring) ska göras, visade sig svåra att direkt modellera som ett maxplusproblem. För hela produktionsprocessen utvecklades därför ett hybridsystem med maxplusalgebraiska subproblem som central ingrediens. Tidtabellen för ett litet produktionssystem med 6 produktionsskeden och 6 produktionsenheter illustrerar tekniken. Trafiksystem, datakommunikationssystem, produktionssystem och nätverksflöden baserar sig på DES och kan därför med fördel beskrivas och analyseras med hjälp av max-plusalgebra