Scheduling

Problem of SCHEDULING using Graph Theory By : Suman Lata 3 rd CSE 121/05

Graphs 

• A graph G = (V, E) is a finite nonempty set of vertices and a set of edges 1 2

3 1 4

2 3

V={(1,2,3)} E={(1,2)} V={(1,2,3,4)} E={(1,2) (2,3) (1,3) (1,4)}

Examples of Graphs SFO SFO

Wash DC DALLAS

Airline Schedules BOS LA

Graph AirlineRoutes is represented as the pair (V,E)  V= {Bos, SFO, LA, Dallas, Wash DC}  E= {(SFO,Bos),(SFO,LA),(LA,Dallas),(Dallas,Wash DC)...}

Applications of Graph Theory (1) (2) (3) (4) (5)

Connection problem Scheduling problem Transportation problem Network analysis problem In Games and Puzzles

Scheduling A schedule is said to be feasible if it fulfills all application constraints for a given set of tasks.  A set of task is said to be schedulable if there exist at least one scheduling algorithm that can generate a feasible schedule.  A scheduling algorithm is said to be optimal with respect to schedulablity if it can always fine a feasible schedule whenever any other schedule algorithm can do so. 

Scheduling Algorithm When are schedules generated? 

Static Scheduling - schedule generated “off-line” before the tasks become ready ,sometimes before the system is in mission.

even

- schedule consist of a “time-table”, containing a explicit start and completion time for each task instance, that controls the order of execution at run time. 

Dynamic Scheduling - schedule generated “on-line”, as a side-effect of tasks being executed , that is, when the system is in mission. - ready tasks are sorted in a queue and receive access to the processor at run time based on priorities and/ or time quanta.

Static Scheduling General Properties :  Automatic techniques for schedule generation - simulate a run time system with dynamic scheduling and record the executions (start and finish time) or, - search for feasible schedule using an intelligent heuristic such as branchand-bound or simulated annealing.



Schedulability test for “free” - generated schedule can be easily checked for feasibility.

Static scheduling   

  

Advantages: • Predictable execution – Monitoring, debugging and schedulability analysis are simplified • Effective inter-task communication – Time for data availability is well known – Well suited for interfacing to TDMA networks

Static scheduling   

 



Disadvantages: • Low flexibility – Schedule cannot adapt itself to changes in the system • Inefficient for tasks with ”bad” periods – Tasks with mutually inappropriate periods gives rise to large time tables, which consumes memory

Dynamic scheduling   

     



General properties: • Mutual exclusion and precedence must be handled on-line – Support for run-time synchronization or task offsets needed • Large variety of static and dynamic priority schemes – Rate-monotonic scheduling [static priority] – Deadline-monotonic scheduling [static priority] – Weight-monotonic scheduling [static priority] – Slack-monotonic scheduling [static priority] – Earliest-deadline-first scheduling [dynamic priority] – Least-laxity-first scheduling [dynamic priority

Dynamic scheduling   

 



Advantages: • High flexibility – Schedule can easily adapt to changes in the system • Effective for different types of tasks – Sporadic tasks easily supported (via suitable priority assignment) – Implementation is not affected by task characteristics

Dynamic scheduling   

  

Disadvantages: • Less predictable execution – Temporary variations (jitter) in periodicity can occur • Complicated inter-task communication – Task must synchronize to exchange data – Difficult to adapt to TDMA networks

Some Problems Based On Scheduling 1. 2.

Crew Scheduling Hospital Scheduling

CREW Scheduling Problem Definition 



Assignment of well-defined tasks (pairing & shift construction) to a group of people while respecting a set of complicated legality rules and resource constraints. Most of the legality rules are non-linear and evolving through time

Crew Pairing Solution Methodology 



Crew Pairing and Crew assignment are too big to be solved together A good solution for Crew Pairing is a must for the efficient and productive use of the airline crews

Airline Crew Scheduling 

Entities of the problem 

 

Flight Leg: A non-stop flight with its crew complement and fleet requirements Duty: A legal sequence of legs for one day Pairing (Trip): A legal sequence of duties 



Pairings start and end at the same crew base

Roster: A set of pairings and other activities assigned to a specific crew member

Airline Scheduling   

The Problem Designing the Algorithm Analyzing the Algorithm

The Problem Suppose u are in charge of managing a fleet of airplanes and u would like to create a flight schedule for them. Here is a very simple model for this. Your market research has identified a set of m particular flight segments that would be very lucrative if u could serve them; flight segment j is specified by four parameters: its origin airport, its destination airport, its departure time and its arrival time. e.g. There is a list consist of six flight segments you would like to serve with your planes over the course of a single day: (1) Bostan (depart 6 A.M.) – Washington DC (arrive 7 A.M.) (2) Philadelphia (depart 7A.M.) – Pittsburg (arrive 8 A.M.) (3) Washington DC (depart 8 A.M.) – Los Angles (arrive 11 A.M.) (4) Philadelphia (depart 11 A.M.) – San Francisco (arrive 2 P.M.) (5) San Francisco (depart 2:15 P.M.) – Seattle ( arrive 3:15 P.M.) (6) Las Vegas (depart 5 P.M.) – Seattle (arrive 6 P.M.)

It is possible to use a single plane for a flight segment i , and then later for the flight segment j, provided that (a) the destination of the i is the same as the origin of j , and there is enough time to perform maintenance on the plane in between; or (b) you can add a flight segment in between that gets the plane from the destination of i to the origin of j with adequate time in between. For example ,an hour for intermediate time, you could use a single plane for flights (1), (3) and (6) by having the plane sit in Washington , DC , between flights (1) and (3) , and then inserting the flight in between flight (3), and (6).

Formulating the Problem 







We will simply say that flight j is reachable from flight I if it is possible to use the same plane for flight I, and then later for flight j, as well. so under above rules (1) and (2) , we can easily determine for each pair i, j, whether flight j is reachable from flight i. The input to the problem will include not just the flight segments, but also a specification of the pairs (i , j ) for which a later flight j is reachable from an earlier flight i. The goal in this problem is to determine whether it is possible to serve all m flights on your original list, using at most k planes total. In order to do this there is need to find a way of efficiently reusing planes for multiple flights. For ex. k= 2 planes. If we use one of the planes for flights (1) , (3), and (6), we would not be able to serve all the flights (2) , ( 4), 950 with the other.However ther is a solution to serve all the six planes flights using two planes, via a different solution: one for the flight (1) , (3), (5), and other plane for the flight (2), (4), and (6).

Designing the Algorithm 





The solution is based on the following idea. Units of flow will correspond to airplanes. We will have an edge for each flight, and upper and lower capacity bounds of 1 on these edges to require that exactly one unit of flow crosses this edge. In other words, each flight must be served by one unit of the planes. If ( ui and vi ) is the edge representing flight i , and ( u j , v j ) is the edge representing flight j, and flight j is reachable from flight I, then we will have an edge from vi to uj with capacity 1; in this way, a unit of flow can traverse ( u i, vi) and then move directly to ( uj , vj). The node set of the underlying graph G is defined as follows. - for each flight I, the graph G will have the two nodes ui and vi. - G will also have a distinct source node s and sink node t.

(cont………) T he edge set of G is defined as follows. (2) For each i, there is an edge (u i , v i) with a lower bound of 1 and a capacity of 1. (3) For each i and j so that flight j is reachable from flight i , there is an edge (v i, u j ) with a lower bound of 0 and capacity of 1. (4) For each i, there is an edge (s, u i) with a lower bound of 0 and capacity of 1. (5) For each j, there is an edge (v j, t) with a lower bound of 0 and capacity of 1. (6) There is an edge (s, t) with lower bound 0 and capacity k. (If we have the extra planes , we don’t need to use them foe any of the flights.) Finally , the node s will have a demand of –k , and the node t will have a demand of k.All other nodes have a demand of 0.

Solution Approaches for the Crew Pairing Problem 

Generate and Optimize  

  

Select sub-problems (Heuristic filtering) Phase 1. Generate a large set of legal pairings (Generate) Phase 2. Select the best pairings (Optimize) Iterate Column Generation

Analyzing the Algorithm 

There is a way to perform all flights using at most k planes if and only if there is a feasible circulation in the network graph G. Proof: Suppose , there is a way to perform all flights using k’ < k planes .The set of flights performed by each individual plane defines a path P in the G, and we send one unit of flow each such path P. To satisfy full the demand at s and t , we send k - k’ units of flow on the edge (s, t). The resulting circulation satisfies all demand, capacity and lower bound conditions. We know that there is a feasible circulation with integer flow values. Suppose that k’ unit of flow are sent on edges other (s, t). Since all other edges have a capacity bound of 1, and the circulation is integer valued , each such edges that carries flow has exactly one unit of flow on it. Now we take the situation is easier here since the graph has no cycles. Consider an edge (s, u i) that carries one unit of flow. It follows by the conservation that ( u i, v i) carries one unit of flow and there is a unique edge of v i, that carries one unit of flow. If we continue in this way , we construct a path P from s tot, so that each edge on this path carries one unit of flow. Now , for each path P we create in this way, we can assign a single plane to perform all the flights connected in this graph. Proved

Airline scheduling problem BOS 6

DCA 7

PHL 7

PIT 8



DCA 8



SFO 2:15

LAX 11

SEA 3:15

PHL 11

LAS 5

SFO

SEA 6

The scheduling problem solution BOS 6

DCA 7

PHL 7

DCA 8

PIT 8

LAX 11

PHL 11

LAS 5

SFO 2

SFO 2:15

SEA 6

SEA3:15

Modeling Approach 



 

A binary variable (column) represents a legal schedule of a person that covers a set of tasks Each variable (column) embeds all non-linear legality rules Legality rules are external to the model Constraints ensure the covering of all tasks

THANK YOU