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 TaskDescription 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, Email: tomlab@tomopt.com % Copyright (c) 20052009 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:n1 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(end1) <= 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 20100205 ===================================================================================== Problem:  1: Construction of a Stadium 1 f_k 64.000000000000000000 f(x_0) 0.000000000000000000 Solver: CPLEX. EXIT=0. INFORM=101. CPLEX BranchandCut 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