In the Beyond Numbers exhibit,
visitors are challenged to organize morning tasks so they can leave the
house in record time. Exhibit labels relate this activity to managing the
Apollo space program:
"I believe that this nation should commit
itself to achieving a goal, before this decade is out, of landing a man
on the moon..."
- John F. Kennedy, May 27,1961
On July 20, 1969, just eight years after Kennedy's
speech, Apollo 11 landed two men on the moon. This achievement was possible
only with careful production planning that included the critical path method.
NASA used the critical path method to help determine an efficient schedule
for the tasks that led to the moon landing. In this exhibit, you used the
critical path method to organize your morning.
NCTM
Standards and/or AAAS Benchmarks addressed:
Mathematics as Problem Solving: Students develop and apply a variety
of strategies to solve problems, with emphasis on multi-step and nonroutine
problems.
Mathematics as Communication: Students model situations using oral, written,
concrete, pictorial, graphical and algebraic methods.
Mathematics as Connections: Students explore problems and describe results
using graphical, and verbal mathematical models or representations..
The Nature of Mathematics, Patterns, and Relationships: Students know that theories and aplications
in mathematical work influence each other. Sometimes a practical problem
leads to the development of new mathematical theories; often mathematics
developed for its own sake turns out to have practical applications.
VOCABULARY
vertex (vertices) - point or corner
where edges meet
edge - a line or border graph - in this
lesson, a network of vertices connected by edges directed
graph - a graph that has vertices connected
by edges that can be followed in only one direction
critical path - in a directed graph, with
"lengths" marked on edges ("length" may represent time, or distance, or
cost, depending on the application), a critical path is a directed path
of maximum total length, i.e. maximum sum of the numbers marked on edges.
This then represents the minimum time to do the entire set of tasks in
a project.
INTRODUCTION
"Scheduling used to be a trial-and-error procedure. Someone
tried out a schedule and tinkered with it to see if it got better. If no
improvement occurred, someone else would tinker in a different way....
Modern mathematics has offered a broad array of optimization techniques
and other tools to assist with the solution and understanding of scheduling
problems."
-Joseph Malkevitch,
In
Discrete Mathematics, Issue #5
In a homework problem, students experiment with scheduling in preparation
for a band concert. Then they are shown the critical path method of scheduling.
With this method, which they apply to a band set-up situation, they will
not only organize their time, but they will find out the minimum amount
of time needed for the whole setup to be done. To continue the music theme,
the attached copy of In Discrete Mathematics offers an activity using "Two-
Processor Scheduling" to arrange music on a tape. [In Discrete Mathematics,
reprinted here with permission, is a periodical that may be useful for
many modern mathematics topics. Subscription information is included in
your sample issue.]
OBJECTIVES
Students will create a directed graph and identify a critical path to find
out how long a project takes.
MATERIALS
Task lists 1 and 2 scissors for each student
Optional: copies of task lists on acetate for an overhead projector
PROCEDURE
Activity 1 - Lines of symmetry
Give each student the Task List 1 and post the following problem as
a homework assignment:
"Your band sent its demo tape to your favorite musicians and
now they've asked you to open for them at the Hollywood Bowl. You have
four months to get ready and lots to do. There are five people in the band
to share the work. You need a schedule to get it all done.
The list before you explians the things that need to be done.
Your challenge is to make a schedule for the next four months. Use any
method you can devise."
When the assignment is turned in, have the students explain their
strategy of scheduling to the class. Allow others to evaluate, extend or
elaborate on the presentations.
Suggest that one might want to know the shortest amount of time in which
the entire job could be done. Have the class decide what the minimum time
(in days) spent on each task would be. Representing each task with a letter,
decide which tasks must precede others. Form a directed graph with arrows
pointing from a task to every task that can be done immediately after it.
Mark the time needed to complete the task at the tail of the arrow. Find
which path is longest ("longest" should be read as most time consuming,
not consisting of the largest number of tasks). Point out that this longest
time chain will be called the "critical path". Its length determines the
shortest amount of time in which the whole job can get done. In the sample
solution on the next page, the darkest path is the critical path.
Have students apply their understanding of the critical path method
by scheduling the concert.
Call on students to estimate the time needed to do each task and have
everyone write the agreed time in the space provided. Let them cut out
the pieces and rearrange a scheduling list.
Extension: Use the activity "Packing and Scheduling" described on page
2 of In Discrete Mathematics as a problem on how to organize the songs
on the band's first album.
Assessment:
Have students draw a directed graph of what they need to do before leaving
their home on a school-day morning. Have them identify the critical path
in their graph.
Task List 1
Your band sent its demo tape to your favorite musicians and now they've
asked you to open for them at the Hollywood Bowl. You have four months
to get ready and lots to do. There are five people in the band to share
the work. You need a schedule to get it all done.
The list before you explains the things that need to be done. Your challenge
is to make a schedule for the next four months. Use any method you can
devise.
To help you, the time to complete each task has been estimated to the
nearest half day and the items that must precede a task have been listed.
Task List 2
The equipment truck is heading for the loading dock at the Hollywood
Bowl. The concert begins at 8 pm. The truckers get paid by the hour. What
is the shortest amount of time you will need the truckers? What is the
latest time that they can arrive at the Hollywood Bowl? This time you estimate
the time to complete each task to the nearest half day and you list the
items that must precede it.
