TomSym Construction of a Stadium 2
This page is part of the TomSym Manual. See TomSym Manual. |
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: (see tomsym_constructstadium1.m) Which is the earliest possible date of completing the construction?
Question 2: (answered here) 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 10, 2005. Last modified Apr 11, 2009.
tomsym_constructstadium1;
maxreduc = [0;3;1;2;2;1;1;0;2;1;1;0;0;2;2;1;3;0];
costperweek = [0;30;26;12;17;15;8;0;42;21;18;0;0;22;12;6;16;0]*1000;
bonus = 30000;
n = length(maxreduc);
save = tom('save',n+1,1,'int');
start = tom('start',n+1,1,'int');
obj1 = Result.f_k;
% Save is first variable, start second
bnds = {0 <= save <= [maxreduc;inf],...
0 <= start};
count = 1;
con1 = {};
for i=1:n
idx = find(taskprecedence(i,:) ~= 0);
for j=1:length(idx)
con1{count} = {start(idx(j)) + taskduration(i) ...
- save(i) <= start(i)};
count = count + 1;
end
end
con1{count} = {start(end-1) <= start(end)};
idx = find(sum(taskprecedence,2) == 0);
count = 1;
con2 = cell(length(idx),1);
for i=1:length(idx)
con2{count} = {start(i) >= taskduration(idx(i)) - save(i)};
count = count + 1;
end
% Start-save constraint
con3 = {start(end) == obj1 - save(end)};
% Objective
objective = -bonus*save(end)+costperweek'*save(1:end-1);
constraints = {bnds, con1, con2, con3};
options = struct;
options.solver = 'cplex';
options.name = 'Construction of a Stadium 2';
sol = ezsolve(objective,constraints,[],options);
PriLev = 1;
if PriLev > 0
tasks = length(maxreduc) + 1; % number of tasks plus one
temp = [sol.save'; sol.start'];
[finished, task] = sort(temp(2,:));
disp('for a best solution')
for i = 1:tasks,
if temp(1,task(i)) > 0,
disp([' finish task ' num2str(task(i)) ' week ' ...
num2str(temp(2,task(i))) ' (with a reduction of ' ...
num2str(temp(1,task(i))) ')'])
else
disp([' finish task ' num2str(task(i)) ' week ' ...
num2str(temp(2,task(i))) ])
end
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 Time for symbolic processing: 0.11894 seconds Starting numeric solver ===== * * * =================================================================== * * * TOMLAB - TOMLAB Development license 999007. Valid to 2011-12-31 ===================================================================================== 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 Elapsed time: 0.002000 sec. 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 Problem type appears to be: mip Time for symbolic processing: 0.17967 seconds Starting numeric solver ===== * * * =================================================================== * * * TOMLAB - TOMLAB Development license 999007. Valid to 2011-12-31 ===================================================================================== Problem: --- 1: Construction of a Stadium 2 f_k -87000.000000000000000000 f(x_0) 0.000000000000000000 Solver: CPLEX. EXIT=0. INFORM=101. CPLEX Branch-and-Cut MIP solver Optimal integer solution found CPU time: 0.015600 sec. Elapsed time: 0.002000 sec. for a best solution finish task 1 week 2 finish task 2 week 15 (with a reduction of 3) finish task 14 week 22 finish task 3 week 23 (with a reduction of 1) finish task 4 week 23 finish task 7 week 25 finish task 13 week 26 finish task 15 week 27 finish task 10 week 28 finish task 5 week 31 (with a reduction of 2) finish task 6 week 36 (with a reduction of 1) finish task 8 week 38 finish task 11 week 39 finish task 16 week 42 finish task 9 week 45 finish task 12 week 47 finish task 17 week 53 (with a reduction of 3) finish task 18 week 54 finish task 19 week 54 (with a reduction of 10)