COMP9334 Revision Problems for Week 9A
Chun Tung Chou April 8, 2021
1. A grid computing customer has a job which requires 107 Mcycles to process and must be completed within 4000s. The customer can choose between three companies:
• Company 1: 1000 Mcycles/s at $0.1/s with a set up cost of $500. • Company 2: 2000 Mcycles/s at $0.3/s with a set up cost of $100. • Company 3: 3000 Mcycles/s at $0.8/s with a set up cost of $0.
Assuming the job can be divided arbitrarily among the three companies for processing. Your goal is to find the combination of companies and the number of cycles to be bought from each company so that the job is completed on time and the cost is minimised.
(a) Formulate this as a mixed integer programming (MIP) optimization problem. (b) Solve this problem by using any MIP solver you choose.
2. A company has 8 databases that it can store at three different locations. The size and frequency of access to the databases are showed in Table 1. These databases can be stored in any of the three locations. Each location has a different capacity and access time and they are shown in Table 2. Note the following:
• The size of the databases and the capacity of each location are measured in the same unit.
• The time to access a location is assumed to be constant and is as given in Table 2. Your goal is to minimise the average access time (weighted by frequency of access) by assigning
the databases to the three locations. The allocation must satisfy the following constraints:
• Each database can only be assigned to exactly one location. In other words, you are not allowed to split a database between two locations nor to replicate it.
• The total size of all the databases at one location cannot exceed the capacity of that location.
The decision variables for this optimisation problem are binary. Let xij be the decision variable:
1 if Database j is stored in Location i
xij = 0 Answer the following questions:
otherwise
1
Database Size Frequency of Access (number of times per second) 17 10 224 335 456 532 663 734 853
Table 1: For Question 2
Location Capacity Access time (s) 1 10 0.1 2 15 0.3 3 100 0.8
Table 2: For Question 2
(a) Consider the decision variables for database 1, which are x11, x21 and x31. A constraint for the optimisation problem is that each database can only be assigned to one of the three locations. This constraint means that there are three possible combinations for (x11,x21,x31). What are the three combinations? This also means that the sum x11 + x21 + x31 has a constant value. What is this constant value?
(b) Formulate an integer programming problem to determine where the databases should be stored
(c) Solve this problem by using any solver you choose.
2