Lesson 8: Solving scheduling problems
Opening the garden sooner
SkillsScheduling problemsCritical paths
Worked example
The committee wants the garden open sooner. Extra volunteers can cut the time to build the beds (, 6 days), but hiring tools for them costs $300 for each day saved. No other activity can be shortened.
(a) Find the least cost of opening the garden in 17 days.
(b) Show that the garden cannot open in 15 days this way.
Step 1: List the paths
––––: 20 days. ––––: 16 days. –––: 14 days.
Step 2: Shorten E for 17 days
Only the first path is longer than 17 days, and it contains . Cut by 3 days to 3 days: the path becomes . The others are already shorter.
Step 3: Try for 15 days
–––– takes 16 days and does not contain . However much is cut, that path still takes 16 days.
Once another path is the longest, it is critical, and shortening the old critical path gains nothing more.
Step 4: Find the best possible
Cutting by 4 days (to 2) gives two critical paths of 16 days. Any further cut is wasted money.
Answer
(a) Shorten by 3 days, at a cost of $900. (b) –––– takes 16 days and does not include , so the garden can open no sooner than 16 days by shortening .
Try a similar one
A fresh question of the same kind, checked as you answer, with hints and a full solution.
Method
List the path lengths.
Shorten critical activities only, one day at a time, rechecking every path.
Stop when another path not containing the activity becomes the longest.
Watch out for
Cutting by 5 days for "15 days": –––– is untouched at 16 days.