Scheduling Activity

- Students will explore the use of graphs to model scheduling problems.
- Students will work as a large group to come up with a list of tasks that may be necessary for designing and building their own city from scratch.
- Students will generate estimates of the time necessary to complete the various tasks required in creating their city.
- In small groups, students will develop schedules for various independent aspects of the construction of the town, utilizing directed graphs.

- Present the students with the "Designing Your Own City" handout. Allow them to read it individually.
- Discuss with the students some of the aspects that might be involved in the construction of such a city.
- Brainstorm with the students to come up with a relatively complete list of the tasks that must be completed to finish the city. Hopefully, the students will come up with a fairly long list, including a least a few tasks that can be completed concurrently as well as some others that can not be started until others have finished.
- If the students have trouble coming up with tasks, some that may be suggested are:
- clearing trees for vehicles to enter the area
- laying down sewer lines
- putting up electric lines
- paving the roads
- building utility plants
- installing phone lines
- building bridges to get to the island
- putting up street lights and traffic lights
- landscaping around the new houses
- landscaping around the new roads

- Have the class estimate the time it would take each task to be completed individually.
- Based on these values, have the class estimate how long it will take to complete construction of the city. Record the estimates.
- (May be reserved until after the activity has been completed) Introduce to the students how a graph can be utilized to depict the relationships among the tasks. Present and discuss transparency TM 4.4 (scheduling graph for the Polaris missile) from the DMTA Instructor's manual.
- Divide the class into small groups and give each group the task of deciding what other tasks must be completed before each of the tasks can start.
- From their decisions, have each group create a graph to represent the scheduling of the tasks.
- Ask each group to create an algorithm that will allow them to determine the minimum time needed to complete the construction.
- When the small groups are finished, have each one present a convincing argument as to why their schedule is the correct one and how they decided upon it and the minimum time for completion.
- Work as a group to decide on a consensus as to which schedule seems the most reasonable.
- Compare the calculated completion times with the estimated times from before the groups completed their work. If there are any jobs that can be completed simultaneously, and if the estimates were based on adding all of the times for each of the tasks, the time based on the new schedule should be somewhat shorter.
- Discuss the students' work as it relates to graph theory and modeling.

graphs, digraphs, vertex, edges, weighted graph, critical path, earliest start time, task table

optimization, modeling

- any class where the students are expected to derive and defend their own algorithms;
- a geometry class as an introduction to symbolic graphs.

- Questions for Further Discussion:
- If we wanted to speed up the completion of the project, which task should we try to speed up?
- How do construction companies actually implement scheduling of tasks? Are there any major projects going on in the neighborhood that could be explored?

- If you need to cook dinner for a group of friends, what things must you get done, and how long will the each take to accomplish? In what order should these be done, and how early should you start to prepare for the dinner?
- Similar questions for preparing a research paper for school.

This opportunity of expansion into other fields can lead to some difficulty. As far as this activity goes, it appears that unless the task is narrowed down substantially, there are too many areas for discussion which are tangential to the final goal of project scheduling. Unless a list of tasks, their specific times and prerequisites are given to the students at the beginning of the activity, there is too much opportunity for discussion about how a construction project can be accomplished. Topics such as whether different underground lines can be run simultaneously (water, sewer, cable, etc.) or how to actually route the cables can derail the discussion, and shift the focus away from actually scheduling the tasks. Although this may be desirable if an open-ended discussion is acceptable, it makes the time required for the activity increase drastically.

The tangents that come up because this is a real-world situation, while possibly being too overwhelming for a short activity, make this problem that much more attractive to a student. Since there is a clear connection to a easily understandable problem, the students may find it something interesting to explore.

Note that this basic idea of designing a city has been implemented in varying degrees as a large framework for many topics. See the article "Design Your Own City: A Discrete Mathematics Project for High School Students", by Carol A Bouma, in the 1991 NCTM yearbook.

Crisler, N., Fisher, P., & Froelich, G. (1994). Discrete Mathematics Through Applications. New York: W. H. Freeman and Company.

Kenney, M. J., & Hirsch, C. R. (Eds.). (1991). *Discrete Mathematics Across the Curriculum, K-12*. Reston. VA: National Council of Teachers of Mathematics.

Tucker, A., (1984). Applied Combinatorics. New York: John Wiley & Sons.

Peressini, et al. (1992). Precalculus and Discrete Mathematics. Glenview, Illinois: Scott, Foresman and Company.

Dossey, J., Otto, A., Spence, E., & Vanden Eynden, C. (1993). Discrete Mathematics. Harper Collins College.

McEliece, R., Ash, R., & Ash, C. (1989). *Introduction to Discrete Mathematics*. New York: Random House.