## Description

1 Critical Path Method

Consider the example given in the Figure. Note that this is an example of activities-on-arcs

formulation (not an activities-on-nodes as shown in class).

Perhaps the pouring of the concrete foundation (activity A-B), happens at the same time

as the pre-assembly of the roof trusses (activity A-D). However, the finalization of the roof

(activity D-E), cannot begin until both A-D and B-D (assembly of the house frame), are done.

Of course B-D cannot start until the concrete foundation has been poured (A-B). All of this

precedence and parallelism information is neatly captured in the PERT diagram.

1.1 Problem

Find the critical path and the project completion time. Make sure you explicitly list out the

critical activities in your listing file.

1.2 Problem

If the project takes longer to complete than you have available, then you will have to spend

some money to speed things up. But which activities should you speed up? Suppose that the

following time/cost tradeoff is allowed for certain activities:

Now every activity can have a duration somewhere dij and Dij . The values for Dij are

given in the figure, Cdij = 5 and CDij = 3 while the values of dij are given in the table below.

How much would it cost to complete the overall project in 25? What about 20? Do the

critical activities change? Be sure to note the critical activities and the start times explicitly.

Problem 1 Page 1

CS635 Problem Set #5 Prof. Michael Ferris

1.3 Problem

Now suppose that you only have 8 workers to complete the project and that each activity

requires the following number of employees:

Activity Workers needed dij

A-B 3 3

A-D 4 2

B-C 2 2

B-D 2 4

B-E 3 6

C-E 2 5

C-G 1 2

D-E 3 5

D-F 1 8

E-F 1 6

E-G 1 4

E-H 1 2

F-H 1 2

G-H 1 4

Can you set up and solve a mixed integer program to find the minimum makespan under

the constraint that no more that 8 workers are used at any given time?

2 Dragon Transport

Given your great Optimization Wizard training, the Ministry of Magic has asked that you

transport 20 dragons from Romania to Hogwarts for the Triwizard tournament. The dragons

will be transported on a route through five cities, with a choice of three different modes of

transport between each of the pairs of cities on the route. The route to be followed is exactly:

1. Romania

2. Transylvania

Problem 2 Page 2

CS635 Problem Set #5 Prof. Michael Ferris

3. Egypt

4. Godric’s Hollow

5. Hogwarts

On each leg of the rout, the dragons are to all be transported by Hogwarts Express (Train),

Portkey, or Thestral. In any of the intermediate cities, it is possible to change the mode

of transport, but you must use a single mode of transport for all the dragons between two

consecutive cities. Table 1 lists the cost of transport in galleons per dragon between the pairs

of cities.

Table 1: Transportation Costs Between Locations on Route

Pairs of cities

1-2 2-3 3-4 4-5

Train 30 25 40 60

Portkey 25 40 45 50

Thestral 40 20 50 45

Table 2 shows the cost of changing the mode of transport in galleons/dragon. (This cost

is independent of the location at which the change is made).

Table 2: Mode Change Costs

From/To Train Portkey Thestral

Train 0 5 12

Portkey 8 0 10

Thestral 15 10 0

2.1 Problem

How should the transport be organized to minimize the cost? What is the minimum cost for

transporting the 20 dragons?

3 Generation capacity

PSI believes they will need the amounts of generating capacity shown below during the next

5 years:

set year /1*5/;

set plant /p1*p4/;

parameter reqCap(year) “in million Kwh” /

1 80

2 100

3 120

4 140

Problem 3 Page 3

CS635 Problem Set #5 Prof. Michael Ferris

5 160

/;

The company has a choice of building (and then operating) power plants with the specifications shown below:

set dfields /

genCap generating capacity in Million Kwh

cCost construction cost in Million $

opCost annual operating cost in Million $

/;

table data(plant,dfields)

genCap cCost opCost

p1 70 20 1.5

p2 50 16 0.8

p3 60 18 1.3

p4 40 14 0.6 ;

3.1 Problem

Formulate and solve an IP to minimize the total costs of meeting the generating capacity

requirements of the next five years.

3.2 Problem

Now suppose that at the beginning of year 1, power plants 1-4 have been constructed and

are in operation. At the beginning of each year, PSI may shut down a plant that is operating

or reopen a shut-down plant. The costs associated with reopening or shutting down a plant

are shown below:

set action /reopen,shutdown/;

table costs(plant,action) in Million $

reopen shutdown

p1 1.9 1.7

p2 1.5 1.2

p3 1.6 1.3

p4 1.1 0.8 ;

Formulate and solve an IP to mimimize the total cost of meeting the demands of the next

five years.

Problem 3 Page 4