Objectives:
To understand the Ford-Fulkerson algorithm and how it can be applied to model
a particular problem.
Due date: Friday, February 23rd by 11:00pm.
What to turn in:
Your submission will contain answers to the problems below. The file format of
your submission is flexible: you can submit a zip file containing PDFs, a
single PDF with all parts, or a Word document containing all parts.
How to submit:
Use the canvas page to submit your solution.
In this assignment, you will solve the processor scheduling problem described in lecture by modeling it as a maximum flow problem and then solving that problem using the Ford-Fulkerson algorithm.
The processor scheduling problem you are to solve was discussed in lecture 17. In particular, the lecture showed how the problem can be modeled as a maximum flow problem.
Unfortunately, that construction still resulted in a pseudo-polynomial time algorithm because the nodes correspond to 1-second intervals of time. If the programs run for long periods of time, we will create a huge number of nodes even if there are only a small numbrer of programs and processors.
The construction you will use below will fix that problem.
Your task is to find a feasible schedule for the problem generated on this page (link) by modeling it as a max flow problem and solving that problem with Ford-Fulkerson. To get your problem, enter your UW netid into the text box on the page and click the "Show Problem" button. (Your problem will be different from that of every other student, but everyone will be given a problem of essentially the same size.) You will need to find a schedule that runs the programs shown, within the allowed time constraints, on 2 processors.
We will find a feasible schedule by modeling this as a maximum flow problem. In particular, we will use the same construction described in lecture 17, but with one important change: rather than having intervals for consecutive 1-second periods, we will allow intervals to represent different lengths of time.
The new intervals will break up the time between the earliest release time and the latest deadline into the largest possible periods in which no interval starts or ends. In other words, every program's release time and deadline will be at the start and/or end of an interval, and for every interval, some program must release or have a deadline at its start and likewise at its end (if not, the interval is too small).
You can find these intervals manually. However, if we were writing a program to do it, the easiest solution would be to put all of the release times and deadlines into a list and sort them. The intervals will then show up as those between consecutive, distinct times in the list.
Draw the graph as described in lecture but with the 1-second intervals replaced by these larger intervals. As before, each program will have an edge with to each interval during which it can be run, but now the capacity of this edge will be the length of the time interval (which might be greater than 1). Also, the edges from the time intervals to the sink should now have capacity equal to the number of processors (2) times the length of the interval since that is the total amount of processing that can be completed during that time.
To simplify your drawings, here and below, you can leave off a capacity label on any edge with capacity 1. That is, an edge will be assumed to have capacity 1 unless labeled otherwise.
Next, you will find the maximum flow using the Ford-Fulkerson algorithm.
Recall that the algorithm starts with a zero flow and then increases it by repeatedly finding augmenting paths in the residual graph until none exist. Note that the choice of augmenting path is not specified by the algorithm, so if many such paths exist, you can pick whichever you prefer.
To show the operation of the algorithm, show each of the augmenting paths that it would choose. For each path, show the following information:
The path itself. (Just the list of vertices in the order visited, starting from the source and ending at the sink.)
The maximum amount of flow that can be pushed down the path. (This is the minimum of the capacities of the edges along the path.)
How the residual graph changes when you push that much flow along the augmenting path. Here, you only need to show the edges between consecutive nodes on the path, as the rest of the residual graph stays the same.
In order to find the augmenting paths, you will need to see the residual graph. Even though we don't want to redraw it after every augmentation, it will be helpful to see a complete picture of the graph periodically. So, in addition to the parts above, after each group of three augmentations, include a drawing of the complete residual graph. (It should be possible to draw three augmentations and the resulting residual graph all one one page. You are not required to do so, but it might make the process easier that way.)
Finally, when the algorithm terminates (because there are no paths in the residual graph from the source to the sink), draw the original graph again but with edges labeled by the flow. You can leave off any edges with zero flow.
The final step of the modeling process is to construct the solution to the scheduling problem from the flow.
Answer the following questions:
List each of the programs along with the precise time ranges and places (processor one or processor two) that it should be run. Note that the total time included across all of the time ranges listed must exactly equal the processing time of that program.
Explain why your solution includes only time ranges that start and end at integer time units.
Explain why it is always possible to find a schedule as described above from the flow produced by Ford-Fulkerson. (In particular, note that the flow does not always indicate the exact time at which the program should be run within the interval, nor does it indicate the processor on which to run. Why do you know that there is always a way to choose these so that you get a feasible schedule for the programs?)