Description
Formulate the following problems in GAMS and solve them. Please follow the instructions given in the problems closely. Submit this assignment electronically to the drop box
as a single zip file. This zip archive should contain exactly 3 files with the following names:
hw5-1.gms, hw5-2.gms, hw5-3.gms
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