Assignment 4: Project Scheduling

A project, such as a construction project, consists of numerous individual tasks. Each task has dependencies (other tasks that must be completed first) and resources requirements (e.g. personnel and equipment). A task cannot be scheduled before its dependencies are satisfied and its required resources are available. For example, one cannot pour the concrete before the foundation is dug. A valid project network does not contain any circular dependencies.

For this assignment, you will write a program called schedule that reads a project description file from standard input and produces a schedule, or reports that a schedule is impossible because of a circular dependency.

Input Format

To keep this assignment manageable we will make a few simplifying assumptions.

• tasks are words as read by the C++ istream operator<< (separated by whitespace)
• task duration is specified in number of days
• once a task is started, it runs to completion without interruption
• a task is scheduled at the earliest possible time after the tasks it depends on complete
• all required resources are available and are not specified in the project description file
• there are no fixed-point constraints (e.g. no-one goes on vacation on some particular date)

A task begins with the TASK keyword followed by the task name and number of days required, followed by an optional clause for the dependencies:

TASK taskname days
DEPENDS_ON taskname...
  

Output Format

The output is a text file with columns: task-name, start-day, end-day, and duration, followed by a list of the tasks which must be completed first. If the project cannot be scheduled, the output will be the message "Cannot schedule: circular dependency".

Note: the project starts on day one, not day zero, because not everyone who manages a project is a computer scientist.

Example

Given this project (click on image to expand),

the project description file contains:

TASK build_foundation                   18
TASK framing                            16      DEPENDS_ON build_foundation
TASK windows                            3       DEPENDS_ON framing
TASK siding                             7       DEPENDS_ON windows
TASK roof                               10      DEPENDS_ON framing
TASK rough_plumbing                     5       DEPENDS_ON roof siding
TASK rough_electrical                   4       DEPENDS_ON roof siding
TASK hvac_ducts                         4       DEPENDS_ON framing
TASK floor_1_drywall                    6       DEPENDS_ON rough_plumbing rough_electrical hvac_ducts
TASK floor_2_drywall                    8       DEPENDS_ON rough_plumbing rough_electrical hvac_ducts
TASK power_hookup                       1       DEPENDS_ON rough_electrical
TASK hvac                               1       DEPENDS_ON hvac_ducts power_hookup
TASK water_heater                       1       DEPENDS_ON rough_plumbing power_hookup
TASK floor_2_bathroom_cabinets          1       DEPENDS_ON rough_plumbing floor_2_drywall
TASK floor_1_plumbing_fixtures          2       DEPENDS_ON rough_plumbing kitchen_cabinets
TASK floor_2_plumbing_fixtures          1       DEPENDS_ON floor_2_bathroom_cabinets
TASK floor_1_electrical_fixtures        3       DEPENDS_ON rough_electrical floor_1_drywall
TASK floor_2_electrical_fixtures        3       DEPENDS_ON rough_electrical floor_2_drywall
TASK floor_1_painting                   4       DEPENDS_ON floor_1_plumbing_fixtures floor_1_electrical_fixtures
TASK floor_2_painting                   5       DEPENDS_ON floor_2_plumbing_fixtures floor_2_electrical_fixtures
TASK carpeting                          2       DEPENDS_ON floor_2_painting
TASK kitchen_cabinets                   3       DEPENDS_ON floor_1_electrical_fixtures
TASK appliances                         1       DEPENDS_ON kitchen_cabinets
  

Expected output:

                build_foundation    1   18   18
                         framing   19   34   16    build_foundation
                         windows   35   37    3    framing
                      hvac_ducts   35   38    4    framing
                          siding   38   44    7    windows
                            roof   35   44   10    framing
                  rough_plumbing   45   49    5    roof  siding
                rough_electrical   45   48    4    roof  siding
                 floor_1_drywall   50   55    6    rough_plumbing  rough_electrical  hvac_ducts
                    power_hookup   49   49    1    rough_electrical
     floor_1_electrical_fixtures   56   58    3    rough_electrical  floor_1_drywall
                    water_heater   50   50    1    rough_plumbing  power_hookup
                kitchen_cabinets   59   61    3    floor_1_electrical_fixtures
                            hvac   50   50    1    hvac_ducts  power_hookup
                      appliances   62   62    1    kitchen_cabinets
       floor_1_plumbing_fixtures   62   63    2    rough_plumbing  kitchen_cabinets
                 floor_2_drywall   50   57    8    rough_plumbing  rough_electrical  hvac_ducts
                floor_1_painting   64   67    4    floor_1_plumbing_fixtures  floor_1_electrical_fixtures
     floor_2_electrical_fixtures   58   60    3    rough_electrical  floor_2_drywall
       floor_2_bathroom_cabinets   58   58    1    rough_plumbing  floor_2_drywall
       floor_2_plumbing_fixtures   59   59    1    floor_2_bathroom_cabinets
                floor_2_painting   61   65    5    floor_2_plumbing_fixtures  floor_2_electrical_fixtures
                       carpeting   66   67    2    floor_2_painting
  

Notes & Hints

For this assignment, you may use the full capabilities of the C++ language, including the STL. Have at it!

You will need to implement a topological sort, which requires vertices to hold the list of incoming edges in addition to the list of outgoing edges. The algorithm destructively modifies the set of incoming edges, so you need to make a working copy.

Bonus Marks

Cycle Detection

Printing "Cannot schedule: circular dependency" is not very helpful for the hapless project manager to figure out what the problem is. It would be really nice if the scheduler listed the dependency cycle when one is detected.

Critical Path

Independent tasks may be scheduled concurrently or sequentially; dependent tasks must be scheduled sequentially. The longest sequence of dependent tasks determines the overall length of time to complete the project and is called the critical path.

Write a stand-alone program critical_path (reusing as much as you can from schedule). While it is possible to have a tie between two different paths, the program should only identify a single critical path.

Resource Utilization

Add an optional REQUIRES resource... clause for to the project description file containing a list of resources required to complete the TASK. Assume that adequate resources are available (for example, if concurrently-scheduled tasks both require an excavator, the company will just rent a second one and bill the customer accordingly).

Resources, such as heavy equipment, may represent a large capital cost, so the decision whether to rent or buy has to be made carefully. The main factor determining whether to rent or buy is how much it gets used. Write a program called utilization that reads the project description file and lists the resources which are required for at least 80% of the project's duration.