1. Scheduling is important for medical centers schools, transportation systems, police services, and fire services. Pick one of these areas and write about the different scheduling situations that come up, the types of processors, and the extent to which the assumptions of the list-processing model hold for the area you pick.

2. Compare and contrast the basic scheduling problem we investigated with the scheduling version of the bin-packing problem.

3. One of the oversimplifications made in our discussion of scheduling was that there were no “due dates” involved for the tasks making up a job. Develop an algorithm for solving a scheduling problem under the assumption that each task has a due date as well as a time length. You will probably want to decide on a penalty amount that will occur when a due date is exceeded.

4. Consider the problem of scheduling tasks on a single machine. Design different algorithms for achieving different goals. You will probably wish to assume that each task has a due date such that if the task is not finished by this date, some penalty payment must be made.

5. Discuss the role of graph colorings for scheduling committee meetings so as to avoid conflicts. Research whether or not these ideas are used in the legislature of your home state.

6. In choosing a location (vertex) for trains to turn around in the graph shown in Spotlight 3.1 (on page 90), explain why it seems to be a much better choice to use as a place to allow the turnarounds, rather than at or at .