Scheduling to Minimize Lateness: An Exchange Argument

In this section we look at solving another scheduling problem where there is one resource and a set of requests to use that resource for a certain amount of time. Each request has a deadline and a time interval length and can be scheduled any time before the deadline. Different requests cannot overlap. An example of this problem is scheduling jobs to minimize lateness. The algorithm must determine a start and a finish time for each request. If the finish time of a request is greater than the deadline then we note that the job is late. The lateness of a job is calculated by the finish time minus the deadline. If the request is not late then the lateness is 0.

The Algorithm:

There are two greedy ways to approach the problem and sort the data:

• order the jobs smallest to largest by the length of the job
• order the jobs smallest to largest by their slack times (deadline minus the length of the job)

Both of these approaches fail and will not produce the optimal solution. Our approach will be to sort the jobs by their deadlines in increasing order. The jobs will be scheduled in this order with each job's start time beginning at the previous jobs finish time.

  Order the jobs in order of their deadlines
  Assume the notation that d<sub>1</sub> =< ... =< d<sub>n</sub>
  Initially f = s
  Consider the jobs i = 1,...,n in this order
     Assign job i to the time interval from s(i)=f to f(i)=f + t<sub>i</sub>
     Let f = f + t<sub>i</sub>
  End
  Return the set of scheduled intervals [s(i),f(i)] for i = 1,...,n
  

Analysis

The solution that is produced from this algorithm does not have any idle time, meaning that there are no gaps between jobs where the machine is not doing anything and there are still jobs to complete.

(4.7) There is an optimal schedule with no idle time.

To prove that our solution is optimal and the maximum lateness is minimized, we use the exchange argument. We consider an optimal schedule O and modify O to transform it to the schedule that our greedy algorithm produced. If a schedule puts a job with a greater deadline ahead of a job with a smaller deadline, then we say that schedule has an inversion. Our greedy algorithm produces a schedule with NO inversions.

(4.8) All schedules with no inversions and no idle time have the same maximum lateness

Proof

If there are two schedules without idle time or inversions, they can only be different in the order they schedule jobs with the same deadline. Jobs with the same deadline are scheduled consecutively and the last one as the maximum lateness which is not affected by the order of the jobs. To prove this we take an optimal schedule with no idle time and convert it to a schedule with out any inversions. The changes we make to the schedule will not increase the maximum lateness. So both schedules are optimal

(4.9) There is an optimal schedule that has no inversions and no idle time

Proof

Start with an optimal solution O with no idle time. The schedule can have at most n/2 inversions if all of the pairs are inverted.

1. if O has an inversion, there is a pair of jobs where the one with the later deadline is scheduled before the one with the earliest deadline
2. after swapping the jobs we get a schedule with one less inversion
3. the new swapped schedule has a maximum lateness no greater than that of O

To prove the new schedule's lateness is no greater than the original solution, we show that the by swapping the two jobs their lateness is either the same or it is less. Swapping them cannot make a greater lateness.

(4.10) The schedule A produced by the greedy algorithm has optimal maximum lateness L.

Shortest Paths in a Graph

We want to be able to find the shortest path from one node to a goal node with a simple algorithm. One example of how we might use this is navigating to a webpage or finding the shortest route to a location. Given a directed graph with a start node we assume that there is a path to every other node in the graph and each edge has a length or weight greater than 0. The length of a path is the sum of the weight of all of the edges in the path. We want to find the minimum path.

Design We start with Dijkstras algorithm. We determine the length of the shortest path by exploring out from our start node and adding to the set each node that has the shortest path distance from s.

  Dijkstra's Algorithm (G, l)
  Let S be the set of explored nodes
      For each u in S, we store a distance d(u)
  Initially S is empty and d(s)=0
  While S is not equal to V
      Select a node v not in S with at least one edge from S for which d'(v) = min<sub>e=(u,v):u in S</sub>d(u)+l<sub>e</sub> is as small as possible
      Add v to s and define d(v) = d'(v)
  Endwhile