User Tools

Site Tools


vidi:research_topic

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
vidi:research_topic [Tuesday, 17 March 2009 : 14:21:08]
lefeber
vidi:research_topic [Tuesday, 17 March 2009 : 14:31:59] (current)
lefeber
Line 1: Line 1:
 +====== Research proposal ======
 +=====Research topic=====
 +Networks with material or information flows are all around, e.g. manufacturing
 +systems, supply chains, electricity networks, communication networks, urban
 +road networks, etc.
 +
 +|   {{ vidifig1.png?​800}} ​   |
 +|   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.
  
vidi/research_topic.txt · Last modified: Tuesday, 17 March 2009 : 14:31:59 by lefeber