Home

9/26/2018

A review of the architecture we are using for the scheduler and simulator.

Notice the two main sections: the scheduler and the 'world simulator'. It can get a little confusing because the scheduler itself has the ability to 'simulate' a schedule into the future in order to determine whether a schedule is valid. In other words the scheduler uses a simulator to determine whether there are conflicts in the schedule it is generating. It has an uncertainty model which is probabilistic based. It infers the potential for delay from this model and schedules accordingly.

The simulator itself has an uncertainty model that is used to inject delays into the simulation.

Let's consider a simple scheduling problem with no uncertainty.

Here we are considering only departures. The node-link model has a numeric label on the edges. These indicate the distance (or maybe time it takes to go) between the nodes. This information could be used by both the scheduler and simulator.

The input is a scenario. It is a tuple (aircraft, gate, release_time). Each aircraft is given a predefined route; for example, aircraft Blue is given the route 0 --> 3 --> 4 --> 5, where 5 is the terminal (runway) node. Notice how conflicts arise: if Green and Blue are both released at their specified release_time then they both occupy node 3 at the same time. In this simple model, that is the definition of conflict: two aircraft occupying the same node at the same time. The scheduler resolves conflict through delaying one of the aircraft. So even for this simple example, it is necessary for the scheduler to insert a delay in the schedule to avoid conflict.

A schedule is a set of locations (nodes) and times to each of the aircraft. A conflict-free schedule is one in which you don't have a pair (n, t), (n,t) of same node and time for different aircraft. There's an example of a conflict-free schedule in the figure. Notice that the travel times between nodes are included in the schedule: for example, the Red aircraft goes from node 2 at time 7 to node 4 at time 10, indicating that it take 3 time units to go between them.

Notice that I included a simple scheduling sequence, based on something like a 'first come first served' method. In this way, you try to schedule each aircraft based on their release time. If there is a conflict detected, you delay one of them at a previous node. This is an intuitive way to schedule.

Some schedules are better than others. There are many different ways of comparing schedules and deciding which are better. One common measure is called 'makespan'. In this example, this is the time that the last aircraft takes off, which is time 15. More generally, makespan is the time it takes to process all of the 'jobs'.

Here's a slightly more complicated example with arrivals and departures.

Notice in this case the scenario consists of indicating whether the aircraft is arriving or departing. Also the scenario has the predefined route attached. The route is something that the scheduler could assign as a step in the scheduling process. In this example, node 5 is attached to a departure runway, and node 6 is attached to an arrival runway. Notice that all arriving flights start at the same node, whereas all departing flights finish at the same node (both are runway nodes).

Try to generate a good schedule for this problem. How would you use a first-come-first-served approach to scheduling?