Networks with material or information flows are all around, e.g. manufacturing systems, supply chains, electricity networks, communication networks, urban road networks, etc.
|Two examples of flow networks with setup times: a re-entrant manufacturing system (left) and part of an urban road network (right).|
From a mathematical modeling point of view we can consider these systems as flow networks of servers that switch between several types (or classes) of jobs. In this proposal we focus on networks of switched servers that require a setup time when switching from serving one type to serving another.
In a manufacturing system machines might require cleaning before a different type of job can be processed, in an urban road network some time passes after a direction has been turned red before an other direction is turned green. Due to this setup time it is advantageous to serve more than one job once the server has been set up. We are interested in the control of these networks. Servers need to decide which type of jobs to serve and for how long. They need to decide when to switch to an other type of job. Our aim is to design tailor made policies for these servers such that desired feasible network behavior is achieved.
The control of flow networks of switched servers with setup times is a challenging problem. Two important kinds of networks can be distinguished: acyclic and non-acyclic networks. A network is called acyclic if the servers can be ordered in such a way that jobs can only move from a server to a server higher in the ordering. A network is called non-acyclic if such an ordering is not possible. Re-entrant manufacturing systems, i.e. manufacturing systems where jobs visit a certain machine several times, see also Figure [vidifig1], are a typical example of non-acyclic networks. Also urban road networks are non-acyclic, as typically cars can both drive from one intersection to the other and vice-versa.
In ([#References|references]) it was shown by simulation that even when each server has enough capacity to serve all jobs, non-acyclic networks can be unstable in the sense that the total number of jobs in the network explodes as time evolves. Whether this happens depends on the policy used to control the flows through the network. In ([#References|references]) several clearing policies have been introduced: serve the queue you are currently serving until it is empty, then switch to another queue. It was shown that in a deterministic environment these policies are stable for a single server in isolation with sufficient capacity. Furthermore, it was shown that a clearing policy stabilizes a deterministic multi-class acyclic queueing network with sufficient capacity.
In ([#References|references]) it was shown analytically by means of a counterexample that using a clearing policy, non-acyclic networks might become unstable. Even deterministic systems without setup times! The main reason is because clearing policies spend too long on serving one type of job. This results in starvation of other servers and therefore a waste of their capacity. Due to this waste the effective capacity of these other servers is not sufficient anymore, resulting in an unstable system.
This observation has led to the development of so-called buffer regulators ([#References|references]) or gated policies (including <math>k</math>-limited policies). The main idea is that each buffer contains a gate, so the buffer is split into two parts: before and after the gate. Instead of switching depending on the total buffer contents, switching is now determined based on the buffer contents after the gate. As a result, a server might now leave a buffer earlier, avoiding long periods of serving one type of job. It has been shown in ([#References|references]) that under certain conditions on these regulators the (possibly non-acyclic) network is stabilized. Since non-acyclic networks are only unstable under certain conditions, applying buffer regulators is not always necessary. Unfortunately, stability for non-acyclic networks is not always easy to check a priori. However, needlessly applying buffer regulators results in a larger mean number of jobs in the network, which from a performance point of view is undesired.
In ([#References|references]) a different approach has been developed. First the minimal period is determined during which the network is able to serve all jobs that arrive during that period. Given this minimal period, or any longer period, how long each server should serve each type can be determined. Next, a controller is proposed where each server serves its buffers in a fixed cyclic order until either the buffer becomes empty or the server has spent the time reserved for serving that type. In the former case, the next setup is prolonged to make sure that the time reserved for serving a type is fully used. It was shown that this policy guarantees stability of the controlled system and that for constant arrival rates the behavior of the network eventually becomes periodic.
The above mentioned references are only a few of the large amount of papers that have been published in this area, or related subjects such as (dynamic) lot sizing problems and polling models, see also ([#References|references]) and references therein. However, most of these papers have one thing in common: first a policy is proposed, and then the resulting behavior of the network under this policy is considered. When performance is considered, mostly the system behavior is optimized over a family of considered policies. A strength of existing results is that they often can be applied to any network and that stability is guaranteed. However, stability is only a prerequisite for a good network control policy. It is usually unclear if the presented policies yield suitable network performance. In particular it is not clear how to obtain desired network behavior.
Instead of having one policy which works for any network, it is better to have a general methodology for designing a tailor made policy for the network under consideration, depending on the desired performance. In this project we propose an entirely different way of looking at the problem of controlling a network of switching servers with setup times. Instead of starting from a policy and then analyzing the proposed policy, we start from a priori specified desired network behavior. Using this desired behavior for the network under consideration as a starting point, we derive a policy for this network which guarantees convergence of the system towards this desired behavior. Though the policy is tailor made for both the network under consideration and its desired behavior, we aim for a general methodology that is applicable to arbitrary networks and arbitrary feasible network behavior.