A+ » VCE » Further Maths U3 & 4 Master Notes » OA2 Networks and Decision Mathematics » FM Networks and Decision Mathematics

FM Networks and Decision Mathematics

7.4 Using Crashing to Reduce Completion Time

Note: if you cannot remember how to determine the critical path of an activity network, revise notes for 7.3 Determine Critical Paths and Float Times.

Crashing

  • Crashing refers to the process of reducing the duration of one or more activity in a project and then recalculating the project duration.
  • Crashing could represent anything that reduces the duration of an activity, such as hiring more staff, favourable weather, utilising more efficient methods, etc.
  • Crashing an activity on the critical path will generally lower the project duration.
  • Crashing an activity which is not on the critical path will not change the project duration.
Read More »7.4 Using Crashing to Reduce Completion Time

7.3 Determine Critical Paths and Float Times

Note: if you cannot remember how to apply forward and backward scanning, revise notes for 7.2 Forward and Backward Scanning.

Float Times

  • The float time for an activity is the difference between its latest start time (LST) and earliest start time (EST).
  • This represents the amount of time the individual activity can be postponed without changing the duration of the project overall.

Example

Picture 5

Above is an activity network which has undergone forward and backward scanning to determine the EST and LST of each activity. The float times of each activity can be calculated from these values:

Read More »7.3 Determine Critical Paths and Float Times

7.2 Forward and Backward Scanning

Note: if you cannot remember how to construct and analyse an activity network, revise notes for 7.1 Activity Networks.

Scheduling Problem

  • It is a problem of determining the minimum completion time for a project given its events.

Earliest Start Time (EST)

  • The earliest possible time that an activity can start.
  • The earliest finishing time of an activity = EST of an activity + Duration of an activity

Forward Scanning

  • Forward scanning is a methodical process for finding the earliest start time (EST) for each activity in an activity diagram. The process works as follows:
Read More »7.2 Forward and Backward Scanning

7.1 Activity Networks

Precedence Tables

  • A precedence table lists each activity required to complete a project and the activities which need to be completed immediately before the activity can be begin. These are arranged into 2 columns.
  • In many cases a third column is added (in the middle), listing the estimated duration of each activity.

Example

Activity

Duration (mins)

Predecessors

Boil water (B)

10

Prepare Sauce (P)

15

Cook Pasta (C)

15

Boil water

Mix Sauce and Pasta (M)

2

Prepare Sauce, Cook Pasta

Activity Networks

Read More »7.1 Activity Networks

6.2 Methods for Optimum Assignment

Note: if you cannot remember how to represent matching problems in graphs and matrices, revise notes for 6.1 Introduction to Matching Problems.

Optimum Assignment by Inspection

  • In smaller scale matching problems, it may be possible to determine the optimum assignment by inspection.
  • One method is to find the lowest weight assignment for each task, object, etc. being assigned to. If there is any conflict, then consider other tasks, objects, etc.

Example

Teacher

Banjo

Violin

Piano

Dave

10

25

35

Jill

11

15

40

Steve

10

18

46

Above is a matrix representing the time in days required for each teacher at a school to teach a beginner’s course in certain instruments. Only one teacher is required for each course and each teacher must be assigned to a course. As this is a smaller-scale problem, we will use inspection to find the optimum assignment.

Read More »6.2 Methods for Optimum Assignment

6.1 Introduction to Matching Problems

Matching Problems

  • There are many instances in which a several tasks, objects, or other needs to be assigned to a group of people, objects or other. For example, individually assigning a group of people a list of tasks. This is known as a matching problem.
  • Matching problems often have multiple solutions however there is generally one or more optimum solution. This is the one which achieves the intended result while expending the least time or resources.
  • In some cases, multiple assignments may be required for either group (e.g. a task may require many people or a person may be assigned to many tasks).

Bipartite Graph

Read More »6.1 Introduction to Matching Problems

5.2 Introduction to Dijkstra’s Algorithm

Dijkstra’s Algorithm

  • Dijkstra’s algorithm provides a methodical method for determining the shortest path between two vertices.
  • Dijkstra’s algorithm works as follows:

1.  Construct a table consisting of a row of empty elements where each column corresponds to each vertex in the network except the starting vertex, and the first (and for now only) row corresponds to the starting vertex.

2.  In each element of the row, write the weight of the edge connecting the starting vertex to the vertex of the corresponding column. If there is no edge such edge for a vertex, place a cross in that element instead.

3.  Draw a square around the lowest weight in the row.

Read More »5.2 Introduction to Dijkstra’s Algorithm

5.1 Shortest Path by Inspection

Shortest Path Problems

  • In many cases it may be useful to determine the shortest path between two vertices of a graph. For example, for a graph representing the road network interconnecting several towns, we may want to find the fastest way of getting from one town to another.
  • The shortest path between two vertices is the path with the least weight.
  • The weight of a path is found by summing the weights of each edge making up that path.

Shortest Path by Inspection

  • Finding the shortest path via inspection involves a crude trial and error approach whereby multiple possible paths are tested until the shortest is found.
Read More »5.1 Shortest Path by Inspection

4.2 Methods for Solving Flow Problems

Inspection

  • In small flow networks, it may be possible to determine the maximum flow.
  • Remember that flow networks show the capacity of each edge. The maximum flow for an edge is often limited by the capacity of other edges. For example, if a pipe capable of carrying 100L/h is attached to one only capable of 50L/h, the maximum flow through the 100L/h pipe will be limited to 50L/h.

Example

Picture 1
Read More »4.2 Methods for Solving Flow Problems

4.1 Introduction to Flow Problems

Flow Problems and Capacity

  • Many networks rely on the transport of fluids, people, objects or other quantities between different locations. Generally, the medium that is taken from one location to another (the pipe, road, etc.) is capable of transporting a certain number or amount per unit of time. This is known as the capacity.
  • Flow problems involves analysing movement through networks made up of a number of vertices connected via edges each with their own capacity.
  • In Further Maths, we will generally analyse flow problems involving digraphs.
Read More »4.1 Introduction to Flow Problems