Skills Checklist

After completing this chapter you should know how to ......

• define a directed graph?

• define flow?

• calculate the maximum flow through a network?

• draw and use a bipartite graph to solve allocation problems?

• find the optimal allocation of multiple groups of objects?

• identify predecessors of an activity?

• draw an activity network and use it to plan for a project?

• account for float times in our project?

• find the earliest starting time and latest finishing time for an

• activity in a project?

• identify the critical path of an activity network?

Lesson 1 - Flow Problems

Learning Intentions

To be able to….

• define and describe flow.

• calculate the maximum flow through a flow network by observation.

• identify cuts and calculate cut capacities.

• determine the maximum flow through a flow network by finding the

capacity of the minimum cut.

• solve flow problems by finding minimum cut capacities.

Tasks

1. Complete the worked solutions to the notes on Ex 14a and then work on Ex 14a

Homework

Complete Ex 14a

Edrolo Link

Lesson 2 - Matching and Allocation Problems (Ex 14b)

Learning Intentions

To be able to….

• define and describe bipartite graphs.

• olve assignment problems using the Hungarian Algorithm.

Tasks

1. Complete the worked solutions to the notes on Ex 14b

Homework

Complete Ex 14b

Edrolo Link

Lesson 3 - Precedence Tables and Activity Networks (Ex 14c)

Learning Intentions

To be able to….

• define and describe bipartite graphs.

• solve assignment problems using the Hungarian Algorithm.

Tasks

1. Complete the worked solutions to the notes on Ex 14c

Homework

Complete Ex 14c

Lesson 4 - Scheduling Problems (Ex 14d)

Learning Intentions

To be able to….

• understand activity networks that include weights (durations) of each

activity.

• determine the EST for activities using forward scanning.

• determine the LST for activities using backward scanning.

• calculate and understand the existence of float times for some activities.

• identify the critical path and completion time of a project.

Tasks

1. Complete the worked solutions to the notes on Ex 14d and complete Ex 14d

Homework

Complete Ex 14d

Lesson 5 - Crashing (Ex 14e)

Learning Intentions

To be able to….

• use crashing to reduce the completion time of a project.

• minimise the cost of crashing activities to achieve the maximum

reduction in completion time of a project.

Tasks

1. Complete the worked solutions to the notes of Ex 14e and complete Ex 14e

Homework

Ex 14e

Edrolo Link