Construction of a Stadium 1

Contents

Problem description

A town council wishes to construct a small stadium in order to improve the services provided to the people living in the district. After the invitation to tender, a local construction company is awarded the contract and wishes to complete the task within the shortest possible time. All the major tasks are listed in the following table. The durations are expressed in weeks. Some tasks can only start after the completion of certain other tasks. The last two columns of the table refer to question 2 which we shall see later.

Data for stadium construction

+----+---------------------------+----+-------+-----+--------------+
|    |                           |    |       | Max.| Add. cost per|
|Task|Description                |Dur.| Pred. | red.| wk (in 1000$)|
+----+---------------------------+----+-------+-----+--------------+
|  1 |Inst. the constr. site     | 2  | none  |  0  |      –       |
|  2 |Terracing                  |16  |  1    |  3  |     30       |
|  3 |Constructing foundations   | 9  |  2    |  1  |     26       |
|  4 |Access roads networks      | 8  |  2    |  2  |     12       |
|  5 |Erecting the basement      |10  |  3    |  2  |     17       |
|  6 |Main floor                 | 6  | 4,5   |  1  |     15       |
|  7 |Dividing up changing rms   | 2  |  4    |  1  |      8       |
|  8 |Electrifying the terraces  | 2  |  6    |  0  |      –       |
|  9 |Constructing the roof      | 9  | 4,6   |  2  |     42       |
| 10 |Lighting of the stadium    | 5  |  4    |  1  |     21       |
| 11 |Installing the terraces    | 3  |  6    |  1  |     18       |
| 12 |Sealing the roof           | 2  |  9    |  0  |      –       |
| 13 |Finishing the changing rms | 1  |  7    |  0  |      –       |
| 14 |Constructing ticket office | 7  |  2    |  2  |     22       |
| 15 |Secondary access roads     | 4  | 4,14  |  2  |     12       |
| 16 |Means of signalling        | 3  |8,11,14|  1  |      6       |
| 17 |Lawn and sport accessories | 9  |  12   |  3  |     16       |
| 18 |Handing over the building  | 1  |  17   |  0  |      –       |
+----+---------------------------+----+-------+-----+--------------+

Precedence graph of construction tasks

                               1
                               |
                               2
                            /  |  \
                           /   |   \
                          /    |    \
                         /           \
                        /      3      \
                       /               \
                      /        |        \
                     /         |         \
                    /          |          \
                 14            5     +----- 4
                   \                /    /
               /    |          |   /    /  /| \
              /  +--+----------+---    /  / |  \
             /  /   |          |   +--+  /  |   \
              -+    |             /     /   |
          15        |          6       /    |    7
                    |                 +     |
           |        |      /   |   \  |     |    |
           |        |     /    |    \ |     |    |
           |        |
           |        \  11      8      9    10   13
            \        \
             \        \   \ /         |     |    |
              \        \   V          |     |    |
               \        \                   |    |
                \         16         12     |    |
                 \                          |    |
                  \        |          |     |    |
                   \       |                |   /
                    \      |         17     |  /
                     \     |                | /
                      \    |          |    / /
                       \   |              / /
                        \  |         18  / /
                         \ |            / /
                          \ \       /  / /
                           \ \     /  / /
                            \ \   /  / /
                             \      / /
                                F

Question 1: (answered here) Which is the earliest possible date of completing the construction?

Question 2: (see tomsym_constructstadium2.m ) The town council would like the project to terminate earlier than the time announced by the builder (answer to question 1). To obtain this, the council is prepared to pay a bonus of $30K for every week the work finishes early. The builder needs to employ additional workers and rent more equipment to cut down on the total time. In the preceding table he has summarized the maximum number of weeks he can save per task (column "Max. reduct.") and the associated additional cost per week. When will the project be % completed if the builder wishes to maximize his profit?

Variables

taskduration       The time it takes to complete each task.
taskprecedence     Describes the order of the tasks.

References

Applications of optimization... Gueret, Prins, Seveaux

% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com
% Copyright (c) 2005-2009 by Tomlab Optimization Inc., $Release: 7.2.0$
% Written Oct 7, 2005.   Last modified Apr 11, 2009.

Problem setup

taskduration   = [2;16;9;8;10;6;2;2;9;5;3;2;1;7;4;3;9;1];
taskprecedence = [0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0;...
    1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0;...
    0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0;...
    0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0;...
    0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0;...
    0  0  0  1  1  0  0  0  0  0  0  0  0  0  0  0  0  0;...
    0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0;...
    0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0;...
    0  0  0  1  0  1  0  0  0  0  0  0  0  0  0  0  0  0;...
    0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0;...
    0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0;...
    0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0;...
    0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0;...
    0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0;...
    0  0  0  1  0  0  0  0  0  0  0  0  0  1  0  0  0  0;...
    0  0  0  0  0  0  0  1  0  0  1  0  0  1  0  0  0  0;...
    0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0;...
    0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0];

n = length(taskduration)+1;
task = tom('task',n,1,'int');

% All variables integer
bnds = {0 <= task};

count = 1;
con1 = {};
for i=1:n-1
    idx = find(taskprecedence(i,:) ~= 0);
    for j=1:length(idx)
        con1{count} = {task(idx(j)) + taskduration(i) <= task(i)};
        count = count + 1;
    end
end
con1{count} = {task(end-1) <= task(end)};

idx = find(sum(taskprecedence,2) == 0);
numidx = length(idx);
count = 1;
con2 = cell(length(idx),1);
for i=1:length(idx)
    con2{count} = {task(i) >= taskduration(idx(i))};
    count = count + 1;
end

% Objective
objective = task(end);

constraints = {bnds, con1, con2};
options = struct;
options.solver = 'cplex';
options.name   = 'Construction of a Stadium 1';
[sol, Result] = ezsolve(objective,constraints,[],options);

PriLev = 1;
if PriLev > 0
    tasks = length(taskduration) + 1; % number of tasks plus one
    [finished, task] = sort(sol.task);

    disp('for a best solution')
    for i = 1:tasks,
        disp(['   finish task ' num2str(task(i)) ' week ' num2str(sol.task(task(i))) ])
    end
end

% MODIFICATION LOG
%
% 051010 med   Created
% 060111 per   Added documentation
% 060126 per   Moved disp to end
% 090411 med   Converted to tomSym
Problem type appears to be: mip
Starting numeric solver
===== * * * =================================================================== * * *
TOMLAB - Tomlab Optimization Inc. Development license  999001. Valid to 2010-02-05
=====================================================================================
Problem: ---  1: Construction of a Stadium 1    f_k      64.000000000000000000
                                              f(x_0)      0.000000000000000000

Solver: CPLEX.  EXIT=0.  INFORM=101.
CPLEX Branch-and-Cut MIP solver
Optimal integer solution found


for a best solution
   finish task 1 week 2
   finish task 2 week 18
   finish task 14 week 25
   finish task 4 week 26
   finish task 3 week 27
   finish task 7 week 28
   finish task 13 week 29
   finish task 15 week 30
   finish task 10 week 31
   finish task 5 week 37
   finish task 6 week 43
   finish task 8 week 45
   finish task 11 week 46
   finish task 16 week 49
   finish task 9 week 52
   finish task 12 week 54
   finish task 17 week 63
   finish task 18 week 64
   finish task 19 week 64