Assignment 1. The following project consists of 8 activities, which have been labelled A to H:
| Activity |
Time(days) |
Precedences |
| A. |
5 |
|
| B. |
7 |
|
| C. |
6 |
|
| D. |
3 |
A |
| E |
4 |
B,C |
| F. |
2 |
C |
| G. |
6 |
A,D |
| H. |
5 |
E,F |
(a) Draw the corresponding AON network for the project.
(b) Draw the corresponding AOA network for the project.
(c) Calculate the total float for each activity.
(d) Find all critical paths in the AON network.
(e) Find the minimum amount of time required to complete the project.
(f) What is the effect on minimum completion time if F is delayed by 3 days?
(g) What is the effect on minimum completion time if E is delayed by 3 days?
2. Consider the network below:
(a) Write down the node-node adjacency matrix for the given network using the formula
{ 1, if nodes i and j are connected by an edge
A = [aij], aij, =
{ 0, otherwise.
(b) Assume that the nodes are ordered as s, p, q, y, u, x, w, t in the rows and columns of A. Without doing any matrix multiplication, write down the top row of A2, and explain your reasoning.
(c) Draw a tree, with root s, indicating a shortest path from s to all the other nodes.
(d) Using the data in your tree, employ the recursive algorithm from class to compute the number of shortest paths from s to t.
(e) Without doing any matrix multiplication, state the entry in the row of node s and the column of node t in A3.
3. (a) For the AON activity network
write down the matrix Q relevant to the max-plus calculation of the earliest start times.
(b) Without doing any explicit max-plus matrix calculations, give the value of
[0 -∞ -∞ -∞ -∞ -∞ -∞ -∞] ⊗ Q5
(c) Consider an AON activity network. Let p equal the maximum number of directed edges in a path of the network. Give a description for a matrix Q˜, a column vector x~, and an analogue of a max-plus operation ⊗˜ such that computing Q˜p⊗x~ will give the latest finish
times at each node. Demonstrate your method on the AON network below.
