Optimisation of scheduling problems based on timed petri nets

Abstract

This PhD thesis deals with modelling and simulation of scheduling and sequencing problems based on Petri Nets. In particular, Timed, Coloured, and Stochastic Petri Nets are used to model and implement specific scheduling problems in the field of production processes and other discrete event systems. The Petri Net models are simulated over the time domain and a simulation-based optimisation is implemented to optimise the input sequences. Petri Nets offer the possibility to handle conditions on the highest layer. This is a big advantage compared to event-oriented approaches for modelling and simulation of discrete event systems. If conflict or resource sharing problems occur, a strategy of solving simultaneous events should be implemented. In contrast, Petri Nets solve these problems through the basic properties of their structure. In this thesis a new conflict resolution is implemented and a sophisticated way of defining firing sequences is developed. This new approach offers the possibility to model queuing, sequencing or scheduling problems being independent of the appearance of any conflicts. The optimisation of sequencing and scheduling problems works by automated changing and evaluating of the used sequences and parameter specifications. This kind of optimisation problem is too complex to be solved to optimality. A promising alternative is to use heuristics, like genetic algorithms, simulated annealing or threshold accepting. All these methods are implemented in the so called MATLAB PetriSimM toolbox which offers the capability of modelling, simulation, and optimisation of Timed, Coloured, and Stochastic Petri Nets. In case of stochastic processes the comparison of alternative system configurations is a highly sophisticated problem. In this work a sequential paired t-test and variance reduction techniques are used and implemented to solve the stochastic optimisation for sequencing and scheduling problems. In the course of this PhD thesis the PetriSimM toolbox is developed and embedded in the MATLAB environment.<br />All the implemented features, functionalities and capabilities are compared and tested in two case studies including the modelling, simulation and optimisation of a production cell and the well-known travelling salesman problem. This PhD thesis is structured as follows.<br />First of all, the basics of Petri Nets are introduced and an overview is given about the state-of-the-art of Petri Nets and their known extensions. Furthermore, the definition for Petri Nets is formulated to allow the modelling of scheduling problems and the new approaches of defining firing sequences and priorities are described. All used optimisation algorithms are presented and the sequential t-test and the implemented variance reduction techniques are introduced. Next follows the MATLAB PetriSimM toolbox where basic features are outlined and advanced functionalities are described. Finally, the implementation and the results of the optimisation of the two case studies complete this work.<br />

Diese Dissertation beschäftigt sich mit der Modellierung und Simulation von Reihenfolgeproblemen basierend auf Petri Netzen. Im Besonderen werden zeiterweiterte, gefärbte und stochastische Petri Netze verwendet, um spezielle Reihenfolgeprobleme aus dem Bereich von Produktionsprozessen und anderen diskreten Ereignissystemen zu modellieren und implementieren. Die Petri Netz Modelle werden über den Zeitbereich simuliert und die Optimierung der Eingangsreihenfolgen erfolgt mittels implementierter simulationsbasierter Optimierung. Petri Netze bieten die Möglichkeit Bedingungen auf der höchsten Ebene zu behandeln. Das ist ein großer Vorteil im Vergleich zu ereignis-orientierten Zugängen zur Modellierung und Simulation von diskreten Ereignissystemen. Wenn Konflikte oder Probleme mit der gleichzeitigen Benutzung vorhandener Mittel auftreten, muss eine Strategie zum Auflösen gleichzeitiger Ereignisse implementiert werden.<br />Im Gegensatz dazu realisieren Petri Netze diese Probleme durch die grundlegenden Eigenschaften ihrer Struktur. In dieser Arbeit wird eine neue Art der Konfliktlösung eingeführt und es wird ein neuer Weg entwickelt um Feuerungsreihenfolgen zu definieren. Dieser neue Zugang bietet die Möglichkeit Reihenfolgeprobleme zu modellieren, ohne dabei abhängig von Konflikten zu sein. Die Optimierung von Reihenfolgeproblemen wird mittels automatisierter Veränderung und Auswertung der verwendeten Reihenfolgen und Parameterspezifikationen durchgeführt. Diese Art des Optimierungsproblems ist zu komplex, um bis zur Optimalität gelöst zu werden. Eine Erfolg versprechende Alternative bietet die Verwendung von Heuristiken, wie Genetische Algorithmen, Simulated Annealing oder Threshold Accepting. Alle diese Methoden sind in der so genannten MATLAB PetriSimM Toolbox implementiert, die die Fähigkeit der Modellierung, Simulation und Optimierung von zeiterweiterten, gefärbten und stochastischen Petri Netzen besitzt. Im Fall von stochastischen Prozessen ist der Vergleich von alternativen Systemkonfigurationen ein nichttriviales Problem. In dieser Arbeit sind ein sequentieller paarweiser t-Test und Varianzreduktionstechniken implementiert, um die stochastische Optimierung von Reihenfolgeproblemen zu lösen. Im Zuge dieser Arbeit ist die PetriSimM Toolbox entwickelt und in die MATLAB Umgebung integriert worden. Alle entwickelten Funktionalitäten und Fähigkeiten werden anhand von zwei Fallstudien verglichen und getestet. Die Fallstudien beinhalten die Modellierung, Simulation und Optimierung einer Fertigungszelle und dem bekannten Problem des Handlungsreisenden. Diese Dissertation ist folgendermaßen strukturiert. Zuerst werden die Grundlagen von Petri Netzen vorgestellt und es wird ein Überblick über Petri Netze und deren Erweiterungen gegeben. Weiters wird die Definition von Petri Netzen formuliert, die es ermöglicht, Reihenfolgeprobleme zu modellieren und es werden die neuen Ansätze zur Definierung von Feuerungsreihenfolgen und Prioritäten beschrieben. Alle verwendeten Optimierungsalgorithmen werden präsentiert und der sequentielle t-Test und die implementierten Varianzreduktionstechniken werden vorgestellt. Als nächstes folgt die MATLAB PetriSimM Toolbox wo grundlegende Fähigkeiten umrissen und erweiterte Funktionalitäten beschrieben werden. Abschließend wird diese Arbeit von der Implementierung und den Optimierungsresultaten der beiden Fallstudien komplettiert.