# TOMLAB  
# REGISTER (TOMLAB)
# LOGIN  
# myTOMLAB
TOMLAB LOGO

« Previous « Start » Next »

22  Scheduling

22.1  Construction of a Stadium 1

% function Result = constructionofastadium1Ex(PriLev)
%
% Creates a TOMLAB MIP problem for production of a stadium
%
% CONSTRUCTION OF A STADIUM 1
%
% 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                     |Duration|Predecessors|reduct.|week (in 1000$)|
% +----+--------------------------------+--------+------------+-------+---------------+
% |  1 |Installing the construction site|   2    |    none    |   0   |      –        |
% |  2 |Terracing                       |  16    |    1       |   3   |     30        |
% |  3 |Constructing the foundations    |   9    |    2       |   1   |     26        |
% |  4 |Access roads and other networks |   8    |    2       |   2   |     12        |
% |  5 |Erecting the basement           |  10    |    3       |   2   |     17        |
% |  6 |Main floor                      |   6    |   4,5      |   1   |     15        |
% |  7 |Dividing up the changing rooms  |   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 rooms    |   1    |    7       |   0   |      –        |
% | 14 |Constructing the 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 constructionofastadium2Ex.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.
%
% RESULTS
%
% x_k has the week each task is finished
% (including task_19 = finished), try this:
% Result = constructionofastadium1Ex(2);
% Result.x_k'
%
% REFERENCES
%
% Applications of optimization... Gueret, Prins, Seveaux
% http://web.univ-ubs.fr/lester/~sevaux/pl/index.php
%
% INPUT PARAMETERS
% PriLev       Print Level
%
% OUTPUT PARAMETERS
% Result       Result structure.

% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com
% Copyright (c) 2005-2006 by Tomlab Optimization Inc., $Release: 5.1.0$
% Written Oct 10, 2005.   Last modified Jan 2, 2006.

function Result = constructionofastadium1Ex(PriLev)

if nargin < 1
   PriLev = 1;
end

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];

Prob = constructionofastadium1(taskduration, taskprecedence);
Result = tomRun('cplex', Prob, PriLev);

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

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

% MODIFICATION LOG
%
% 051010 med   Created.
% 060111 per   Added documentation.
% 060126 per   Moved disp to end

22.2  Construction of a Stadium 2

% function Result = constructionofastadium2Ex(PriLev)
%
% Creates a TOMLAB MILP problem for production of a stadium
%
% CONSTRUCTION OF A STADIUM 2
%
% 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                     |Duration|Predecessors|reduct.|week (in 1000$)|
% +----+--------------------------------+--------+------------+-------+---------------+
% |  1 |Installing the construction site|   2    |    none    |   0   |      –        |
% |  2 |Terracing                       |  16    |    1       |   3   |     30        |
% |  3 |Constructing the foundations    |   9    |    2       |   1   |     26        |
% |  4 |Access roads and other networks |   8    |    2       |   2   |     12        |
% |  5 |Erecting the basement           |  10    |    3       |   2   |     17        |
% |  6 |Main floor                      |   6    |   4,5      |   1   |     15        |
% |  7 |Dividing up the changing rooms  |   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 rooms    |   1    |    7       |   0   |      –        |
% | 14 |Constructing the 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 constructionofastadium1Ex.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.
%
% RESULTS
%
% For an interpretation of the results, use PriLev > 1, for example:
% Result = constructionofastadium2Ex(2);
%
% REFERENCES
%
% Applications of optimization... Gueret, Prins, Seveaux
% http://web.univ-ubs.fr/lester/~sevaux/pl/index.php
%
% INPUT PARAMETERS
% PriLev       Print Level
%
% OUTPUT PARAMETERS
% Result       Result structure.

% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com
% Copyright (c) 2005-2006 by Tomlab Optimization Inc., $Release: 5.1.0$
% Written Oct 10, 2005.   Last modified Jan 2, 2006.

function Result = constructionofastadium2Ex(PriLev)

if nargin < 1
   PriLev = 1;
end

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];

Prob = constructionofastadium1(taskduration, taskprecedence);
Prob.PriLevOpt = PriLev-1;
Result = tomRun('cplex', Prob, PriLev-1);

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;
idx            = sum(taskprecedence,2);

Prob = constructionofastadium2(maxreduc, costperweek, bonus, idx, taskduration, Result);

Result = tomRun('cplex', Prob, PriLev);

if PriLev > 1,
   tasks = length(maxreduc) + 1; % number of tasks plus one
   temp  = reshape(Result.x_k,tasks,2)';
   [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

22.3  Flow-shop scheduling

% function Result = flowshopschedulingEx(PriLev)
%
% Creates a TOMLAB MIP problem for flow shop scheduling
%
% FLOW-SHOP SCHEDULING
%
% A workshop that produces metal pipes on demand for the automobile
% industry has three machines for bending the pipes, soldering the
% fastenings, and assembling the links. The workshop has to produce
% six pieces, for which the durations of the processing steps (in
% minutes) are given in the following table. Every workpiece first
% goes to bending, then to soldering, and finally to assembly of the
% links. Once started, any operations must be carried out without
% interruption, but the workpieces may wait between the machines.
%
% Processing durations in minutes
%
% +---------+-+-+-+-+-+-+
% |Workpiece|1|2|3|4|5|6|
% +---------+-+-+-+-+-+-+
% |Bending  |3|6|3|5|5|7|
% |Soldering|5|4|2|4|4|5|
% |Assembly |5|2|4|6|3|6|
% +---------+-+-+-+-+-+-+
%
% Every machine only processes one piece at a time. A workpiece may
% not overtake any other by passing onto the following machine. This
% means that if at the beginning a sequence of the workpieces is
% established, they will be processed on every machine in exactly
% this order. Which is the sequence of workpieces that minimizes the
% total time for completing all pieces?
%
% VARIABLES
%
% nummachines                The number of machines
% proctimes                  Time to process a workpiece in a machine
%
% RESULTS
%
% The vector x_k can be interpreted by running the following:
% Result = flowshopschedulingEx(2);
%
% REFERENCES
%
% Applications of optimization... Gueret, Prins, Seveaux
% http://web.univ-ubs.fr/lester/~sevaux/pl/index.php
%
% INPUT PARAMETERS
% PriLev       Print Level
%
% OUTPUT PARAMETERS
% Result       Result structure.

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

function Result = flowshopschedulingEx(PriLev)

if nargin < 1
   PriLev = 1;
end

nummachines = 3;
proctimes   = [3 6 3 5 5 7;...
      5 4 2 4 4 5;...
      5 2 4 6 3 6];

Prob = flowshopscheduling(nummachines, proctimes);

Result = tomRun('cplex', Prob, PriLev);

if PriLev > 1,
   p      = size(proctimes,2);                % number of pieces
   m      = nummachines;                      % number of machines
   order  = reshape(Result.x_k(1:p*p),p,p);   % the order of the pieces
   order(find(order<0.5)) = 0;                % delete bad zeros
   wait1  = Result.x_k(p*p+1:p*p+p);          % wait before machine 1
   wait2  = Result.x_k(end-2*p+1:end-p);      % wait before machine 2
   wait3  = Result.x_k(end-p+1:end);          % wait before machine 3
   proctimes   = [3 6 3 5 5 7;...             % the processing times
         5 4 2 4 4 5;...
         5 2 4 6 3 6];
   sequence = [] ;                            % the sequence of pieces
   for i = 1:p,
      sequence = [sequence find(order(:,i))]; % insert piece by piece
   end
   disp(['A best sequence is: ' num2str(sequence)])

   mt1 = [];   % empty machine-times for machine 1
   mt2 = [];   % empty machine-times for machine 2
   mt3 = [];   % empty machine-times for machine 3
   t11 = 0;    % timepoint for entering machine 1
   t12 = 0;    % timepoint for exiting  machine 1
   t21 = 0;    % timepoint for entering machine 2
   t22 = 0;    % timepoint for exiting  machine 2
   t31 = 0;    % timepoint for entering machine 3
   t32 = 0;    % timepoint for exiting  machine 3
   first2 = 1; % the first piece in machine 2
   first3 = 1; % the first piece in machine 3

   for i = 1:length(sequence),
      id  = sequence(i);

      % times in and out of machine 1
      t11  = t12 + wait1(id);
      t12  = t11 + proctimes(1,id);

      % times in and out of machine 2
      if first2 == 1,
         t21 = t12 + wait2(id);
         first2 = 0 ;
      else,
         t21 = t22 + wait2(id);
      end
      t22  = t21 + proctimes(2,id);

      % times in and out of machine 3
      if first3 == 1,
         t31 = t22 + wait3(id);
         first3 = 0 ;
      else,
         t31 = t32 + wait3(id);
      end
      t32  = t31 + proctimes(3,id);

      % times in and out of machines
      mt1 = [mt1; t11  t12];
      mt2 = [mt2; t21  t22];
      mt3 = [mt3; t31  t32];
   end

   mt = [mt1 mt2 mt3];

   disp('FLOW FOR THE PIECES')
   for j = 1:p,
      disp(['piece ' num2str(sequence(j)) ' has this flow' ])
      for k = 1:m,
         disp(['   machine ' num2str(k) ': ' num2str(mt(j,(k-1)*2+1)) '-' num2str(mt(j,(k-1)*2+2)) ])
      end
   end
   disp('FLOW FOR THE MACHINES')
   for k = 1:m,
      disp(['machine ' num2str(k) ' has this flow' ])
      for l = 1:p,
         disp(['   piece ' num2str(sequence(l)) ': ' ...
               num2str(mt(l,((k-1)*2+1))) '-' num2str(mt(l,((k-1)*2+2)))])
      end
   end

end

% MODIFICATION LOG
%
% 051010 med   Created.
% 060111 per   Added documentation.
% 060124 per   Interpretation of results upgraded.
% 060126 per   Moved disp to end

22.4  Job Shop Scheduling

% function Result = jobshopschedulingEx(PriLev)
%
% Creates a TOMLAB MIP problem for job shop scheduling
%
% JOB SHOP SCHEDULING
%
% A company has received an order for three types of wallpapers: one
% (paper 1) has a blue background with yellow patterns, another
% (paper 2) a green background and blue and yellow patterns, and the
% last (paper 3) has a yellow background with blue and green
% patterns. Every paper type is produced as a continuous roll of
% paper that passes through several machines, each printing a
% different color. The order in which the papers are run through the
% machines depends on the design of the paper: for paper 1 first the
% blue background and then the yellow pattern is printed. After the
% green background for paper 2, first the blue and then the yellow
% patterns are printed. The printing of paper 3 starts with the
% yellow background, followed by the blue and then the green
% patterns.
%
%       p2             p1              p3
%       |              |               |
%       V              V               V
%      +-----+        +----+ --p1-> +------+
%      |GREEN| --p2-> |BLUE| --p2-> |YELLOW|
%      +-----+ <-p3-- +----+ <-p3-- +------+
%
%         |                           |   |
%         V                           V   V
%         p3                          p1  p2
%
% Production flows through printing machines
%
% The processing times differ depending on the surface that needs to
% be printed. The times (in minutes) for applying every color of the
% three paper types are given in the following table.
%
% Times required for applying every color
%
% +-------+------+-------+-------+-------+
% |Machine|Color |Paper 1|Paper 2|Paper 3|
% +-------+------+-------+-------+-------+
% |   1   |Blue  |  45   |  20   |  12   |
% |   2   |Green |   -   |  10   |  17   |
% |   3   |Yellow|  10   |  34   |  28   |
% +-------+------+-------+-------+-------+
%
% Knowing that every machine can only process one wallpaper at a time
% and that a paper cannot be processed by several machines
% simultaneously, how should the paper printing be scheduled on the
% machines in order to finish the order as early as possible?
%
% VARIABLES
%
% the colors are ordered as follows:
%    color1 = blue   (paper 1's first color)
%    color2 = green  (paper 2's first color)
%    color3 = yellow (paper 3's first color)
%
%
% proctimes                  Times for the papers in the machines
% flow                       The order of colors on the paperS
% final                      The last machine for each paper
% bigM                       The total processingtimes.
%
% RESULTS
%
% run this for explanation of x_k
% Result = jobshopschedulingEx(2);
%
% REFERENCES
%
% Applications of optimization... Gueret, Prins, Seveaux
% http://web.univ-ubs.fr/lester/~sevaux/pl/index.php
%
% INPUT PARAMETERS
% PriLev       Print Level
%
% OUTPUT PARAMETERS
% Result       Result structure.

% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com
% Copyright (c) 2005-2006 by Tomlab Optimization Inc., $Release: 5.1.0$
% Written Jan 2, 2006.   Last modified Jan 2, 2006.

function Result = jobshopschedulingEx(PriLev)

if nargin < 1
   PriLev = 1;
end

proctimes   = [45 20 12;...
      0  10 17;...
      10 34 28];

flow        = [1 3 0;...
      2 1 3;...
      3 1 2];

final       = [3;3;2];

bigM        = sum(sum(proctimes));

Prob = jobshopscheduling(proctimes, flow, final, bigM);

Result = tomRun('cplex', Prob, PriLev);

if PriLev > 1,
   c      = 3; % number of colors
   p      = 3; % number of papers
   temp   = reshape(Result.x_k,c,c+c+2);
   disp(['all papers are finished after ' num2str(max(temp(:,c+1))) ' minutes'])
   disp(' ')
   for j = 1:p,
      disp(['paper ' num2str(j) ':'])
      colortimes = temp(j,1:c);
      [time,col] = sort(colortimes);
      for i = 1:c,
         this_col  = col(i);
         this_time = time(i);
         if this_time == 0
            disp(['   starts using color ' num2str(this_col) ' after ' ...
                  num2str(this_time) ' minutes (or not at all)'])
         else
            disp(['   starts using color ' num2str(this_col) ' after ' ...
                  num2str(this_time) ' minutes'])
         end
      end
   end
end

% MODIFICATION LOG
%
% 060102 med   Created.
% 060111 per   Added documentation.
% 060126 per   Moved disp to end

22.5  Sequencing jobs on a bottleneck machine

% function Result = sequencingjobsonabottleneckmEx(PriLev)
%
% Creates a TOMLAB MIP problem for sequencing jobs on a bottleneck machine
%
% SEQUENCING JOBS ON A BOTTLENECK MACHINE
%
% In workshops it frequently happens that a single machine determines
% the throughput of the entire production (for example, a machine of
% which only one is available, the slowest machine in a production
% line, etc.). This machine is called the critical machine or the
% bottleneck. In such a case it is important to schedule the tasks
% that need to be performed by this machine in the best possible way.
% The aim of the problem is to provide a simple model for scheduling
% operations on a single machine and that may be used with different
% objective functions. We shall see here how to minimize the total
% processing time, the average processing time, and the total
% tardiness. A set of tasks (or jobs) is to be processed on a single
% machine. The execution of tasks is non-preemptive (that is, an
% operation may not be interrupted before its completion). For every
% task i its release date and duration are given. For the last
% optimization criterion (total tardiness), a due date (latest
% completion time) is also required to measure the tardiness, that
% is, the amount of time by which the completion of jobs exceeds
% their respective due dates. The following table lists the data for
% our problem.
%
% What is the optimal value for each of the objectives:
%    1 - minimizing the total duration of the schedule (= makespan)?
%    2 - minimizing the mean processing time?
%    3 - minimizing the total tardiness?
%
% Task time windows and durations
%
% +------------+--+--+--+--+--+--+--+
% |Job         | 1| 2| 3| 4| 5| 6| 7|
% +------------+--+--+--+--+--+--+--+
% |Release date| 2| 5| 4| 0| 0| 8| 9|
% |Duration    | 5| 6| 8| 4| 2| 4| 2|
% |Due date    |10|21|15|10| 5|15|22|
% +------------+--+--+--+--+--+--+--+
%
% VARIABLES
%
% releasedate                Release dates of jobs (row 1 in table)
% duration                   Time to perform a job (row 2 in table)
% duedate                    Deadline of each job  (row 3 in table)
%
% RESULTS
%
% For an interpretation of the results try the following:
% [Result1, Result2, Result3] = sequencingjobsonabottleneckmEx(2)
%
% REFERENCES
%
% Applications of optimization... Gueret, Prins, Seveaux
% http://web.univ-ubs.fr/lester/~sevaux/pl/index.php
%
% INPUT PARAMETERS
% PriLev       Print Level
%
% OUTPUT PARAMETERS
% Result       Result structure.

% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com
% Copyright (c) 2005-2006 by Tomlab Optimization Inc., $Release: 5.1.0$
% Written Jan 2, 2006.   Last modified Jan 2, 2006.

function [Result1,Result2,Result3] = sequencingjobsonabottleneckmEx(PriLev)

if nargin < 1
   PriLev = 1;
end

releasedate = [2 5 4 0 0 8 9]';
duration    = [5 6 8 4 2 4 2]';
duedate     = [10 21 15 10 5 15 22]';

Prob1 = sequencingjobsonabottleneckm(releasedate, duration, duedate, 1);
Result1 = tomRun('cplex', Prob1, PriLev);

Prob2 = sequencingjobsonabottleneckm(releasedate, duration, duedate, 2);
Result2 = tomRun('cplex', Prob2, PriLev);

Prob3 = sequencingjobsonabottleneckm(releasedate, duration, duedate, 3);
Result3 = tomRun('cplex', Prob3, PriLev);

if PriLev > 1,
   j         = length(releasedate); % number of jobs
   sequence2 = reshape(Result2.x_k,j,j+2);    % results from 1 and 2
   sequence3 = reshape(Result3.x_k,j,j+3);    % results from 3
   sequence2(find(sequence2(1:7*7)<0.1)) = 0; % remove bad zeros
   sequence3(find(sequence3(1:7*7)<0.1)) = 0; % remove bad zeros
   s2 = [];                                   % blank sequence
   s3 = [];                                   % blank sequence
   for t = 1:j,
      s2 = [s2 find(sequence2(t,1:j))];
      s3 = [s3 find(sequence3(t,1:j))];
   end
   disp(['An order to minimize duration (=' ...
         num2str(sequence2(j,j+2)) ') and to minimize mean '...
         'processing time (=' num2str(sequence2(j,j+2)/j) ')'])
   disp(num2str(s2))
   disp(' ')
   tard = sum(sequence3(:,size(sequence3,2)));
   disp(['An order to minimize tardiness (=' num2str(tard) ')' ])
   disp(num2str(s3))
   disp(' ')
end

% MODIFICATION LOG
%
% 060102 med   Created.
% 060111 per   Added documentation.
% 060126 per   Moved disp to end

22.6  Paint production

% function Result = paintproductionEx(PriLev)
%
% Creates a TOMLAB MIP problem for paint production
%
%
% PAINT PRODUCTION
%
% As a part of its weekly production a paint company produces five
% batches of paints, always the same, for some big clients who have a
% stable demand. Every paint batch is produced in a single production
% process, all in the same blender that needs to be cleaned between
% two batches. The durations of blending paint batches 1 to 5 are
% respectively 40, 35, 45, 32, and 50 minutes. The cleaning times
% depend on the colors and the paint types. For example, a long
% cleaning period is required if an oil-based paint is produced after
% a water-based paint, or to produce white paint after a dark color.
% The times are given in minutes in the following table CLEAN where
% CLEANij denotes the cleaning time between batch i and batch j.
%
% Matrix of cleaning times
%
% +-+--+--+--+--+--+
% | | 1| 2| 3| 4| 5|
% +-+--+--+--+--+--+
% |1| 0|11| 7|13|11|
% |2| 5| 0|13|15|15|
% |3|13|15| 0|23|11|
% |4| 9|13| 5| 0| 3|
% |5| 3| 7| 7| 7| 0|
% +-+--+--+--+--+--+
%
% Since the company also has other activities, it wishes to deal
% with this weekly production in the shortest possible time (blending
% and cleaning). Which is the corresponding order of paint batches?
% The order will be applied every week, so the cleaning time between
% the last batch of one week and the first of the following week
% needs to be counted for the total duration of cleaning.
%
% VARIABLES
%
% cleantimes                 Times to clean from batch i to j
% prodtimes                  Production times per batch
%
% RESULTS
%
% For an interpretation of the results, use PriLev > 1, for example:
% Result  = paintproductionEx(2);
%
%
% REFERENCES
%
% Applications of optimization... Gueret, Prins, Seveaux
% http://web.univ-ubs.fr/lester/~sevaux/pl/index.php
%
% INPUT PARAMETERS
% PriLev       Print Level
%
% OUTPUT PARAMETERS
% Result       Result structure.

% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com
% Copyright (c) 2005-2006 by Tomlab Optimization Inc., $Release: 5.1.0$
% Written Oct 17, 2005.   Last modified Jan 2, 2006.

function Result = paintproductionEx(PriLev)

if nargin < 1
   PriLev = 1;
end

cleantimes = [ 0 11  7 13 11;...
      5  0 13 15 15;...
      13 15  0 23 11;...
      9 13  5  0  3;...
      3  7  7  7  0];

prodtimes  = [40;35;45;32;50];

Prob = paintproduction(prodtimes, cleantimes);

Result = tomRun('cplex', Prob, PriLev);

if PriLev > 1,
   batches = size(cleantimes,1);                    % number of batches
   temp1   = reshape(Result.x_k,batches,batches+1); % reshape x_K
   link    = [];                                    % connections

   for i = 1:batches,
      for j = 1:batches,
         if temp1(i,j) == 1
            link = [[i j ]; link ];                 % finding connections

         end
      end
   end

   first = link(1:1);                               % start batch
   next =  link(1,2);                               % next batch
   order = [first];                                 % ordered batches

   for k = 1:batches,
      order = [order next];                         % adding next
      next =  link(find(link(:,1)==next),2);        % finding new next
   end
   disp(['one best order: ' num2str(order)])        % display solution
end

% MODIFICATION LOG
%
% 051010 med   Created.
% 060111 per   Added documentation.
% 060126 per   Moved disp to end

22.7  Assembly line balancing

% function Result = assemblylinebalancingEx(PriLev)
%
% Creates a TOMLAB MIP problem for assembly line balancing
%
% Assembly line balancing
%
% An electronics factory produces an amplifier on an assembly line
% with four workstations. An amplifier is assembled in twelve
% operations between which there are certain precedence constraints.
% The following table indicates the duration of every task
% (in minutes) and the list of its immediate predecessors (the
% abbreviation PCB used in this table stands for ‘printed circuit
% board’).
%
% The production manager would like to distribute the tasks among the
% four workstations, subject to the precedence constraints, in order
% to balance the line to obtain the shortest possible cycle time,
% that is, the total time required for assembling an amplifier. Every
% task needs to be assigned to a single workstation that has to
% process it without interruption. Every workstation deals with a
% single operation at a time. We talk about cycle time because the
% operations on every workstation will be repeated for every
% amplifier. When an amplifier is finished, the amplifiers at
% stations 1 to 3 advance by one station, and the assembly of a new
% amplifier is started at the first workstation.
%
% List of tasks and predecessors
% +----+---------------------------------------+--------+------------+
% |Task|Description                            |Duration|Predecessors|
% +----+---------------------------------------+--------+------------+
% |  1 |Preparing the box                      |    3   |    –       |
% |  2 |PCB with power module                  |    6   |    1       |
% |  3 |PCB with pre-amplifier                 |    7   |    1       |
% |  4 |Filter of the amplifier                |    6   |    2       |
% |  5 |Push-pull circuit                      |    4   |    2       |
% |  6 |Connecting the PCBs                    |    8   |   2,3      |
% |  7 |Integrated circuit of the pre-amplifier|    9   |    3       |
% |  8 |Adjusting the connections              |   11   |    6       |
% |  9 |Heat sink of the push-pull             |    2   |  4,5,8     |
% | 10 |Protective grid                        |   13   |  8,11      |
% | 11 |Electrostatic protection               |    4   |    7       |
% | 12 |Putting on the cover                   |    3   |  9,10      |
% +----+---------------------------------------+--------+------------+
%
% A precedence graph of the same table with times within ( ).
%
%                   1  (3)
%
%                 /   \
%                /     \
%               /       \
%
%              3 (7)      2 (6)
%
%            /   \      / | \
%           /     \    /  |  \
%          /       \  /   |   \
%
%         7 (9)      6    5    4 (6)
%                     (8)  (4)
%         |          |    |    |
%         |          |    |    |
%         |          |    |    |
%                         |    |
%        11 (4)      8    |    |
%                     (11)|    /
%           \      /  \   |   /
%            \    /    \  |  /
%             \  /      \ | /
%
%              10 (13)    9 (2)
%
%                \       /
%                 \     /
%                  \   /
%
%                    12 (3)
%
% VARIABLES
%
% duration                   Time or each task.
% stations                   Stations available.
% dependsvec1 and 2          For a task t: If dependsvec1[i] = t and
%                            dependsvec2[i] = d then k depends on d.
%
% RESULTS
%
% To get the results interpreted:
% Result = assemblylinebalancingEx(2);
%
% REFERENCES
%
% Applications of optimization... Gueret, Prins, Seveaux
% http://web.univ-ubs.fr/lester/~sevaux/pl/index.php
%
% INPUT PARAMETERS
% PriLev       Print Level
%
% OUTPUT PARAMETERS
% Result       Result structure.

% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com
% Copyright (c) 2005-2006 by Tomlab Optimization Inc., $Release: 5.1.0$
% Written Oct 17, 2005.   Last modified Jan 2, 2005.

function Result = assemblylinebalancingEx(PriLev)

if nargin < 1
   PriLev = 1;
end

duration    = [3;6;7;6;4;8;9;11;2;13;4;3];
stations    = 4;
dependsvec1 = [2;3;4;5;6;6;7;8;9;9;9;10;10;11;12;12];
dependsvec2 = [1;1;2;2;2;3;3;6;4;5;8; 8;11; 7; 9;10];

Prob = assemblylinebalancing(stations, duration, dependsvec1, dependsvec2);

Result = tomRun('cplex', Prob, PriLev);

if PriLev > 1,
   t      = length(duration);               % number of tasks
   s      = stations;                       % number of workstations
   temp   = reshape(Result.x_k(1:t*s),t,s); % reshaping distribution
   time   = Result.x_k(t*s+1);              % total time

   for i = 1:s,
      disp(['tasks managed by station ' ...  % filter + disp
            num2str(i) ': ' ...
            num2str(find(temp(:,i))')])
   end

   disp(['total time ' num2str(time)])      % disp the time
end

% MODIFICATION LOG
%
% 051010 med   Created
% 060111 per   Added documentation.
% 060126 per   Moved disp to end

« Previous « Start » Next »