# OLAF ZIMMERMANN

Decentralized Scheduling of Discrete Production Systems with Limited Buffers

# BAND 99

Decentralized Scheduling of Discrete Production Systems with Limited Buffers

Wissenschaftliche Berichte des Instituts für Fördertechnik und Logistiksysteme des Karlsruher Instituts für Technologie (KIT)

Olaf Zimmermann

Decentralized Scheduling of Discrete Production Systems with Limited Buffers

#### WISSENSCHAFTLICHE BERICHTE

Institut für Fördertechnik und Logistiksysteme am Karlsruher Institut für Technologie (KIT)

BAND 99

# Decentralized Scheduling of Discrete Production Systems with Limited Buffers

by Olaf Zimmermann

Karlsruher Institut für Technologie Institut für Fördertechnik und Logistiksysteme

Decentralized Scheduling of Discrete Production Systems with Limited Buffers

Zur Erlangung des akademischen Grades eines Doktors der Ingenieurwissenschaften (Dr.-Ing.) von der KIT-Fakultät für Maschinenbau des Karlsruher Instituts für Technologie (KIT) genehmigte Dissertation

von Olaf Zimmermann, M.Sc.

Tag der mündlichen Prüfung: 19. Juli 2022 Hauptreferent: Prof. Dr.-Ing. Kai Furmans Korreferent: Prof. Dr. Horst Tempelmeier

#### **Impressum**

Karlsruher Institut für Technologie (KIT) KIT Scientific Publishing Straße am Forum 2 D-76131 Karlsruhe

KIT Scientific Publishing is a registered trademark of Karlsruhe Institute of Technology. Reprint using the book cover is not allowed.

www.ksp.kit.edu

*This document – excluding parts marked otherwise, the cover, pictures and graphs – is licensed under a Creative Commons Attribution 4.0 International License (CC BY 4.0): https://creativecommons.org/licenses/by/4.0/deed.en*

*The cover page is licensed under a Creative Commons Attribution-No Derivatives 4.0 International License (CC BY-ND 4.0): https://creativecommons.org/licenses/by-nd/4.0/deed.en*

Print on Demand 2023 – Gedruckt auf FSC-zertifiziertem Papier

ISSN 0171-2772 ISBN 978-3-7315-1292-9 DOI 10.5445/KSP/1000157036

# **Decentralized Scheduling of Discrete Production Systems with Limited Buffers**

Zur Erlangung des akademischen Grades eines **Doktors der Ingenieurwissenschaften (Dr.-Ing.)**

von der KIT-Fakultät für Maschinenbau des Karlsruher Instituts für Technologie (KIT) genehmigte

### **Dissertation**

von

## **M.Sc. Olaf Zimmermann**

aus Geseke

Tag der mündlichen Prüfung: 19.07.2022 Hauptreferent: Prof. Dr.-Ing. Kai Furmans Korreferent: Prof. Dr. Horst Tempelmeier

# Danksagung

Die vorliegende Arbeit entstand während meiner Tätigkeit als wissenschaftlicher Mitarbeiter am Institut für Fördertechnik und Logistiksysteme (IFL) des Karlsruher Instituts für Technologie.

Ich danke meinem Doktorvater Prof. Dr.-Ing. Kai Furmans, da er durch die Übernahme der Betreuung sowie der Erstkorrektur diese Arbeit überhaupt erst ermöglicht hat. Weiterhin danke ich Prof. Dr. Horst Tempelmeier für die Übernahme des Korreferats sowie Prof. Dr.-Ing. Xu Cheng für die Übernahme des Prüfungsvorsitzes meiner Promotionsprüfung.

Ich möchte mich ebenfalls bei allen aktiven und ehemaligen Kollegen des IFL bedanken.

Besonderer Dank gilt meiner Familie und meinen Freunden. Sie haben mich während der Dauer meiner Promotion nach Kräften unterstützt und stets ermutigt diesen Weg fortzusetzen.  Für diesen Rückhalt bin ich sehr dankbar.

Geseke, Juli 2022 Olaf Zimmermann

# Kurzfassung

Die Steuerung der Produktion ist eine der Kernaufgaben eines jeden produzierenden Unternehmens.  Aktuelle Trends im Markt führen dabei zu einer hochindividualisierten Produktion bei gleichzeitiger Erhöhung der produzierten Stückzahlen.    Diese Arbeit beschäftigt sich mit eben jenen Steuerungsmethoden, genauer gesagt Methoden zur Planung von Produktionsaufträgen in diesen neuen Produktionssystemen.

Zur Steuerung eignen sich echtzeitfähige und autonome Entscheidungssysteme, mit denen die Steuerung der neuen Organisationsstruktur der Produktion angepasst ist. Agentenbasierte Systeme bieten genau diese Eigenschaften und erlauben es, komplexe Planungsaufgaben in kleinere Teilprobleme zu zerlegen, die schneller und genauer gelöst werden können. Sie erfordern die Verfügbarkeit von Daten in Echtzeit und eine schnelle Kommunikation zwischen den Agenten, was heute dank der vierten industriellen Revolution zur Verfügung steht. Demgegenüber steht der erhöhte Koordinierungsbedarf, der in diesen Systemen beherrscht werden muss. Das Ziel dieser Arbeit ist es, einen dezentralen Produktionsplanungs-Algorithmus zu entwickeln, der in einem Multi-Agenten-System implementiert ist. Er berücksichtigt begrenzte Verfügbarkeit von Pufferplätzen an jedem Arbeitsplatz, ein Thema, das in der Literatur wenig erforscht ist. Der Algorithmus ist in einer flexiblen Werkstattfertigung anwendbar und zeigt eine große Zeiteffizienz bei der Einplanung größerer Mengen von Aufträgen.

Um dieses Ziel zu erreichen, wird zunächst der Produktionsplanungs-Algorithmus ohne das Agentensystem entworfen. Er basiert auf der von Adams et al. (1988) veröffentlichten Shifting Bottleneck Heuristik.    Der entworfene Algorithmus wird angepasst und in das Multi-Agenten-System implementiert. Da das System im praktischen Einsatz immer eine Lösung finden muss, stellen wir mögliche Fehlerfälle vor und wie mit ihnen umgegangen wird. Abschließend findet eine numerische Evaluierung mit zwei realen Produktionssystemen statt. Da sich diese Systeme in einem wichtigen Merkmal ähneln, werden weitere zufällig erzeugte Beispiele getestet und ausgewertet.

# Abstract

Production control is one of the core tasks of any manufacturing company. It is crucial to respond to the market requirements and thus to the demands of the customers. Current trends in the market lead to highly individualized production with a simultaneous increase in the number of goods produced. One consequence of this is that companies must have more flexible and agile production systems to respond to constantly changing customer requirements. Since rigid production lines are no longer suitable, more complex structures such as job shops or matrix production increasingly see usage. They require suitable control methods for production. This thesis deals with those control methods, more precisely with planning production orders in these new production systems.

Real-time and autonomous decision systems are suitable for the control of the new organizational structure of production. Agent-based systems offer precisely these characteristics and break down complex planning tasks into smaller sub-problems that can be solved faster and more accurately. They require real-time data availability and fast communication between agents, which is available today thanks to the fourth industrial revolution. It contrasts with the increased coordination requirements that these systems must master. The goal of this work is to develop a decentralized production scheduling algorithm implemented in a multi-agent system. It considers the limited availability of buffer space at each workstation, a topic that is not well studied in the literature. The algorithm is applicable in a flexible job shop environment and shows excellent time efficiency in scheduling large quantities of jobs.

The production scheduling algorithm is first designed without the agent system to achieve this goal. It bases on the Shifting Bottleneck heuristic published by Adams et al. (1988). Since many changes are necessary to accommodate the required characteristics, only the basic procedure remains the same, while all steps of the heuristic are modeled from scratch. Then, a multi-agent system is designed to represent the above requirements using the algorithm for scheduling. In this system, each workplace has a workplace agent responsible for scheduling and controlling its assigned workplace and additional agents doing the communication, data storage, and general tasks. The designed algorithm is adapted and implemented in the multi-agent system. Since the system always has to find a solution during practical use, we present possible failure cases and how to deal with them. Finally, a numerical evaluation with two real-world production systems takes place. Since these systems are similar in one crucial feature, further randomly generated examples are tested and evaluated.

# Contents

# 1 Introduction

Requirements for production systems have always depended on the market and therefore on the needs of the customers. Companies need to react to the latest trends in society to stay competitive. Change in the market also offers opportunities for the companies, for example, to influence the trends or to open new business segments. In the last decades, a general trend went from requiring pure mass production towards a more individualized production while simultaneously increasing the number of goods produced. Furthermore, globalization added the need to offer various product variations for different regions of the world. Figure 1.1 shows a time-line of these trends in the production area of the last 150 years.

Other trends, which require adaptation of production systems, are shorter innovation and product life cycles, more competition on global markets, and higher customer quality demands. These trends lead to a need for more flexibility and agility in production systems (Leitão 2009). To achieve the desired flexibility, new design methods and tools for production are necessary. "In the future, long-established paradigms of production will still have to continue to change in order to meet the demand for even more individuality, customer-specific product variants and shortest delivery times within the meaning of the term production on demand" (Matt et al. 2015). One of these paradigms can be the organizational structure of the production. It is no longer suitable to build inflexible production lines because installing new lines or changing existing ones requires a high amount of work, knowhow, and money. A new and more modular organization of the production is required to handle the current trends, based on a job shop or matrix production. They allow producing various products and product families in the same production system. However, this only works with a suitable control and planning system for a much more complex production.

Figure 1.1: Overview of trends in production systems (Koren 2010, p.34)

Currently, we are in the fourth industrial revolution, also called Industry 4.0. Real-time and autonomous control of manufacturing processes becomes more and more relevant (Grundstein et al. 2017). It is characterized by "connected and communicating systems through the newest internet technology" (Roth 2016, p. 5). These features enable us to combine the required modular organizational structure of a production system with a decentralized and modular software structure controlling it. Agentbased systems are a possible solution for the previously mentioned more complex planning requirements, enabling decentralized, autonomous realtime planning decisions. Multi-agent systems allow to break down highly complex problems into smaller subproblems, making them much more manageable. The system agents coordinate with each other their local decisions and solve the original global problem together. This approach is known to offer much more flexibility than traditional hierarchical systems with central planning units (J. Zhang et al. (2019)). Advantages of decentralized planning include faster computing of results, better flexibility to dynamic surroundings, robust result quality under changing external circumstances, and better security if parts of the system fail. On the other hand, it needs extra measures to make sure the system is working continuously. These include ensuring that the data is consistent between the elements and that the agents can exchange it in real-time with a reliable communication structure between the different parts of the production system. Furthermore, it needs to include additional rules if a communication is not successful or data is missing.

Parente et al. (2020) write that current decentralized multi-agent systems are limited to selfish decisions and local optima and that the challenge is to gather available data to approach globally optimal decisions. This thesis tries to improve upon that point by introducing a new multi-agent system for scheduling, in which the agents consider the other agents in their local decisions to obtain a better global solution. This work aims to develop a **decentralized scheduling algorithm**, which incorporates **limited available buffer space** at each workplace. It schedules a **flexible job shop** production and scales to large production systems without losing much **efficiency**. The solution is based on a multi-agent system and can react to any change of the production system it represents at the latest at the start of the following scheduling. The idea behind this thesis originated with an existing modular production system in mind. The goal was to create a suitable planning algorithm to schedule it. The usual approach in practice is to use an algorithm for scheduling and then decide how much buffer space is required in the production afterward, making limited buffers in production systems not often researched in the literature. In our case, since the factory for the application of this algorithm already existed, there were already clearly defined maximum buffer slots available. Therefore, the algorithm presented in this works needs to be able to handle this restriction. Nevertheless, we designed the presented algorithm to be applicable in any given discrete production system with the same features. It was a requirement that the algorithm should be as deterministic as possible, meaning that the rules and decisions taken by it based on the current situation are comprehensible to a human, and nothing happens seemingly by chance. This requirement excluded several meta-heuristics, like, for example, a genetic algorithm or artificial intelligence methods from the start. Therefore, this work's algorithm is based on the **Shifting Bottleneck heuristic** by Adams et al. (1988) since previous publications have proven that it gives good results, and its structure makes it perfectly adaptable to a decentralized system.

#### Structure of the Thesis

The thesis starts by giving an overview of the two topics combined in this work. First, scheduling is introduced in **chapter 2**, followed by introducing multi-agent systems in **chapter 3**. Both chapters include a short introduction to their topic and an overview of the later chapters' methods. They also contain a literature review of the relevant publications. These include extensions of the method used for scheduling and existing appliances of multi-agent systems for production planning. **Chapter 4** continues by giving a presentation of the scheduling problem underlying this thesis. It combines the problem and the literature overview of the previous chapters, identifies the research gap, and develops the research questions concerning the problem.

The following two chapters are the central part of the thesis. **Chapter 5** presents an algorithm to solve the scheduling problem based on the Shifting Bottleneck heuristic presented in chapter 2. Since not much more than the basic idea is kept from the original method, it presents all the algorithm steps in detail. The new algorithm is an iterative procedure consisting of four steps. First, it describes the general procedure, and afterward, all of the steps in detail. **Chapter 6** applies the developed algorithm in a multiagent system. It starts with describing the multi-agent system structure and a description of all elements present in it. Furthermore, it describes the necessary changes and additions to make the developed algorithm work in a decentralized system. Since termination is an essential topic in a decentralized system, we finish by describing the features and safety func-

Figure 1.2: Organization of the thesis

tions present in the agent system to guarantee always finding a solution to a scheduling call.

Afterward, chapter 7 presents a numerical evaluation of the algorithm compared to a FIFO (First-In-First-Out) solution. After describing the experiments' setup, we apply the algorithm in the production system of two companies. Since these real-world examples have a common characteristic, we did further tests on randomized systems without that limitation. Finally, the **chapter 8** concludes this thesis. It presents the achieved results and answers to the research questions and presents an overview of how the work can continue in the future.

# 2 Basics of Scheduling

As mentioned in the introduction, the thesis combines two research fields, scheduling, and multi-agent systems, into one production planning system. In this chapter, we start presenting the first area, the scheduling of production systems. After giving a short general introduction to scheduling, including basic notations and definitions, it presents the Shifting Bottleneck heuristic used in this thesis's model in detail. Finally, a presentation and discussion of the extensions and appliances of the literature method conclude this chapter.

# 2.1 Introduction to Scheduling

According to Graves (1981), scheduling is the allocation of available production resources over time to best satisfy some set of optimization criteria. In the classical application of production scheduling, these resources are automated machines or manual workplaces used to produce jobs. Jobs are generally composed of operations, which the given workplaces process, needing a specific processing time to do so. A schedule then is an allocation of operations and time slots in which suitable workplaces do the processing. So-called Gantt-Charts can depict schedules, which makes them easy to read and understand. Figure 2.1 shows an exemplary schedule, once jobbased and once machine-based. Both show a schedule, including four jobs and three workplaces.

Figure 2.1: Gantt-Chart of a schedule, once machine-based (a), once job-based (b) (Brucker 2007, p. 2)

#### 2.1.1 Notation

The number of jobs and workplaces has to be finite in every scheduling problem (Pinedo 2012, p. 13). A job is denoted by *n* and a workplace by *m*. *N* and *M* stand for the set of all jobs and workplaces. Subscripts are given as *j* for jobs and *i* for workplaces. A pair (*i*, *j*) describes the processing of job *j* on workplace *i* and is also called an operation *o*. Operations of a job number from 1 to *k*. When the last operation of a job finishes, the job itself is considered finished. In the basic case, the numbering means that operations process in that order, and the sequence is fixed. From these basic definitions, some more definitions regarding jobs are possible. The operation *o* always has a processing time *tp* , representing the time needed to complete the processing of job *j* on workplace *i*. A job may have a release date *r j* if it is not available at time 0. The release time represents the earliest time the job can start processing its first operation. Jobs may have a due date *dj* . It stands for an externally given date when the job has to be completed, not to be late. Both due dates and release dates as defined here are for the whole production system. They also exist locally at a workplace using the same notation, where they mean the earliest time an operation can start or has to finish at that workplace in order to comply with the global value.

### 2.1.2 Optimization Criteria

The optimization criterion defines the goal of the scheduling process that the scheduling algorithm tries to achieve. It has the form of an objective function, which is always formulated so that it is to be minimized in scheduling problems. A due date does not exist for every scheduling problem. In case jobs have due dates, the objective function bases on these. If scheduling is done without due dates, other criteria, for example, the completion time of jobs, are chosen. Many optimization criteria can apply to a scheduling problem. Here, we present only a few of the more common ones in the following table. Definitions of the criteria stem from Pinedo (2012, p. 18-19).

Table 2.1: List of relevant optimization criteria (taken from Pinedo (2012))

There are also more complex objective functions, which combine several of the above goals or extend them. For this thesis, however, the abovementioned objective functions are sufficient as we will only use them.

## 2.1.3 Shop Models

From the given notation, fundamental scheduling problems, also called shop models, can be derived. Here we will present the three standard models, called flow shop, job shop, and open shop, and some of the extensions made to them in the literature. The way the operations within a job are sequenced defines the three models. All of them assume that precisely one workplace can process a given operation. For a more detailed description of each of the three basic shop models, we refer the reader to Blazewicz et al. (2019), who explain the models in detail.

#### Flow Shop

The flow shop is the most simple of the three models. Here the flow of material is always the same. The flow direction is the same for every job that needs to be scheduled and is known beforehand. The only possible exception is the skipping of a workplace; going backward in the flow is not allowed, as shown in figure 2.2 showing an exemplary flow shop.

Figure 2.2: Exemplary flow shop

#### Job Shop

The assumptions in a job shop are less restrictive than in the flow shop. Here, an external source still gives the sequence of operations in a job, but various jobs can have different sequences. Thus, the order of workplace visits is still known before scheduling. However, material flow through the system differs because every job has its own route. Figure 2.3 shows an exemplary job shop.

Figure 2.3: Exemplary job shop

#### Open Shop

Different from the other two models, the open shop relaxes the property that the sequence of operations is predetermined. In an open shop operations can instead be completed in any order. Since there are no precedence relations between a job's operations, workplace visits of two jobs from various products differ, like in the job shop. In contrast, the order of workplace visits also differs between identical jobs. The open shop allows the processing of all operations of the job in any order. Figure 2.4 shows an example where one job is processed in five different ways.

Figure 2.4: Exemplary open shop

#### More Advanced Shop Models

Numerous possible extensions to the three presented basic models are possible. Since the basic models are very restrictive, many additional features were developed to make the models better applicable in practice. In this section, we present some of them relevant to the model developed in this thesis. The presented models do not have a unique name in most cases. However, when authors mention more advanced shop models, they are sometimes named by their new features or complex or practical job shops. Table 2.2 gives an overview with a detailed description following afterward.

Table 2.2: List of advanced shop models

The first extension is the so-called flexible shop (for reference see Pinedo (2012, p. 15)). It is possible to make in any of the three basic models. In the three basic models, every workplace is unique and only available once. In the flexible shop, there may be more than one workplace processing a given operation. This situation leads to the problem that the scheduler does not know before scheduling which workplace will process which operation of a job. The flexible shop allows identical parallel workplaces in its easiest form, which have the same processing time for each operation. A more complex version allows non-identical processing times for the same operation at different workplaces. An even more complex variation is allowing one workplace to process more than one type of operation. As a practical example, we could have a system where workplace one is a sawing machine, but machine two can saw and drill. The scheduling problem is now more complicated than before because all parallel workplaces share the same subset of operations from a given set of jobs in the flexible shop. With the multi-purpose workplace extension (see Brucker (2007, p. 293ff.)), workplaces only share some of the operations, or they share them with different subsets of workplaces. In the case of these features, the scheduling problem splits into two parts. Then the first step only determines which workplace processes which operation. Then in a second step, the regular scheduling would take place. It is also possible to do both steps together which will most likely lead to better results as it offers an algorithm more optimization potential.

If some of the operations in a job have a fixed sequence but others do not, the resulting model is a mix between a job shop and an open shop (see Brucker (2007, p. 226)). This shop type has different names in the literature; we will refer to it as a partial shop, as for example in Amin-Naseri and Afshari (2012). Another feature regarding the sequence of operations in a job is to include recirculation or re-entrance of jobs. Then, one job can visit a workplace or do an operation more than once during its process sequence.

The only time given in the basic models is the processing time of a job. There can be additional steps in the processing of a job that require time usage. They could, for example, be transport times between workplaces or setup times on a given workplace. Setups are mostly modeled sequencedependent, meaning that the specific time needed for setup depends on the current and the next job to be processed. Furthermore, setup can be done parallel to processing or only in between the processing of two jobs. Both setup and transport could also be resource-limited so that only a fixed number of transport vehicles or a given number of tools is available.

Another important point is the inclusion of waiting areas at or between the workplaces. The basic models assume that there is an infinite amount of space for waiting available at every workplace. If the modeled system has limited buffer space, every job has to be at a waiting spot or in transport at any given time between the processing of two operations. A general assumption is that a job uses input buffer slots before processing an operation on a workplace starts and output buffer slots after processing. A buffer slot may also be used for both, depending on the model. A buffer slot may only be used by the workplace which it is allocated to and not by any other workplace. There can also be buffer slots allocated to no workplace, which are usable by every workplace. Limited waiting space can lead to blocking (see Pinedo (2012, p. 17) where a job cannot leave the current workplace since the next workplace in the process step has no space in its buffer to accommodate the job. The current workplace is then blocked if it cannot continue processing because all buffer slots are full. Limited waiting space can also lead to deadlocks where two workplaces want to transport two jobs between each other, but both cannot start because all buffer slots are full. What a deadlock exactly is will be described in chapter 3.

As the last extension, every aspect of a scheduling model is either deterministic or stochastic (see Pinedo (2012, p. 245ff.)). In deterministic models, every event or time is known beforehand, while in stochastic models, events or times occur according to a probability distribution. That includes any time used in the model, which can be either faster or slower than the planned average, and workplaces' downtime in which they are not available for processing.

Later in this work, in chapter 4, these extensions will be used again. There, the scheduling model underlying this thesis will be defined.

# 2.2 The Shifting Bottleneck Procedure

The algorithm presented in this work bases upon the Shifting Bottleneck procedure (SB) published by Adams et al. (1988). A numerical example of the procedure can be found in Pinedo (2012, p. 196ff.). The procedure applies in the standard job shop scheduling model. It follows an iterative heuristic approach, which is why we also call it SB heuristic, where the main idea is to identify a bottleneck in each iteration. In the following iteration, all other machines then take into account the local schedule of the bottleneck. This section describes the procedure as Adams et al. (1988) released initially. Table 2.3 summarises all variables used in the description of the procedure.

Table 2.3: List of variables used in the Shifting Bottleneck procedure

A set of *N* = {0,1,...,*n*} jobs needs to be scheduled on *M* machines. The jobs are described by a number of process steps. Each process step is assigned to a machine and the order in which the process steps of a job have to be completed is known. The set *On* contains all process steps of job *n*, also known as operations, and the set *O* contains all operations to be planned. *Om* contains all operations which are completed on machine *m*. Each machine can only process one operation at a time. The time needed for processing *pi* is known and fixed and cannot be interrupted. In the optimization problem, *ti* represents the start time of operation *oi* . The goal is to create a schedule that minimizes the makespan given by the objective function which minimizes the latest start time of any operation. The formalization of this problem looks as follows:

$$\begin{aligned} \min \quad & \max\_{l \in O} t\_l\\ \text{s.t.} \quad & t\_j - t\_l \ge p\_i, \quad & j > i, \forall (i, j) \in O\_m, n \in N\\ & t\_l \ge 0, \quad & \forall i \in O\\ & t\_j - t\_l \ge p\_i \lor t\_l - t\_j \ge p\_j, \quad \forall (i, j) \in O\_m, m \in M \end{aligned} \tag{2.1}$$

The three constraints in this problem ensure a job shop. The first states that the difference in start times of two operations of the same job must be larger or equal to the earlier operation's processing time. The second states that start times can only be in the future, while the last one forbids that two operations can be processed simultaneously on a machine. A solution is achieved by deploying the following iterative approach, where *M*0 contains all machines that are already sequenced (*M*0 is empty at the start):

Step 1: Update the release times *ri* and the due dates *fi* of every operation.

Step 2: Create a sequence on all machines *M*\*M*0 and identify a bottleneck machine *m* among them. Set *M*0 = *M*0 +*m*.

Step 3: Re-optimize the sequence of each critical machine *M*0 while keeping the other sequences fixed. Then, if *M* = *M*0 stop, otherwise go to step one again.

In the following, each of the three steps is described in detail.

#### Updating the Release Times and Due Dates

At the start of the procedure, the initial makespan is equal to the longest job's total processing time in *N*. In the iterative solution procedure, each operation *i* is assigned a release time *ri* , which describes the time it can be processed the earliest. This time calculates by summing up the processing times of all previous operations. If any previous operation is already scheduled, *ri* calculates by taking the start time of the closest predecessor already scheduled and summing the processing times from there. The due date *fi* is the latest time the operation has to finish not to increase the complete schedule's makespan, which can be calculated similarly to the release time by taking the current makespan and subtracting the preceding processing times.

#### Identifying the Bottleneck

Before identifying the bottleneck machine in step 2, the local scheduling problem is solved for every machine using the algorithm of Carlier (1982), which will be explained subsequently. At every point during the creation of the local schedule, a priority dispatching rule is applied. The rule takes all operations available to be scheduled at time *t* (all operations with *ri* ≤ *t*) and chooses the one with the earliest due date *fi* . In case of a tie, it takes the one with the longest processing time on the current machine. If there is no operation available at time *t*, but there are still operations to be scheduled, *t* is set to the minimum *r* of all operations to be scheduled. In the following formalized form of this algorithm, *U* is the set of operations already scheduled and *U* the set of all unscheduled operations:

Step 1: Set *t* = min*i*∈*I ri* ; *U* = ;.

Step 2: At time *t*, from amongst the ready operations *i*(*ri* ≤ *t*) of *U*, schedule the operation *j* with the smallest *fi* .

Step 3: Set *U* = *U* ∪ {*j*},*t* = max(*t* + *dj* ,min*i*∈*U ri*),*U* = *U*\{*j*}. If *U* is empty, the algorithm is finished. Otherwise, go to step two.

After scheduling all machines with this algorithm, the bottleneck has to be identified. For this, the makespan of each machine is calculated. Since aiming for the shortest makespan is equal to minimizing the maximum lateness of any job on the given machine regarding *fi* , each operation's end time in the schedule is compared to its due date *fi* . The maximum on a given machine equals the makespan delay of that machine. The bottleneck then is the machine with the highest makespan delay of all machines. In case of a tie, one can choose any of the machines at random.

#### Re-optimizing the Sequences

At the end of each iteration, the local re-optimization uses the same algorithm as the local sequencing. The local sequencing repeats for every machine that has already been the bottleneck of an iteration. If there was an improvement, the old schedule is replaced. Otherwise, no action is taken. The re-optimization cycle finishes once every bottleneck machine has been rescheduled. If there was an improvement during the current cycle, another one starts. Adams et al. (1988) however arbitrarily limit the number of cycles to three up to the point where *M*0 contains all machines. Then, in the last iteration, the cycle only stops if there was no improvement for an entire cycle. During the re-optimization step, machines are rescheduled in order of their makespan value, starting with the highest—their order updates after each cycle.

Adams et al. (1988) propose an additional measure before starting the next iteration, which is only mentioned here for the sake of completeness of the method since the algorithm presented in this work does not use it. They found it helpful to repeat the procedure after removing some non-critical machines with a maximum of p |*M*0| machines removed. They define a machine as non-critical if none of the operations done on this machine is on the schedule's critical path. If there are more non-critical machines than the maximum allowed number, those with the lowest makespan are removed. After the re-optimization cycle, the machines are added one by one until *M*0 contains all machines again. Then the next iteration starts.

# 2.3 Extensions of the Shifting Bottleneck Procedure

Since Adams et al. (1988) published the Shifting Bottleneck heuristic more than 30 years ago, numerous extensions to it have been made. Here, we want to give a short overview of the most relevant ones. The advanced scheduling models presented in chapter 2.1.3 are the basis for most extensions. The extensions to the Shifting Bottleneck procedure divide into two groups. The first group extends or changes only the local workplace scheduling subproblem, while the second changes the procedure itself. The following two sub-chapters are not supposed to give the reader a complete overview of all the publications related to the Shifting Bottleneck procedure. Instead, we focus on those most relevant to our work. The publications not mentioned are applications of the procedure without adding new features or replacing large parts of the procedure with different algorithms, whereas we are only interested in publications that remain somewhat close to the original procedure. The results from this section will be discussed later in chapter 4.

### 2.3.1 Changes to the Single Workplace Subproblem

Changes to the local sequencing are as common as changes to the procedure itself. They are because many of the advanced shop models presented in chapter 2.1.3 can be implemented into the SB without changes to the procedure itself and only require more advanced local sequencing algorithms. An overview of all publications presented in this section can be found in table 2.4 and 2.5. Both tables list the same publications but separate after specific characteristics. The columns of the tables stand for the type of change or additional characteristics added in the publication.

The goal of the original Shifting Bottleneck procedure is the minimization of the makespan. Since jobs in a real-world production system often have delivery or due dates, much research has been done to incorporate a different optimization function within the same procedure. Pinedo and Singer (1999) change the objective function to minimize the Total Weighted Tardiness of the jobs. Mason et al. (2002) present a solution with the goal of total weighted tardiness minimization as well. They use the heuristic in their complex job shop application, which extends the job shop model with batch workplaces, setup times, parallel workplaces, and re-entrant process flows. In Mason and Oey (2003) the published heuristic is slightly changed

Table 2.4: Overview of the changes to the single workplace sub problem and their contents (part 1)

Table 2.5: Overview of the changes to the single workplace sub problem and their contents (part 2)

since batch processing and delayed precedence constraints sometimes lead to an infeasible schedule.

Dauzère-Pérès and Lasserre (1993) update the local sequencing with a new heuristic method which updates the release times of all unplanned operations each time an operation is planned during the local sequencing. The update is done because there may be dependent jobs at the same workplace, which could lead to the situation that the delay of one operation influences another operation's release time at the same workplace. This is, for example, the case if the same job visits a workplace more than once. Balas et al. (1995) solve the same problem as Dauzère-Pérès and Lasserre (1993), but instead of a heuristic, they choose an exact approach for the problem with a branch-and-bound method, which Dauzère-Pérès (1995) also uses. Braune and Zäpfel (2016) propose new heuristics for the Total Weighted Tardiness criterion with the specific aim of solving larger problem instances. Before, in Braune et al. (2012), they proposed an exact algorithm for the single workplace subproblem solution with the same objective. Yoo and Martin-Vega (1997) used a new subproblem procedure for the number of tardy jobs objective function.

Ivens and Lambrecht (1996) extend the procedure with many characteristics that apply in real-world scheduling problems. These include transport times between workplaces, setup times, parallel workplaces, and planning not only in empty but also in production systems with work-in-process. They also include batch processing and the assembly and split of jobs during production. Schutten (1998) follows a similar approach and extends the procedure with more practical features. He takes setup times, parallel workplaces, transport times, orders with more than one job, additionally needed resources for processing, downtimes, and the assembly or split of jobs into account. Ramudhin and Marier (1996) take the different shop types into account, applying the SB to open shops, partial shops, and assembly shops. Sun and Noble (1999) update the single workplace problem with a heuristic for sequence-dependent setup times. Wenqi and Aihua (2004) propose a new single workplace algorithm, which they call Schrage algorithm with a disturbance. They deal with the particular problem of prioritizing between two jobs where job one has the earlier release date, but job two has the earlier due date. Thus, they reduce the due date of jobs that release in the future by multiplying the time between the end of the current schedule and the job's release with a coefficient and then subtracting the result from the original due date. With this change, they can obtain better results than with the original scheduling algorithm. Sourirajan and Uzsoy (2007) use a revised SB procedure. The revised procedure schedules single workplaces, parallel workplaces, and batch processes. They integrate the idea of Balas et al. (1995) and extend the batch processing algorithm of Uzsoy (1995) for parallel workplaces. Topaloglu and Kilincli (2009) propose a new single workplace method to schedule a re-entrant job shop with the Total Weighted Tardiness goal.

In addition to extending the local sequencing problem to include complex characteristics, some research was done to replace the single workplace scheduling with different approaches. Ovacik and Uzsoy (1992) apply the SB heuristic for semiconductor testing operations. They decompose the system into work centers scheduled with the Jackson heuristic and an extended local search. They specialize in testing work centers that also include setup times. In Holtsclaw and Uzsoy (1996) again, two different local subproblem solution procedures are tested, one providing an optimal, one a heuristic solution. Balas et al. (2008) extend their algorithm from 1995 with sequence-dependent setup, deadlines, and precedence constraints. They use an adapted Travelling Salesman Problem for the single workplace subproblem, which can be solved efficiently. Scholz-Reiter et al. (2013) replace the subproblem solution and re-optimization step with a variable neighborhood search. Bilyk and Mönch (2012) also use a variable neighborhood search but implement it in parallel to reduce computation time. One last relevant use of the SB heuristic comes from Cayo and Onal (2020). They use the heuristic to schedule a group of work centers but use different local algorithms to schedule each of them. The applied algorithms mainly include different dispatching rules but also insertion algorithms.

## 2.3.2 Changes to the General Procedure

In contrast to chapter 2.3.1, this section's publications alter the SB procedure or use it differently. That includes changing the bottleneck selection criterion, exchanging parts of the procedure for new methods – most often the re-optimization step –, introducing new features to the heuristic, or taking measures to reduce problem complexity. An overview of all referenced publications and their topic can be found in table 2.6.

Holtsclaw and Uzsoy (1996) test different bottleneck selection criteria including random, most workload, maximum lateness from two different local solution procedures, and a pre-emptive earliest due date approach. Aytug et al. (2003) work on the same topic. They include static measures, namely the Total Machine Load, the Average Remaining Operations to Completion, the Average Remaining Processing Time, and dynamic measures. For the dynamic criterion, they calculate an infeasibility profile for every workplace. The profile includes the number of jobs processed at a workplace at any given time. If the number is greater than one, the schedule is infeasible. From this infeasibility, they develop three criticality measures: The Maximum Infeasibility, Total Infeasibility, and Average Infeasibility of a workplace. Using these measures can reduce computing time by up to 20% compared to the static measures. Mönch and Zimmermann (2007) use simulation to test different workplace criticality measures for which they combine different measures into a single weighted sum where a simulation then optimizes the weights. Pfund et al. (2008) use a multi-criteria approach for the SB, which they based on Mason et al. (2002). They put together the objectives makespan, cycle time, and total weighted tardiness into a desirability function. It is then used on the single workplace subproblem and the workplace criticality level. They can show that the combined approach manages to minimize all three objectives simultaneously.

Lawrence and Sewell (1997) include uncertain processing times into the SB heuristic. To do so, they create an initial schedule with the expected value of the processing time and then update the schedule after each successful processing step according to the difference between expected and actual

Table 2.6: Overview of publications to the general procedure and their focus

processing time. Mehta and Uzsoy (1998) use the procedure as the first step for their heuristics to include workplace breakdowns into the scheduling process. They create an initial solution with the SB and then apply their heuristic to create idle time in the schedules to even out potential breakdowns. Mason et al. (2004) consider general deviations from the created schedule. They tested three different rescheduling strategies to handle the deviations from the created schedule. The first, Right-Shift Rescheduling, delays the whole schedule by the duration of the interruption. Fixed-Sequence Rescheduling does not push all operations back by the delay duration but instead uses existing gaps in the original schedule to even out the delay. The last strategy is Total Rescheduling, which starts the scheduling process again with all remaining operations. They confirm that Total Rescheduling leads to the best results at the expense of computing time, whereas the other two strategies are faster but lead to 10-30% worse results.

Driessel and Mönch (2012) use the SB for complex job shops and add transportation constraints to it. They first calculate a production schedule and afterward compute if a capacity-limited transportation system can handle all required transports. Their goal is to determine the required amount of transport vehicles for the given production schedule. Q. Zhang et al. (2014) also solve the scheduling problem with the SB heuristic and then add a second heuristic to schedule transportation tasks afterward. If the heuristic finds no feasible transportation schedule, the scheduling starts again. They also allow the storage of orders between processing steps. Three storage types are considered: No wait, no storage, or storage allowed. In the first one, jobs are not allowed to wait between two operations, whereas in the second, jobs can wait but only at workplaces since there are no storage places. If storage places exist and storage is allowed, jobs may only wait up to a given maximum time between two processing steps. In the case of storage allowed, its capacity at workplaces is always infinite in this publication.

Pezzella and Merelli (2000) extend the SB with a Tabu Search. They use the SB solution as initial input for a Tabu Search to improve the results. Yeung and Mason (2006) change the re-optimization step. Instead of reoptimizing every time, they use a real option analysis to value the option of re-optimizing and only do it if their model gives a promising result. They can reduce the computation time for the Total Weighted Tardiness objective while simultaneously getting good results. Bülbül (2011) changes the re-optimization procedure to a Tabu Search for the total weighted tardiness objective. Liu and Kozan (2012) solve a parallel workplace job shop scheduling problem with a hybrid approach between the SB heuristic and a Tabu Search. They also present a topological sequencing algorithm that effectively calculates the release and due dates for the single workplace subproblems. The hybrid approach is using a Tabu Search for the re-optimization step in the SB procedure.

Yoo and Martin-Vega (1997) apply the same decomposition technique for semiconductor production, which Mason et al. (2002) also uses. Unlike them, however, in this publication, the goal criterion is the number of tardy jobs. A so-called General Algorithm Framework does the scheduling of the decomposed work centers, which schedules a set of single workplace problems. A publication entirely focused on decomposition strategies was published by Ovacik and Uzsoy (1997). The ideas were later used again by Sourirajan and Uzsoy (2007). They use a revised procedure with a rolling horizon, where jobs group according to their availability date and only one group is scheduled at a time. Cheng et al. (2001) use the SB to schedule a parallel workplace flow shop. The bottleneck is not identified on a single workplace basis, but instead, a stage of the flow shop becomes the bottleneck. To achieve better results, they also propose a new parallel workplace scheduling heuristic for minimizing the maximum lateness.

Singer (2001) published a time horizon decomposition approach. It splits operations into groups planned for a certain time window, thus reducing the problem's complexity. Also, it allows some overlapping of time windows to improve the results. Upasani et al. (2006) reduce the problem size of the decomposition approach by partitioning the work centers into two groups, one of high utilization and one of low utilization. The SB is only done on the high utilization work centers, whereas the low utilization work centers bundle into a single infinite capacity workplace scheduled with a dispatching rule. Chen et al. (2006) publish an approach for the scheduling of job shops with non-identical parallel workplaces. To increase computational efficiency, they propose a new heuristic that omits the bottleneck selection part. They schedule all work centers at once with a dispatching rule and then directly start the re-optimization procedure with all work centers. They also include a procedure to determine the number of workplaces needed in each work center.

# 3 Multi-Agent Systems for Production Planning

There is a trend towards modeling more and more complex systems in production and logistics with decentralized solutions as they present a way to deal with the flexible and modular structure of these systems (Leitão et al. 2015). This chapter is supposed to introduce a variant of these systems, called multi-agent systems, focusing on its use for production planning. In a decentralized system, multiple (sometimes identical) independent elements work together to achieve the system's goal. The elements are usually called "agents". Chapter 3.1 presents a definition, and some essential characteristics of agents. When more than one agent is present in a system, the system is called a multi-agent system. Multi-agent systems and some implications derived from them are outlined in chapter 3.2. Furthermore, we want to show some existing agent solutions for production scheduling in chapter 3.3.

# 3.1 Characteristics of Agents

As used in this thesis, the term "agent" is the short form of "software-agent". Ferber defines the term agent (Ferber 1999, p. 9-10). He writes that an agent is a physical or virtual entity which is capable of acting in an environment and can communicate with other agents. It is autonomous and tries to achieve its goals. For this, it watches its surroundings. This definition is extensive because it includes every control system and even humans in it. Ferber presents more specific definitions following the general one. However, for this work, a definition by Wooldridge fits: "An agent is a computer system that is situated in some environment, and that is capable of autonomous action in this environment in order to meet its design objectives" (Wooldridge 2006, p. 15). This definition focuses on software agents and leaves out all physical agents, which fits agents' usage in this work. The autonomous actions mentioned in the definition typically involve the agent taking input from the given environment and transform it into an output, which is given back to the environment. With this transformation, the agent tries to fulfill its goal best.

There are several different categorizations of agents concerning their abilities and features from various authors, which extends this work's purpose. One differentiation made is between a reactive and a deliberate agent. A reactive agent only reacts to the environment without representing its state towards the environment (Ferber 1994). On the other hand, deliberate agents have explicit goals and plans, which fits the description from Wooldridge. They are also able to store information and save a representation of the environment in a knowledge base. Actions from deliberate agents are based on a planning process for realizing the given goals (Büttner 2011, p. 44-45). An exemplary early approach for a deliberate agent is the BDI-model of Bratman (Bratman 1987). There are also combinations of the two types, which combine the reactive agent's fast answers with the slower but more in-depth responses from the deliberate agent.

Apart from this definition, the term 'Intelligent agent' is also often used. According to Wooldridge (2006, p. 23), a reactive agent is not intelligent. Instead, the agent also has to take the initiative itself to reach its goal and has to be able to interact with other agents. This extends the deliberate agent with the ability to communicate and interact between agents. He states that it is hard to effectively balance between the blind execution of tasks (similar to the reactive agent) and the reaction towards new situations by changing the goal or reaction pattern (p. 24). His argument about the interaction between agents leads directly towards multi-agent systems. There is a need for interaction between these agents if their decisions influence each other in any system with more than one agent making decisions.

# 3.2 Multi-agent Systems

A multi-agent system consists of at least two agents who interact to reach their own or shared goals (Jung 2016). In theory, a multi-agent system can consist of an unlimited number of agents. The goal of using multiple agents is to solve problems that a single agent would not be able to solve (Monostori et al. 2006). Figure 3.1 shows an exemplary structure of a multi-agent system. Each agent in this system has its own goal. If two agents have the same goal, they have to cooperate to reach it. If their goals are different, they are automatically rivals if they cannot reach their goals simultaneously. Each agent has its area of influence in the environment, which does or does not overlap with that of other agents. As one can see in figure 3.1, agents may be in a group. Between the various groups or also within a group, there may be a hierarchy of the agents. A hierarchy indicates some control of one group of agents over another group. This, however, is not depicted in the figure. According to Lima et al. (2006), apart from a hierarchical relation, two other relations between agents are possible. Agents can either be autonomous, which means that they can talk to each other directly or build a federation where the communication takes place via a mediator architecture. Of course, different relation types can also mix in a single system.

### 3.2.1 Interactions between Agents

Interactions mostly take part between the agents in a group, but it does not have to be limited to that. Agents of different groups or even whole groups can also interact with each other. The interaction between the agents can include but is not limited to cooperation, coordination and negotiation (Wooldridge 2006, p. 3). For agents to be able to communicate, they need to talk in the same language. There are numerous communication protocols described in the literature, which will not be presented in detail here, as we developed the communication of the presented system without using an existing protocol. This will be presented in chapter 6. In addition to a common language that defines the structure and content of messages agents send and receive, agents also need a way to exchange messages.

Figure 3.1: Exemplary multi-agent system (Wooldridge 2006)

This problem does not exist in centralized systems since all information is present at the only agent's location (in our case, the scheduler or scheduling agent). Measures to share data and information between the agents must exist if this is not the case. It is not only crucial that adequate data or knowledge is present in decentralized systems since it can be done without problems, as we will see. If many agents are to execute local algorithms, but the agents' results are dependent on each other, the system must guarantee that the independent agents achieve fitting results. This will be discussed further in the chapter 3.2.2 about coordination. For sharing information, two different ways are common in multi-agent systems, shown in figure 3.2. The first is the blackboard approach (shown on the left), a decentralized system in which the data storage is centralized. Mandal et al. (2010) de-

scribe it in more detail. A communication artifact or blackboard serves as a shared central information pool in which agents can store data and messages. All agents can then retrieve information from the blackboard. It makes the coordination between agents easier without taking away the agents' independent decision-making (see also Lee and Kim (2008)). The second way (right side of the figure) works without such a tool. It stores data directly in each agent. That creates a need for a feature to exchange new information between the agents to keep all databases in synchronization and to ensure that agents only get the information relevant to them. For this, event systems were developed. In them, each message (called "event") created by an agent contains a topic. Agents can subscribe to topics and so only receive the messages relevant to them. An event-managing agent is responsible for receiving and distributing the messages without processing them. This type of event processing is called a publish-subscribe system. A detailed introduction to these systems can be found in Tarkoma (2012). One can also use it in combination with the blackboard approach where messages can be used, for example, to tell other agents to start or stop working.

An essential point for the interaction is that agents have to understand the messages sent between them. If the agent system is developed newly from the start, this is not a problem. However, if agents from various projects or developers interact, a common language or ontology is necessary. An example of a formalized system is the contract net protocol by Davis and Smith (1983) which resembles an auction. In this thesis, we created the interaction between the agents without considering any existing systems. Therefore, we will not describe any protocol in detail here.

#### 3.2.2 Coordination and Planning

A reason for using the described communication among the agents is the coordination between them. Coordination is the problem of managing all inter-dependencies between the agents (Wooldridge 2006, p. 200). There are several approaches to ensure proper coordination between agents. They depend on the fact whether the agents in the systems cooperate or compete towards their goals. Cooperating agents work together to reach a common goal. Competing agents, however, follow different goals and only work together if needed. As this thesis's topic requires the agents' cooperation, we will focus on this aspect in the following. Cooperation can be achieved in two different ways. By dividing the goal into several sub-goals where a better result for a sub-goal leads to a better result for the overall goal, agents automatically cooperate even if they act selfishly. This can be reversed in that the different sub-goals compete with each other, whereby the better fulfillment of one target can lead to a worse fulfillment of the overall target. The second approach is to divide the possible actions, which then distribute among the agents. If all of the agents have the same goal, they need to work together to achieve it. This way, joint intentions of the agents achieve the coordination (p. 204). Systems can also use a coordination agent to monitor the coordination or to make decisions if the agents cannot settle on a solution. This approach is called Cooperative Multi-Agent Planning as stated by Torreño et al. (2017).

Without considering hierarchies, there are three possibilities for planning in a multi-agent system. The descriptions and evaluations stem from Wooldridge (2006, p. 218-219). Ferber (1999) had previously described almost the same possibilities more in-depth. The simplest way, because it eliminates all necessary coordination, is to plan centrally and only execute the plan with several agents. Here, a central planning agent creates a plan for one or several executing agents while the planning agent views the whole system. This automatically introduces a hierarchy since the executing agents will use every plan given to them by the planning agent. As a second step, the planning could also be done decentralized. To keep it easier at first, several agents contribute to one plan where they are specialists for certain parts of the plan. This can be extended to the most difficult possibility, to create individual plans decentralized. As already mentioned, coordination so that all plans fit together is especially important now. That is also what makes this step the most complicated. The agents must correct their local results if they notice that the global solution becomes infeasible, all while still trying to get the best possible (or at least a sufficiently good) global result.

When conflicts arise in a multi-agent system, either between cooperating agents, which cannot decide on the same result or between rival agents, who want to use the same resource, a fast mechanism for solving the conflict is required. For solving conflict situations, various negotiation mechanisms are used. They include auctions, one-to-one negotiation, bargaining and argumentation-based negotiation (Monostori et al. 2006). Again, this thesis will use a newly designed system, which does not completely fit any of the categories mentioned here, as we found none of the existing system fits our needs perfectly.

Apart from conflicts about the planning result, there can also be conflicts within the organizational structure. Those lead to deadlocks or livelocks of the multi-agent system. Tanenbaum and Bos (2015, p. 439) give a formal description of deadlocks: "A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can cause". An example of this would be two people standing across each other in a very narrow hallway. Both want to continue onwards but cannot do so since the other person is in the way. They are therefore blocking each other and causing a deadlock. It is either possible to recover from an existing deadlock or to avoid one occurring in the first place. An agent system needs to guarantee one of the two possibilities. Otherwise, it can lead to situations where the system fails, and manual intervention becomes necessary. There are two more related concepts. The first is the livelock, which we already mentioned. Explaining it with our hallway example again, now the two persons have enough space to go past each other. However, as they stand across each other, one moves to the right, while the other moves to the left simultaneously. They are now standing across each other again, and therefore reverse their actions. This creates a cycle in which both are still acting, but a solution to the problem is never acquired. The last point related to these two concepts is the starvation of a process. Starvation means that a process is available to be worked, but this never happens since higher prioritized processes always cut in front of it. For an agent system, this could be a communication request from one agent to another, which is never answered since the requested agent deems other work more important. Then, the requesting agent is waiting for an answer endlessly and is starved. We will also look at this topic and preventing it when discussing deadlocks and livelocks in chapter 6.3.

# 3.3 Existing Multi-agent Systems in the Literature

Having now presented an introduction to multi-agent systems, in conclusion, several existing multi-agent systems for production planning are presented. They divide into two categories—one for systems connected to the SB heuristic and one for those not. The most relevant parts for understanding the architecture of a multi-agent system are the types of agents present in the system and which of those agents are intelligent and which are not. A further topic of interest is the communication between the agents in the given system. Here, we will not explain the presented systems in full detail. Some of them are very similar so that only the differences will be highlighted. For others, we mention only relevant or essential aspects of the publication. Furthermore, since there are numerous multi-agent systems published in the literature, this section focuses on publications that also contain the scheduling aspect in the multi-agent system, which is the point of interest of this thesis.

# 3.3.1 Applications of the SB Heuristic in Agent Systems

The first to use the SB heuristic in agent systems were Brandimarte et al. (2000). They use a two-level architecture consisting of local schedulers for the workstations and a material coordinator above them. Figure 3.3 depicts the schema. They assume that every job has a given release and due date. The coordinator determines a time window for each operation from the job time window and sends it to the respective local scheduler. Each time window's start and end times serve as the release and due date for that operation on the workstation. The local scheduler then tries to create an optimal schedule from the given time windows. The scheduling finishes if the time windows are feasible for each local scheduler. If not, the coordinator updates the time windows, and the process continues iteratively until it finds a solution. This process is decentralized, and the local scheduling agents plus the material coordinator exchange the time windows and solutions through messages. The result of this algorithm is not a plan that local work centers have to adhere to but instead time windows for operations, which were proven feasible during the planning step. If a local work center cannot hold the given due date during the processing of an operation, it exchanges messages with the following work center agent to see if the delay can be buffered there.

Mönch and Drießel (2005) use an approach very close to the original SB heuristic but introduce a second level of decomposition to reduce problem complexity. They decompose the job shop into several work areas. The

Figure 3.3: Two level architecture (Brandimarte et al. 2000)

SB heuristic is then applied on two levels. They use it to create a schedule among the work areas, where each work area uses the SB heuristic again to create a local schedule. From the local schedules, a bottleneck work area is determined. The release times and due dates of all other work areas then update with the determined bottleneck area's start and release times. From there on, the standard process of doing the local scheduling for all remaining work areas applies. This repeats until no more work areas remain to be scheduled. In this publication, there is no intention to use the system in a decentralized way. The authors call it "distributed" instead, which relates to the fact that the original bigger problem is decomposed into several more minor problems at different job shop areas while still, a central processing unit does the scheduling. This procedure was made faster by Drießel et al. (2010) where they state that the work area subproblems are independent of each other and can therefore be solved in parallel. The same group of authors also published their agent-based system for semiconductor scheduling. It was first presented in Mönch et al. 2003 and is called FABMAS. This system transports the hierarchical structure into a FAB (semiconductor fabrication plant) agent, work area agent, and work center agent. The idea is extender further in Mönch and Stehli (2006) and Mönch et al. (2006). They operate their system with a centralized FAB scheduling agent, however.

Gavareshki and Zarandi (2011) use an agent system to improve upon a solution found by the SB heuristic. For this, they develop their search method based on a neighborhood search. Each machine gets one search agent that tries to improve the local solution towards a global optimization criterion. Iima et al. (1999) do not directly cite the SB heuristic. However, their method is very similar to a decentralized implementation of the reoptimization procedure in the heuristic. They generate an initial schedule according to the Earliest Due Date dispatching rule. Afterward, a random agent - each machine has an agent in this system - proposes a new solution. The proposal consists of choosing a random operation on the machine and producing it earlier. The agent proposes the new solution to all other agents, which can accept or refuse the new solution. If the new solution is better on a local agent's objective, the agent accepts it. The current best solution is updated in case of all agents accepting. This procedure repeats a given number of times.

### 3.3.2 General Agent Systems for Production Planning

Since usage of the SB heuristic in agent systems is somewhat limited, we extend our overview of agent systems for production planning to general agent systems to gather additional information about how other publications do decentralized production planning. First, we describe a few older systems and their basic ideas. Afterward, in more detail, more recent and more relevant publications are presented. An overview of the publications mentioned in this section and their characteristics can be found in table 3.1. We classified the publications according to whether the agent system is hierarchical or non-hierarchical and if the decision-making is centralized or decentralized. A separate category was included for auction-based systems, as most publications use auctions to reach decisions.

Sikora and Shaw (1997) focus on the communication between planning agents. In their system, a production line requires scheduling, but also, the decision about lot sizes has to be made beforehand. In the first step, two agents, one for sequencing, one for lot-sizing, work together to create a line schedule. This is then extended by applications to a system with multiple lines and re-scheduling practices if changes to the system happen during a planned time horizon. This approach can be seen as one of the first publications implementing agents for production planning. It only contains scheduling agents and leaves out agents to control the system's workflow, which later publications also include. Another example focusing on communication is the publication by Krothapalli and Deshmukh (1999). They design three negotiation protocols that agents can use to create a schedule and then compare them to a hierarchical model. The first model used is based solely on the processing time of the tasks where the job chooses the machine with the shortest processing time. The second is a currency scheme, where jobs enter the system with some arbitrary currency. Machines calculate a price for processing a job task based on the expected completion time and their recent bids' success. The job then evaluates the prices and chooses one within the limits of its money and due date. The last model is similar to the second and additionally allows the pre-emption of other tasks depending on the required due dates. Sousa and Ramos (1999) use negotiation with a focus on problems of indecision and conflict avoidance. Indecision occurs when a resource makes a bid for a production task and is not informed about the bid's acceptance or decline before bidding for a second task, which it could produce in the same time slot. This problem is avoided by only allowing tasks to start a negotiation with resources currently not in another negotiation process.

A multi-agent system, called HOLOS, was published by Rabelo et al. (1999). It consists of a scheduling supervisor, enterprise agents assigned to every resource, so-called distribution centers (groups of enterprise agents) whose responsibilities contain choosing the best agent for an order. Lastly, the consortium consists of the enterprise agents chosen to process an order. The scheduling works with a negotiation process on an auction basis, which Rabelo and Camarinha-Matos (1994) describe in detail. Another early example for a negotiation on auction-basis is from Schoop et al. (2001). How-

Table 3.1: Overview of publications of agent systems for production planning and their classification

ever, the publication does not state how offers and decisions are calculated. Bussmann and Schild (2001) present a more complex auction system. Their system consists of three agent types, one for the machines, one for the jobs, and a third for the transportation between machines. When an operation of a job finishes or a job enters the system, the job agent starts an auction. All machines configured to perform the task then make a bid based on their current workload and the number of tasks the machine can do. After collecting all bids, the job agent decides which machine to choose. If no bid arrives, it restarts the auction. One interesting point for practical application is that the machine agents manage their virtual input and output buffers. The input buffer contains all the machine's open tasks, while the output contains all jobs that finished processing and have not yet been assigned to a follow-up machine. The critical point for the management of the buffers is that they are limited in size. Therefore, machines can only make a bid for a job if they have a spot open in their virtual input buffer. This leads to the fact that deadlocks may occur during the scheduling. The implications from it for the scheduling process will be discussed later in chapter 4. Another aspect making this paper very interesting despite its age is that other publications related to it (Bussmann and Schild 2000, Sundermeyer and Bussmann 2001, and Schild and Bussmann 2007) describe this system in use in an automobile factory in Germany, the only publication of those mentioned here to do so.

Frey et al. (2003) introduce two different multi-agent systems. Both consist of machine and order agents. In the first system, orders start the scheduling process. They call each machine agent, asking for a proposal. Machine agents can refuse to either answer (decline the proposal), make a bid, or ask the order agent for a new proposal since the current one could not be understood. After collecting all answers, the order agent accepts one machine proposal and refuses all the others. The second system works exactly opposite to the first. In it, the machine agents ask for proposals after finishing the processing of a task. Then, the order agents decide whether they want to send a proposal to the machine agent or not. Afterward, they use the same procedure as in the first case. The results of both systems were compared with a classical optimization problem. They conclude that the multi-agent system is better if the underlying production system becomes more complex and inhomogeneous and in cases of re-scheduling. Another example of an auction-based negotiation comes from Sudo et al. (2010). In this publication, again, job agents start a negotiation that machine agents respond to with a bid. Renna (2011) presents an architecture for scheduling manufacturing cells consisting of several machines. In his system, there are part agents, manufacturing cell agents, and machine agents. The scheduling process starts with the part agent determining which cell it has to visit next. Then it sends a request to the corresponding machine cell agent. The cell agent then asks all of its machine agents to send key performance figures regarding the part's processing. After obtaining all answers, the cell agent decides which machine will process the part and communicate it to the machine and the part. The performance figures considered are the time needed until the part's processing can start, the percentage of the machine's downtime, and the average deviation from the expected processing time. These three are weighted and calculated into a normalized index. Giordani et al. (2013) use an iterative procedure to deal with the problems of conflicts among the agents. A central coordinator agent starts all auctions and can change prices to improve result quality after getting all bids from the agents. This ensures that the coordinator always considers all options before reaching a decision and awarding tasks.

Figure 3.4: Agent system of Klein et al. (Klein et al. 2018)

Using negotiation for scheduling in multi-agent systems is not only done in older publications. Klein et al. (2018) use an approach in which an order agent tries to schedule its way through a production system by setting up auctions with the help of an auctioneer agent for each of its production steps. Bidders consist of two kinds of agents. Transport agents compete to get the transport order between production steps, and resource agents compete to get production orders. Both groups of bidding agents try to maximize their profit; therefore, they want to get as many orders as possible allocated to them. After all of the bids have arrived, the auction agent relays the best of them to the order agent. For transport, the order agent simply chooses the best offer. For production, a second step is implemented in which the order agent directly communicates with the best bidders. The offers are criticized, and resource agents get the possibility to improve their offer. This iterative procedure continues until none of the offers can be negotiated anymore. Afterward, the order agent chooses the best offer or cancels the negotiation. Guizzi et al. (2019) extend the well-known Contract Net Protocol for their interaction. This system consists of resource and job agents. Resource agents start the negotiation process. All jobs available for processing on that machine then respond with a bid containing their required processing time. The machine evaluates the bids according to the total processing time of a job, the job's residual processing time, and those two values only on the machine in question. Afterward, the machine decides to process one of the jobs. This is equivalent to a complex dispatching rule that is implemented decentralized.

The most recognized publication in this section, by the number of citations, is from Wang et al. (2016). The publication focuses on agents relevant to the scheduling process and leaves out all other agents present in the system.  The supplementary agents are responsible for handling buffer spaces in the production. After a task finishes or a job enters the system, it starts an auction for the next task with all machine and supplementary agents. All receiving agents then determine if they are capable of doing the task and are idle. If both apply, they bid for the task. If an agent is capable but not idle, it informs the job agent about this fact. Otherwise, it ignores the message. The job agent then decides what to do next. If it receives no answer, there likely is a malfunction in the system. In case of only busy messages, the job agent waits and starts the negotiation again after a time. If there are bids, it will decide for one of them according to a set of priority rules. Before awarding the task to the chosen agent, it starts a negotiation with the transport agents. Here, however, multiple transportation agents can form a group to finish the task together if no one can do the transport by itself. After the transport negotiation finishes, both transport and production or buffer task are awarded to an agent.

Figure 3.5: Negotiation procedure (Wang et al. 2016)

Other than in the systems presented before, there is no mention of limited buffers in this case. Since the authors write about dealing with deadlocks, buffer slots must, however, be limited in some way. Dealing with deadlocks is also an essential aspect of the model developed for this thesis; therefore, we take a closer look at this publication's deadlock avoidance strategies. The authors present four strategies to avoid deadlocks. The first is for a particular case of a production system in which multi-purpose machines exist. In this case, they try to limit the number of multi-purpose machines by restricting the use of those machines for tasks that could also be done on other machines. This procedure leaves a maximum of one machine, which shares the capability to do tasks with other machines. It considerably reduces the number of loops in the product flows and consequently the chance for deadlocks to occur. As a second step, the number of visits on the multi-purpose machine and the machines with the same operation type is equally balanced. Strategy three reserves buffer spots for the critical machines identified after steps one and two. According to the authors, if there are enough buffer spots available, deadlocks can no longer occur after these three steps. If this is not the case, a protocol is applied, prioritizing jobs in a loop over jobs not in a loop. These strategies work well, according to the authors. However, they cannot eliminate deadlocks completely and only reduce the chance of a deadlock occurring.

So far, all of the presented systems have used some variation of an auctionbased scheduling system. Some publications do not use an auction to schedule production tasks, although their number is smaller than auctionbased publications. Wang and Lin (2009) describe a system called agentbased agile manufacturing planning and control system (AMPCS) in detail. The system includes variations of resource, job, and scheduling agents. Additionally, there are specialized data and monitoring agents present. The scheduling is done in multiple steps. A central scheduling agent first creates a production schedule based on demand, which contains the products to be manufactured. Then, the schedule is evaluated in a simulation and, if successful, saved. Afterward, with information from the resource agents, the scheduling agent creates an operation schedule. Here, a small part of an auction-based system remains since the resource agents submit their information by making a bid towards the scheduling agent. The simulation again evaluates the final plan before the production starts. Resource agents may also reject the final plan if they cannot comply with it. This triggers a re-scheduling from the scheduling agent. Another approach with a centralized scheduler is chosen by Y. Zhang et al. (2014). A Capability Evaluation Agent evaluates the orders coming into the system and assigns the tasks to the best-suited machine. Machines have their agents that supply the Capability Evaluation Agent and a Process Monitor Agent with real-time information. The Process Monitor Agent tracks the machine agents' status and calls for a re-scheduling if disturbances or interruptions occur. Finally, the Scheduling Agent schedules all tasks on the assigned machines considering the given real-time information. Groß et al. (2020) focus on the simultaneous scheduling of production and transports in remanufacturing. A central scheduling agent in a multi-agent system creates schedules for workplaces and AGVs.

The three presented non-auction-based publications while being multiagent systems, had a centralized scheduling agent. The last part of this section presents publications that use decentralized non-auction scheduling in at least some parts of the process. Leitao and Restivo (2008) propose a hierarchical holon system. A supervisor does the scheduling, and operational holons execute the production plans. When disturbances such as breakdowns or general deviations from the plan occur, the operational holons gain more autonomy to re-schedule as they see fit. The system then dynamically changes to a decentralized structure wherein the holons communicate and negotiate how to best react to the disturbance.

Figure 3.6: Scheduling process of Maoudj et al. (Maoudj et al. 2019)

Another example of a system in this category is the publication of Maoudj et al. (2019). They use robotic assembly cells where each cell has a local agent, which includes a scheduling module. Each agent only solves a part of the scheduling problem without having a global view. Before each agent schedules its operations, a global scheduling agent assigns the operations to a cell. For this, operations are prioritized, and then each prioritization level is dispatched to a cell. Afterward, the cell scheduling agent assigns each operation to a robot within the cell, and finally, the operations on each robot are sequenced. Scheduling in each step is done according to time-based dispatching rules. Agents exchange information about operations so that local release times can be updated when necessary. Mayer et al. (2019) publish a decentralized system where the job agent decides its route through the production system by deciding which workstations to visit. The workstation itself regularly updates its schedule with an optimization model according to the jobs currently wanting to visit it. A vehicle agent handles requests for transports from the workstation agent, which assigns the transports to AGVs based on a different optimization model. In the publication of Egger et al. (2020), a job arriving into the system sends a request to the agent processing its last process step. That agent then asks the precessing step to make a statement about when they can finish processing these jobs. This continues until the first process of the process sequence. Each agent who has received the answers to its requests then plans its start and end time until the final step finishes the planning.

# 4 Scope of this Thesis

After providing the basics of the two main topics and an overview of the relevant works published in the areas, this chapter finalizes the introduction. It starts with concluding the literature research by summarizing it and identifying the research gap. A definition of the problem that the algorithm in this work solves and its assumptions are developed. This problem is then split up into research questions to structure the work on it.

# 4.1 Conclusion to the Literature Overview and Research Gap

The publication dates of the extensions to the SB heuristic indicate that it has fallen out of researchers' focus over time. Publications added many characteristics in the first years after the initial release, but there are relatively few publications during the last years. To find out why is not easy, but it may have to do with more powerful computers and the availability of other heuristics, enabling to schedule systems without decomposing them. It has not completely gone off the radar since there are still publications using it, mostly combining it with some artificial intelligence technique. It has been regularly used only in the area of semiconductor scheduling. Since semiconductor manufacturing is generally considered one of the most complex production processes, this shows that the method is still relevant. This is especially true in decentralized systems since the heuristic can easily be converted into a decentralized algorithm. However, its use in decentralized systems so far is also minimal. It is either extended with entirely different algorithms (such as a Tabu or Neighborhood search) or used at several points in a distributed system but calculated centrally for each of them. Although researchers have made many extensions already to the SB heuristic, the literature overview has shown that only one of the mentioned publications research available buffer space in the production system (Q. Zhang et al. (2014)). And it even only mentions that their production system contains buffer slots, not that they are limited.

The argument about missing research about limited buffer slots in scheduling extends beyond the SB heuristic. Even generally, limited buffer space is a topic not widely researched in scheduling problems. In Fleischmann et al. (2021), we searched for publications focusing on mathematical formulations of the scheduling problem, including limited buffers, not only looking for the SB heuristic or decentralized systems. We found some but none of those matched the formulation of the presented problem. We refer to Brucker (2012) for a general overview of the limited buffer topic. However, none of the cases presented match this thesis's problem, as we will see soon. There are also publications concerning the so-called "blocking job shop", for example, in Lange and Werner (2019), which are equivalent to a system having zero buffer slots, but they only work with precisely zero buffer slots at every workplace. In conclusion, this topic is not only of interest for this specific application of the SB heuristic, but it has not been researched thoroughly in general.

There are numerous multi-agent systems for scheduling production systems, which do not use the SB heuristic. To find them, our search string consisted of three groups. The first group contained the words "Agentbased", "Distributed", "Decentralized", and "Multi-Agent". The second group contained the words "Production" and "Manufacturing". The last group consisted of "Scheduling", "Planning", and "Control". From these groups, all possible combinations (in total 24) were used in the Google Scholar search engine. A large part of the resulting publications focuses on auction mechanisms to create a production plan. Auctions can have the disadvantage that they base on relatively short-term planning, where they plan each step only when the previous step finishes. Since they are easy to implement and give good results if deadlocks are not a problem, publications not using auctions are relatively scarce (excluding meta-heuristics). We found only four publications matching our criteria and not using auctions where the scheduling is done decentralized. In three of these systems, scheduling is done hierarchically. Only one publication presents a decentralized, non-hierarchical agent-based scheduling system (Egger et al. 2020). Their system, however, also plans short-term, as agents negotiate about one job at a time. Among the auction-based publications, two are dealing with limited available buffer space in the production. However, both show rule-based strategies to avoid deadlocks but cannot guarantee the absence of deadlocks. It can be concluded from the overview that no decentralized deterministic scheduling algorithm taking into account limited buffers without hierarchies exists yet.

# 4.2 Problem Description

This work aims to develop a decentralized scheduling algorithm that incorporates limited available buffer space at each workplace. We made two significant design decisions before starting the project. The first one was that it had to be a decentralized system. The second one, and more relevant to the scheduling aspect, that the resulting algorithm should be deterministic in every aspect. After some research, we chose the SB heuristic as a base since it can be easily used in a decentralized way and showed remarkable results in the publications using it.

The underlying system is based on the job shop problem presented in chapter 2.1.3 extended by a few advanced features. The most important is that the job shop model assumes an unlimited available buffer space at each workplace in the production. In this work, the buffer space at each workplace is strictly limited. There is also no other buffer space than those at the workplaces. This creates a need to limit the number of orders released into the production system to prevent unnecessary waiting time, blockages, or even deadlocks. We define that a job can only enter or leave a workplace's processing area via a buffer slot. Therefore, there always needs to be a free buffer slot once an operation finishes for the job to leave the processing area, and a free buffer slot on the following workplace in the process sequence when it is transported there. This definition of buffer slots makes a deadlock occur if two (or more) workplaces need to send jobs to each other in a circle but cannot do so because input buffer slots at each affected workplace are full.

We also changed the objective function of the algorithm. The original SB heuristic uses the maximum makespan criterion. Instead, here we use the average makespan of all jobs as our objective function. It is equivalent to the "Total Completion Time" presented in chapter 2.1.2. Table 4.1 can explain the reason for this change. It is supposed to show the finish times of eight orders after finishing the scheduling. The number of workplaces in the system is irrelevant for this example. With the original objective function, both plans would have the same value, which is 40 if we assume planning to happen at time zero. From a one-time optimization standpoint, that statement is correct. Taking a look at a scheduling algorithm's practical applications leads to a separate evaluation of the two plans. In the real world, not only one scheduling run is performed. Instead, scheduling repeats again and again. Therefore, more regular completion of orders makes more sense because some are already finished at the next scheduling point, which is achieved by each order having an impact on the objective function. Another even more critical argument for the changed objective function is that the more regular finishing of jobs leads to an overall reduced number of jobs in the system. Then, buffer usage is lower, and the algorithm gains more flexibility to improve the result.

Table 4.1: Job finishing times of two plans

Buffer slots incur a delay; a minimum time a job needs to spend in a buffer slot before it can leave again. Slots are also strictly divided into input and output buffer slots, meaning that input buffer slots only store jobs that the workplace has yet to process, and output buffer slots only for those that it has already finished. For simplification, especially in the agent system, we assume that the division of buffer slots into input and output buffer is strictly given and cannot be changed. This work assumes that one of them is an output buffer, and the rest are input buffer slots for any given number of buffer slots. Furthermore, more than one workplace may offer an operation, this is the flexible shop extension from 2.1.3. Workplaces offering the same type of operation are called parallel workplaces throughout this work. We allow processing times to differ on workplaces offering the same operation. Each workplace can only offer one type of operation. Setup and transportation times are assumed to be always zero. The workplace following in the process sequence always carries out transports. The ownership of the job, therefore, switches once the job leaves the processing area. The production system does not have to be empty when planning starts. Instead, there can be any number of work-in-progress jobs currently being processed at a workplace or waiting in any buffer slot. Workplaces are always assumed to have 100% uptime, meaning there are no breakdowns or interruptions of a process. Furthermore, the algorithm cannot stop an operation in progress to start a different operation. We formulated this problem, including more than the mentioned extensions, as a mathematical optimization problem in Fleischmann et al. (2021).

# 4.3 Research Questions

After defining the research problem, we can specify the questions to solve it. The research of this thesis divides into four parts. The first area deals with the scheduling aspect of the problem. Here, we make the necessary extensions and changes to the SB heuristic integrated into the basic algorithm of Adams et al. (1988). Especially the limitation of available buffer slots needs significant changes in the logic of the algorithm. Therefore, the research question that will be answered in chapter 5 is the following:

#### **1st research question: How can a Shifting Bottleneck procedure schedule the problem presented in chapter 4.2?**

The result of the first question is a scheduling algorithm that can handle the required characteristics but still executes centrally. The second research area builds on the algorithm and converts it into a decentralized multiagent system. For this, some parts of the algorithm need to be adapted to continue to work. Furthermore, all parts of the multi-agent system, for example, data storage or communication between agents, have to be newly developed. Chapters 6.1 and 6.2 try to answer the following question:

### **2nd research question: How can a decentralized multi-agent system executing the algorithm of research question one be modeled and implemented?**

Finally, more critical than pure numerical quality is the reliability of the algorithm. For this, the algorithm needs to avoid deadlocks, livelocks, and starvation, which were described in chapter 3.2.2. There, the three problems were described referring to an agent system, which leads to the third research question. With regard to our problem description, ideally, we can prove that the algorithm will always create a schedule in any given situation.

### **3rd research question: Does the decentralized multi-agent system guarantee the creation of a production plan for every possible case of valid input data?**

However, the same problems can also occur during the execution of a scheduling plan. Therefore, we also need to guarantee that the scheduling result is free of deadlocks, livelocks, and starvation. Whether that is possible, is the aim of the fourth and final research question. Since the third and fourth question are closely related, both will be answered in chapter 6.3.

**4th research question: Is the production plan created by the decentralized multi-agent system always free of deadlocks, livelocks, and starvation?**

# 5 Scheduling Algorithm

This chapter presents the algorithm to solve the problem presented in chapter 4.2 and therefore answers the first research question. For this, first, the general procedure of the modified SB heuristic is presented. It follows the original publication of Adams et al. (1988) in the order of the general steps with some changes and additions. Before all five steps of the algorithm are described in detail afterward, a short section describes the rules and ideas guiding the algorithm in general. They will be relevant for every step of the algorithm. The problem's objective function has also changed slightly as described in chapter 4.2. Chapter 5.4 will explain it in detail, where a bottleneck is identified, and the objective function is applied. As in the original procedure, *M* describes the set of all workplaces, and *M*0 the set of workplaces already identified as a bottleneck. The general procedure of the algorithm is as follows, also pictured in figure 5.1:

Step 1: Update all necessary information before scheduling.

Step 2: Create a local sequence on all workplaces *M*\*M*0.

Step 3: Identify a bottleneck workplace *m* among them. Set *M*0 = *M*0 +{*m*}.

Step 4: Re-optimize the sequence of each critical workplace *M*0 while keeping the other sequences fixed. Then, if *M* = *M*0 go to step five, otherwise go to step two again.

Step 5: Finish the scheduling by creating a production and a transport plan for each workplace from the scheduling result.

Step one of the original procedure is now included in the local sequencing since it has to be done workplace-specific. Instead, a new first step to update data, which only needs updating once per scheduling, is introduced. Which data exactly needs to be gathered is described in chapter 5.2. Step two has not changed on the iteration level. We only divided it into two separate steps, presented in chapter 5.3 and 5.4. However, many changes were made within the local sequencing since it needs to incorporate the additional features required to solve the problem. The re-optimization (step four) is different in one crucial aspect in comparison to the original procedure. The step was repeated until no change in all workplaces' local plans occurs but only until a maximum of three repetitions finished. We removed the limit of three repetitions. Now, every time the re-optimization starts, it will continue until a full repetition of re-optimizations without any change completes.

We also have to include an additional feature in the re-optimization since limited buffers can lead to infeasible plans. We introduce a repair method for the case of creating an infeasible plan during the re-optimization. This step and the changes are described in chapter 5.5.

Figure 5.1: Flow chart of the scheduling algorithm

The original procedure uses the algorithm from Carlier to sequence bottleneck and non-bottleneck workplaces (steps 3 and 4 of the new procedure). Here, we use different versions of a newly developed algorithm at various points during the scheduling process. Until a workplace becomes a bottleneck in an iteration, we use the basic version. It is described in chapter 5.3; we call it our local sequencing algorithm. Afterward, local sequencing is not called any more for that workplace unless it is part of a parallel workplace group. The differences between parallel and non-parallel workplaces will be explained in chapter 5.4. Once a workplace was added to the pool of bottleneck workplaces, the second version of the algorithm applies for the reoptimization. If an infeasible plan is detected during the re-optimization, a third version of the algorithm helps to repair the plan. Versions two and three are the same as the base version for large parts; chapter 5.5 explains the differences. After describing the algorithm's general guidelines, we can continue to give a detailed explanation of all steps in chronological order, starting with the preparations before scheduling.

# 5.1 Guidelines for the Algorithm

The main addition compared to the original SB heuristic is the addition of limited buffer space at each workplace. This brings up the question of how and if the local sequencing on each workplace needs to change because of this. If buffer space is unlimited, it is generally preferable that every workplace works as fast as it can. The reason for this assessment is that it minimizes the possibility that any succeeding workplaces become idle by offering them as many work-in-process as possible. Reducing idle time of workplaces is in turn a way to achieve a better global plan, as a plan with no idle time on any workplace can not be improved further concerning the makespan. The algorithm of Carlier, therefore, only uses the due dates of operations to prioritize between them, while the prioritized individual operation is always produced as early as possible. With limited buffer slots, this rule no longer applies. While producing as fast as possible on a workplace is still optimal for the global result, an algorithm also has to consider the fact that it may overfill the buffer slots of a succeeding workplace, blocking itself in the process, since finished operation can no longer be transported to the following workplace. In the worst case, this creates a deadlock in the production system. This introduces a need for the workplaces to only process operations as fast as the system can handle. As we will see, the algorithm presented here does not schedule every operation as early as possible. Instead, if the bottleneck is downstream from the current workplace, it tries to produce the operation after just-in-time, reducing required buffer time and, therefore, slots. For an upstream bottleneck, the algorithm still tries to produce as fast as possible. To achieve this behavior, the algorithm contains several additional prioritization criteria, which will be presented in detail later in this chapter. For each of them, a pairwise comparison with multiple conditions is done between the current best and a candidate operation. If all conditions are fulfilled, the algorithm determines the candidate as the more important operation. If not, then the current best operation stays the most important. Sometimes a formula in the text of chapter 5.3 contains more than one criterion. They were grouped together in the description of the algorithm since they are closely related. If that is the case, an operation only needs to fulfil one of the criteria to be deemed as more important. After the algorithm has compared all operations for each criterion, the most important operation is selected as next in the local sequence. Its start time is then set according to the rules. The details of this process and the criteria are described in section 5.3.

With just this guideline, the local sequencing can create infeasible plans. Infeasible in this case means that the plan would require more buffer slots for a production plan than there are available in the production system. When that case occurs during the scheduling, a method to repair the plan is needed. We extended the algorithm with a method to repair a plan, which we call a negotiation. How the negotiations function is described in detail in section 5.5 but we want to give a short overview here to describe the motivation behind them. The easiest way to repair a plan is to introduce a time delay. The operation which does not have a buffer slot can be delayed until a slot is available again. Also, the whole plan after that operation (timewise) is delayed by the same amount. This solution will always create a feasible plan with the cost of a worse objective function value. Therefore, the algorithm first tries to find a different sequence of operations, in which the amount of buffer slots is sufficient. Only if it can not find one, a delay is included. That this delay will always work can be shown with a relatively simple example of an extreme case. If it were needed, one could introduce so many delays within the production plan that only one job is processed in the production system at a time, meaning that the next job is only allowed to start processing once the previous job has been finished. In that case, infeasibilities are not possible anymore.

The algorithm described in this chapter was designed with the intention of applying it in a decentralized scheduling system. Therefore, some of the solutions or explanations of this chapter may seem unnecessary complex for a centrally executed algorithm. However, they were chosen since they help to make the transition to a decentralized system as smooth as possible. Without this background some of the features could be reduced in complexity in case the user plans a centralized usage for which the above-mentioned negotiations are an example. For the following functional description of the algorithm, it helps to remember the general remarks of this section to understand the design decisions made for the algorithm.

# 5.2 Preparations before Scheduling

Since the algorithm does not need to assume an empty system at the point of planning, the first step is to gather the current system state before scheduling can start. The algorithm starts with a list of all operations needing processing for every workplace. Whenever a job enters the system, its operations get added to the workplace's lists. The workplaces delete an operation once it finishes processing. Therefore, the combination of all lists represents the amount of work that needs doing in the production system. It does, however, not correctly represent the operations that require scheduling. The algorithm needs to remove two kinds of operations before local sequencing can start since the workplace will not process them. The first kind are operations that are currently being processed on a workplace, if there are any. These operations have already been planned in a previous call of the algorithm and cannot change any more since we do not allow the interruption of a process. We also decided that the algorithm will not plan the operations of all jobs already waiting in an input buffer slot. They already must have a planned start time for processing from previous scheduling, which the algorithm will not change. However, if there was any delay during the previous plan's execution, the starting times of jobs waiting in the input buffer have to be adjusted to account for the delay, if needed. The input buffering times of these jobs are also lengthened for the same delay. Table 5.1 shows a situation with which we will explain how the algorithm proceeds in this case.

Table 5.1: Example situation for a delay in the plan on a single workplace

The workplace in question had a local plan of four operations after the last scheduling. The first operation started and finished on time. The second operation had a delay of two time units. Operations three and four have not yet started, so the current time must be somewhere between time units 12 and 17. Assuming that operations three and four are already waiting in the input buffer, the algorithm needs to check their times. It corrects the start time from operation three since it can start at time 17 at the earliest. There was a gap of four time units before operation four so that one does not need a change in times. Then, the algorithm removes the old buffer slot reservation of operation three and creates a new one from the current time up to time 17. Now the algorithm will account for the delay in the current scheduling. A delay in one workplace might also lead to necessary changes in a preceding workplace. This only happens if the input buffer of the delaying workplace is currently full. In that case, a planned transport might have to be carried out later, therefore inducing a delay in the output buffer of the preceding workplace.

If an operation, processed at a workplace that is available multiple times in the production, is removed from the list of operations to be scheduled for one of the two reasons, it is removed at all parallel workplaces. After the list of operations for scheduling is now final, the algorithm deletes the old times for processing and buffering of all previously planned operations that will now be planned again (since they have not arrived at the workplace in question).

Because a workplace might have leftover work from the last plan, it cannot guarantee that the first operation can immediately start processing. Instead, the latest finish time of all operations, which were removed before on that workplace, is saved as the earliest time (*tst ar t*) an operation can start processing in the new local sequence. The same happens for the input buffer slots. The algorithm already knows if they are currently in use. It creates a buffer reservation from planning time to the time processing starts for operations waiting in the input buffer.

During the scheduling, the algorithm will need a list of all predecessors of a workplace. Since it is now clear, which operations it will plan, it can precompute this list. This is done for time-efficiency because the algorithm may use it many times later. It looks at every operation to be planned in a workplace to create the list. If the workplace does not process the first step in the process sequence, it saves all workplaces that offer the preceding operation in the list. Duplicates will only be listed once.

After these steps, the algorithm knows the current system state and has finished pre-computations. The scheduling process can begin. It starts in the same way as the original algorithm, with the local sequencing step at each workplace described in the next section.

# 5.3 Create a Local Sequence

The process of creating a local sequence, also called local sequencing throughout this thesis, describes the algorithm for scheduling the operations to be processed in a given workplace. The only input for it is the list of operations resulting from the preparations. If this section mentions any operations, it refers only to those that the current workplace can process. If other workplaces can process the same operations as the workplace currently planning, the operations will split between the parallel workplaces during this step. The result of the local sequencing is a production and an input buffering plan for the given workplace. The algorithm of this section creates the local sequences for workplaces that are not yet a bottleneck. The described procedure considers the already fixed start times of all operations on workplaces identified as a bottleneck while creating them. Every time the sequencing starts, the algorithm makes an entirely new sequence of operations, and the old sequence from a previous local sequencing gets deleted. Due to an additional bottleneck, the plan from the last call is no longer valid.

The process starts by updating the key variables (chapter 5.3.1), which is done once at the start of sequencing. Afterward, it schedules one operation after another until there are none left. Chapter 5.3.2 describes the process of deciding which operation to schedule next and its start time. It consists of two separate steps, first selecting and timing an operation that is to be next in the sequence, then creating a buffer reservation for that operation.

## 5.3.1 Update the Key Variables of Operations

The local sequencing starts with an update of all operations with the currently available data from bottleneck workplaces. For each operation, key variables are updated, which will be used for the sequencing. Table 5.2 gives an overview of the variables, which will be described afterward.

From the variables in table 5.2, *tp* , only the operation's processing time is known at this point. Every other variable has to be determined or calculated with information from other workplaces. The first is the variable *earlier*. It describes the relative position of the first fixed operation within the process sequence of this operation's job. If the first fixed operation's position in the process sequence is before the operation to be updated, *earlier* is true. If the position is after or there is no fixed operation yet, it is false. While looking

Table 5.2: Key variables used during the sequencing of operations

at the process sequence, *st* is also determined. It describes if the job of this operation has already started the first operation of the process sequence.

$$t\_{avall,j} = \max\_{l=1}^{j-1} t\_{start,l} + \sum\_{k=l+1}^{j-1} t\_{p,k} \tag{5.1}$$

$$t\_{\text{late},j} = \min\_{l=p+1}^{\infty} t\_{\text{start},l} - \sum\_{k=p+1}^{l} t\_{p,k} \tag{5.2}$$

Afterwards, *tavail* and *tlate* are determined, which the formulas 5.1 and 5.2 describe. *tavail* describes the earliest time the operation can begin processing. This time equals the earliest time the operation can arrive at the workplace plus the minimum input buffer delay. It is calculated by adding the process and minimum buffering times of all previous process steps in the sequence to the current time *t*. If there is any fixed step before or the job has already started, it takes the known end time of the last earlier fixed operation, and process and buffering times of the steps between are added. *tlate* is calculated in the same way, starting from the current makespan value of the job and subtracting the process and buffering times or taking the start time of the first fixed step occurring later in the process sequence and subtracting process and buffering times from there. The current makespan value of a job is equal to the earliest time it can finish. *tavail* does not have to be equal to the earliest possible starting time, *tearl*, since a job may arrive earlier at the workplace than the workplace can begin processing. Therefore, *tearl* is equal to the maximum of *tavail* and *tstart*, which was determined during the preparations.

An optimal start time *topt* of the operation is calculated from these values. In a production system with unlimited buffers, it is always optimal to produce an operation as early as possible since it can be stored after processing until the next workplace needs it. If buffers are limited, as they are in this thesis, it is generally better to only produce an operation just in time for the next step of the process sequence to limit the buffer usage as much as possible to have a reserve for situations where buffering is not avoidable. Also, buffering increases the makespan of a job (though not always of the whole plan) and should only be done if necessary. Therefore, this algorithm sets *topt* to the following: If the operation has no fixed step before (*earlier* is false) and a fixed step afterward in the process sequence, it is optimal to start the order as late as possible (while causing no delay), which is equal to *tlate* − *tp* . If fixed steps exist before and after this operation, the algorithm determines the first fixed operation. If it is after this operation, *topt* is as late as possible. In the two remaining cases, we try to produce the operation as fast as possible and, therefore, equal *tearl*. We either know that there is a bottleneck before this operation and therefore want to produce it as fast as possible to limit buffer usage. Alternatively, there is no fixed operation at all in the process sequence, in which case the operation can be produced at any time between *tearl* and *tlate*. We set the value to *tearl* because we would rather have the algorithm produce it fast for a better scheduling result while producing it later is always possible. It may also be that the result of *tlate*−*tp* is smaller than the earliest start time, in which case the optimal start time is also *tearl*. Table 5.3 summarizes this paragraph and the calculation of *topt*.

Table 5.3: Different cases for the optimal start time

After updating all operations, the algorithm classifies the operations into two groups. The first contains all operations which have a fixed step in their process sequence, and a second all orders without a single fixed step. We make this differentiation because orders which have a fixed step need to be planned as close as possible to their optimal start time, whereas the algorithm can schedule the other orders at any point between their earliest and latest start time. We will call the first group high-priority operations and the second group low-priority operations for the next steps.

## 5.3.2 Determine the Next Operation to be Scheduled

The process of creating a local sequence for a workplace is iterative. In every iteration, one operation is selected, scheduled at the end of the current plan according to its start time. Adding an operation to the plan before an already scheduled operation is not possible. An iteration consists of two connected steps. First, an operation is selected and its start time is determined. Afterward, a buffer reservation in accordance with the planned start time is created. At single workplaces, this process continues until all operations are scheduled. Parallel workplaces do this process simultaneously since they still have overlapping lists after the preparations step. Therefore, at a parallel workplace, only one operation is scheduled before stopping the process. Then, the algorithm determines on which parallel workplace the next operation will be scheduled. It always chooses the workplace with the earliest plan end time. In case of a tie, any workplace can be taken.

#### Select an operation

The decision which operation to schedule next is made over several criteria. For each criterion, a current best operation evaluates against the other operations. If a candidate fulfills the criterion, it replaces the current best operation. If the two compared operations are equivalent according to the criterion, the current best operation does not change. The algorithm needs to select one operation as the current best to start comparing operations. Since this only influences the case of a tie between two operations, which indicates that it does not matter which operation to take, any operation can be chosen for this. We take the first alphabetical entry of the high-priority list as a starting operation. It is to note that only high-priority operations are available for selection for the following criteria. Lower priority operations will be checked afterward at the end of the selection process. Some of the criteria only apply if both operations were not planned during an earlier planning process or both were. Operations that were already planned before, but were not processed yet, are sometimes preferred over new operations to prohibit extensive backlogging of "bad" operations. "Bad" in this context means that an operation always is at the end of a schedule, as it does not fit well earlier. We will describe for each criterion if this rule applies. In the following, the index *best* indicates the current best operation, and the index *cand* the candidate operation, which evaluates against it.

$$t\_{\rm opt,cand} < t\_{\rm opt,best} \tag{5.3}$$

(5.4)

Equation 5.3 describes the primary condition after which the algorithm orders the operations for the sequencing. Generally, it chooses the operation with the earliest optimal start time. We take the operation with the earliest *topt* since it replaces the *tlate* of the original algorithm as described in chapter 5.3.1. If the same *topt* value occurs in multiple operations, a decision between them is made according to equation 5.4.

The original algorithm takes *tp* as a tiebreaker. We already included the processing time in the calculations for *topt*. Therefore, the algorithm uses the due date *tlate* as a tiebreaker. It is, however, only applied if the jobs of both operations have not started yet. If at least one of the jobs has started or the two compared operations have the same value for the tiebreaker, *tavail* is the tiebreaker. It forces a FIFO ordering of the two operations. Should *tavail* also be the same for the candidate and current best operation, the algorithm keeps the current best operation because it cannot decide which of the two operations it should process first.

*tstart* is the start time of an operation in the local sequence. After the first criterion, the algorithm plans to schedule the current best operation at its optimal starting time *topt*,*best*. If that time is earlier than the end time *t* of the current plan, it plans to schedule it at time *t* instead. Afterward, the selection process does not finish yet. In the following, the algorithm checks several additional unique cases, where it is better to diverge from the basic ordering. For this, it makes a case distinction. Case one applies if the planned start time is equal to *t*, case two if it is later than *t*, meaning there would be a gap in the plan if the selection process stops now.

$$\text{Select}\begin{cases} \text{candidate} & t\_{\text{earl,cand}} \le t, \text{t}\_{\text{late,cand}} < t\_{\text{late,best}}\\ & t\_{\text{late,cand}} < t + t\_{p,cand} + t\_{p,\text{best}}\\ \text{current best} & \text{otherwise} \end{cases} \tag{5.5}$$

First, the case of *tstart*,*best* equal to *t* is presented. It implies that the current best operation either causes a delay or is processed just in time (*tstart*,*best* + *tp*,*best* ≥ *tlate,best*). The algorithm then checks if any candidate operation gets delayed because it will start after the current best operation. If one is found and has an earlier *tlate*, the algorithm switches the current best operation. The reason is that one of the two operations will be late. Therefore, the algorithm tries to minimize the combined lateness of the two operations. Equation 5.5 describes the conditions for the switch. Here, the algorithm only compares operations that both have not started. If at least one of them has started already, this condition gets ignored, and it keeps the basic ordering. Figure 5.2 describes an example of a situation in which this criterion is applied.

For simplicity's sake, we can assume that the two operations given in the diagram are the only two remaining to be scheduled. Both operations are

Figure 5.2: Example situation for condition 5.5

drawn at their optimal start time in the diagram. From that we can already gather that one will definitely be late as they must be processed in parallel to both be on time which is not possible. The time instant *t* depicts the current end time of the local sequence. Therefore, the operation marked as current best will be late, as it can start earliest 10 time units after its optimal start time. In this example, the primary criterion chooses the operation marked as current best to schedule since it has the earlier optimal start time. If the algorithm schedules this sequence, the candidate operation would be 30 time units late, as it would finish at time unit 50 instead of 20. The current best operation would be ten time units late, giving a total delay of 40 time units. If it switches the sequence, the candidate operation would be on time, and the current best operation would finish at time 50, making it 20 units late. That is a superior solution, so the algorithm switches the sequence.

At this point during the selection process, it might be that the current best operation finishes later than its *tlate,best*. At a later point, that is not possible anymore, since the second case of the case distinction describes that *tstart,best* > *t*. The criteria as mentioned earlier directly mirror that an operation finishing on-time starts at its *topt,best*. Therefore, the algorithm now checks if *obest* finishes too late. If that is the case, it tries to find gaps earlier in the plan, which can be closed by shifting the start times of already scheduled operations forwards. Every operation with a start time later than its earliest start time can shift. With this, the algorithm tries to finish a few operations too early instead of finishing one too late. The maximum shift time is *tstart,best* + *tp*,*best* − *tlate,best* as that is the delay of the current best operation. If the algorithm finds a possible shift smaller than that value, the sequence will still be shifted by that number since it improves the plan's objective function value by reducing the delay of the currently selected operation. After the possible shift, the first case finishes.

$$\text{Select}\begin{cases} \text{candidate} & t\_{opt,cand} < t + t\_{p,best}, t\_{late,cand} < t\_{late,best} \\ & t\_{earl,cond} \le t - t\_{p,cand} \\ \text{current best} & \text{otherwise} \end{cases} \tag{5.6}$$