Index

Discrete Mathematics Project
Scheduling Activity

Title

Design Your Own City (Jim Arnow)

Goals

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.

Abstract

This activity focuses on modeling and scheduling projects. Students are asked to decide on a number of tasks that must be completed in order to design a small town, and must then utilize graph analysis techniques to determine an optimum schedule. This activity may be used as an introduction to graph theory, or near the beginning of an integrated exploration into city design, incorporating a variety of topics from not only mathematics but any of a spectrum of outside courses.

Problem Statement

The students are put in charge of scheduling the construction of a new city. The street layout has already been determined for them, but they must determine an efficient way to complete the construction. To efficiently model the problem, the students will be introduced to a scheduling graph and a task table.

Instructor Suggestions

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.

Materials

Transparency TM 4.4 from DMTA Instructor's Manual, "Designing Your Own City" handout, Chalk- or dry-erase board, scratch paper, pencils.

Time

Introduction of problem statement: (5 min.), discussion of tasks: (15 min.), estimating time: (5 min.), introduction of relevant graph theory concepts: (15 min.), small-group work (20 min.), presentation of small-group work and large-group discussion (20 min.)

Mathematics Concepts

Discrete Mathematics Concepts

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

Related Mathematics Concepts

optimization, modeling

NCTM Standards Addressed

Mathematics as Problem Solving, Mathematics as Communication, Mathematics as Reasoning, Mathematical Connections, Discrete Mathematics, Geometry from a Synthetic Perspective

Colorado Model Content Standards Addressed:

Number Sense (1), Algebraic Methods (2), Data Collection and Analysis (3), Geometric Techniques (4), Linking Concepts and Procedures (6)

Curriculum Integration

This activity could be integrated into

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

Further Investigation

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?

Similar activities:

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.

Variations/Comments

This direction of research (construction of a city) lends itself easily to a variety of other areas of study. For instance, the students can examine various types of circuits and paths in designing roads, they can use minimal spanning trees to design an appropriate way of routing the cable service, they could design emergency preparedness plans by deciding which roads should be repaired first also based on minimum spanning trees or they could design recycling or mail delivery routes(see the Designing Recycling Routes activity. Other subjects such as art, social science and ecology can easily be introduced into the considerations.

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.

Send your variations and comments to this Web page's editor

References:

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.

Discrete Mathematics Project Scheduling Activity