- Research , Home Stretch
- 16/05/2023
Home Stretch | The math behind waiting
The production process of large high-tech manufacturers, such as ASML, is characterized by many parties supplying the components that make up the final product. If these parties can’t supply on time, this results in supply-chain delays that may have major financial consequences. Dennis Schol, who’s defending his dissertation today, developed queueing theory-based mathematical models to map out these complex supply chains.
High-tech companies, such as Veldhoven-based chip machine manufacturer ASML, produce advanced machines consisting of many different components. These components are supplied by thousands of different manufacturers from all over the world, which in turn have their own suppliers. This makes these large supply chains unbelievably complex.
When a manufacturer can’t supply a component in time, a delay in the supply chain arises. As ASML annually produces a relatively small number of final products that are extremely valuable, such a delay can cause incalculable turnover losses. Dennis Schol, a PhD candidate at the Department of Mathematics and Computer Science, developed several mathematical models to map out these supply chains and study the behavior of these systems. In so doing, he answered questions such as: What’s the maximum waiting time? And what are the chances of an extremely long waiting time occurring?
Waiting
At first sight, Schol’s central research question may not seem that relevant to many people, but in actual fact these supply chains are a complex version of something we all have to deal with from time to time: a queue. “Waiting in line at the grocery store, waiting on the phone before you’re put through or waiting at a traffic light – these are all examples of queuing,” Schol explains.
The above situations may seem fairly unspectacular, but queues also exist in healthcare, with much more bothersome or even serious consequences. “An elderly lady I know had to undergo surgery, so she was put on a waiting list. But because this happened during the pandemic, the surgery kept being postponed,” the PhD candidate says to illustrate.
Queueing theory
Queuing theory is a branch of applied math that studies queues by way of mathematical models. The basic system is always the same, and consists of tasks or customers, and servers where these tasks are processed or the customers are assisted. If a new task arrives while the server is already working on another one, this results in a queue – just like in the grocery store.
As it’s impossible to know exactly how many people will visit a grocery store at a specific time, for example, probability calculation plays an important role in the queuing models. Schol: “On the basis of the calculations, we can predict the behavior of the queuing systems and take effective measures to prevent overly long queues.”
You can also use this method to model all kinds of practical situations. “Take the helpdesk of a call center,” he continues. “You don’t want the customers to be stuck in a queue for ages, but you also don’t want the staff to sit around doing nothing for half the time. So the question is: How many employees do you need to reach an optimal balance? To answer this, you first need to describe the situation using a mathematical model. Once you know exactly what’s happening, you can take decisions like hiring extra staff.”
Fork-join queue
In his research, Schol focused on a specific type of queuing model, namely the fork-join queue. As its name suggests, it operates based on two principles: splitting and joining (also see the below figure). In this system, incoming tasks are split into subtasks that are processed by several servers at the same time, after which they’re joined together again at the end of the process. Logically, the speed of the slowest server determines how fast the complete task is executed.
The supply chains of large tech manufacturers like ASML are a great example of a practical problem that the fork-join queue can model, as this is also a process in which the main task is split into many different subtasks. ASML places a great many orders with different suppliers at the same time. Only when these orders have been processed, the final product can be assembled. Schol took the existing model as his starting point and elaborated a number of cases inspired by these supply chains. Based on a number of assumptions, such as the number of suppliers and the average waiting time, he arrived at a number of scenarios and calculated the maximum waiting time for every one of them.
As the models are based on assumptions, they don’t fully correspond to scenarios from practice. They are useful nonetheless, because they give the manufacturers an idea of how the system behaves. “They can see what case fits their situation best and this should give them a good approximation of the waiting times. Based on this they can draft guidelines and make better agreements,” he explains. “I also tried to make the models very general to guarantee they’re as widely applicable as possible.”
Data centers
One of the papers making up his dissertation revolves around another application, namely in data centers. A data center consists of a large number of servers making calculations. When a task arrives, it is spit into much smaller subtasks. Each server executes a subtask and all calculations are put together again at the end. It’s a completely different situation, but it’s clear this system can be modelled in the same way as the supply chains,” Schol says.
There is something that makes the situation different and extra challenging. At data centers, sometimes a task comes in that has a huge workload. In mathematics, this phenomenon where a value significantly exceeds the average is called a ‘heavy tail’.
“For instance, an average Instagram user has about 150 followers, but there are also people with millions of followers. So those are the odd ones out,” Schol explains. “Similarly, you have tasks that constitute huge deviations because they cost so much time. Which is a problem.” When a heavy tail is in progress, the system’s behavior is fundamentally different. Schol calculated what the longest waiting time is in data centers that have to deal with these extremely taxing tasks.
Infinite applications
Schol finds it important to see how useful queue systems can be in solving all kind of practical problems that occur in society. His own research had a limited scope, but there’s an infinite number of possible applications. And every day new ones are added because of the changing world we live in.
“Take self-checkouts. The problem is that people steal, so you have to check them. The checks need to be effective enough to discourage people to steal, but you don’t want to carry out too many of them because this defeats the purpose of having self-checkouts.” This is one of the many examples of practical situations you can model as a queue to arrive at the ideal solution.
“Mathematical models are always an approximation of reality, which sometimes means the solution is stylized, but they help us to better understand these systems, which enables us to develop better models,” Schol emphasizes. “As someone (statistician George Box, ed.) once said: ‘All models are wrong, but some are useful.’”
Discussion