1.
COMP9334 Solution to the revision problems for Week 9A
Chun Tung Chou March 8, 2021
(a) Let us define a few notation:
• Tmax = computation time limit = 4000s
• P = total number of cycles required = 107 Mcycles.
• pi = Speed (in Mcycles/s) of company i, e.g. p1 = 1000 Mcycles/s • ci = Per-second charge for company i, e.g. c1 = $0.1/s.
• si = Set up cost for company i, e.g. s1 = 500.
The decision variables are yi and xi (for i = 1, 2, 3): 1 if Company i is chosen
yi = 0 otherwise
xi = fraction of cycles to be bought from Company i and is ≥ 0
Based on these decision variables, we know that • Completion time T is:
• Total cost C is:
The problem formulation is
subjectto
C =
n c i P x i p +siyi
T = max P xi i pi
1
i=1 i min C
Tmax ≥ C=
xi ≤ xi = 1
3 i=1
xi ≥ yi ∈
0 {0,1}
Pxi pi
p +siyi i
1≤i≤n
1≤i≤n
1≤i≤n 1≤i≤n
n c i P x i
i=1 yi
2. (a)
Since Database 1 can only be placed at one of the three locations, there are three possible combinations for for x11, x21 and x31:
i. x11 =1,x21 =0andx31 =0 ii. x11 =0,x21 =1andx31 =0 iii. x11 =0,x21 =0andx31 =1
(b) By using an integer programming solver, we find that we should buy 8 × 106 Mcycles from Company 2 and 2 × 106 Mcycles from Company 3. This costs a total of $1833. The files used to solve this problem are hw_grid.mod, hw_grid.dat and hw_grid_batch.
Thismeansx11+x21+x31 =1. (b) The decision variables are
1 if Database j is stored in Location i
xij = 0
We use the notation:
• Di = capacity of Location i
• ti = access time of Location i
• sj = size of Database j
• fj = frequency of accessing Database j • F = total number of accesses per second
The (binary) integer programming problem is:
subject to
otherwise
8
138
min fj tixij
F i=1 j=1
sjxij ≤ Di for1≤i≤3 j=1
3
xij = 1 for1≤j≤8 i=1
xij ∈{0,1}
Note the first set of constraints enforces capacity limit of each location. The second set
of constraints ensures that each database is stored at exactly one location. (c) The location is as showed below.
• Databases 2,3,4 at Location 1. • Databases 1,7,8 at Location 2. • The rest at Location 3.
The files used to solve this problem are hw_db.mod, hw_db.dat and hw_db_batch.
2