TomSym Assigning Personnel to Machines

From TomWiki
Jump to navigationJump to search

Notice.png

This page is part of the TomSym Manual. See TomSym Manual.

Problem description

An operator needs to be assigned to each of the six machines in a workshop. Six workers have been pre-selected. Everyone has undergone a test of her productivity on every machine. The table below lists the productivities in pieces per hour. The machines run in parallel, that is, the total productivity of the workshop is the sum of the productivities of the people assigned to the machines.

Productivity in pieces per hour

+-------+-----------------+
|       |    Machines     |
+-------+--+--+--+--+--+--+
|Workers| 1| 2| 3| 4| 5| 6|
+-------+--+--+--+--+--+--+
|   1   |13|24|31|19|40|29|
|   2   |18|25|30|15|43|22|
|   3   |20|20|27|25|34|33|
|   4   |23|26|28|18|37|30|
|   5   |28|33|34|17|38|20|
|   6   |19|36|25|27|45|24|
+-------+--+--+--+--+--+--+

The objective is to determine an assignment of workers to machines that maximizes the total productivity. We may start by calculating a (non-optimal) heuristic solution using the following fairly natural method: choose the assignment p -> m with the highest productivity, cross out the line p and the column m (since the person has been placed and the machine has an operator), and restart this process until we have assigned all persons. The problem should then be solved to optimality using Mathematical Programming. And finally, solve the same problem to optimality, but for machines working in series.

Variables

prodmat                    The productivity matrix

Reference

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.1.0$
% Written Oct 7, 2005.   Last modified Mar 8, 2009.

Problem setup

prodmat = [ 13 24 31 19 40 29;...
    18 25 30 15 43 22;...
    20 20 27 25 34 33;...
    23 26 28 18 37 30;...
    28 33 34 17 38 20;...
    19 36 25 27 45 24];

p = size(prodmat,1);  %workers
m = size(prodmat,2);  %machines

assign = tom('assign',p,m,'int');

% All variables are binary
bnds = {0 <= assign <= 1};

% Worker/machine constraints
con = {sum(assign,1) == 1, sum(assign,2) == 1};

% Objective
objective = -sum(sum(prodmat.*assign));

constraints = {bnds, con};
options = struct;
options.solver = 'cplex';
options.name   = 'Assigning Personnel to Machines';
sol1 = ezsolve(objective,constraints,[],options);
f_k1 = subs(objective,sol1);

% Series
pmin = tom('pmin',1,1);
bnds = {bnds, pmin >= 0};

% Productivity bounds 1
con2 = {sum(prodmat.*assign,2) >= pmin};
constraints = {constraints, con2};
objective = -pmin;
sol2 = ezsolve(objective,constraints,[],options);
f_k2 = subs(objective,sol2);

PriLev = 1;
if PriLev > 0
    m   = size(prodmat,1); % number of machines
    w   = m;               % number of workers
    x1  = sol1.assign;
    disp(['Best parallel work (' num2str(-f_k1) ') when '])
    [workers,machine] = find(x1);
    for i = 1:length(workers)
        disp(['   worker '           num2str(workers(i)) ...
            ' operates machine ' num2str(machine(i))])
    end
    x2  = sol2.assign;
    disp(['Best serial work (' num2str(-f_k2) ') when '])
    [workers,machine] = find(x2);
    for i = 1:length(workers)
        disp(['   worker '           num2str(workers(i)) ...
            ' operates machine ' num2str(machine(i))])
    end
end

% MODIFICATION LOG
%
% 051202 med   Created.
% 060117 per   Added documentation.
% 060126 per   Moved disp to end
% 090308 med   Converted to tomSym
Problem type appears to be: mip
Time for symbolic processing: 0.015904 seconds
Starting numeric solver
===== * * * =================================================================== * * *
TOMLAB - TOMLAB Development license  999007. Valid to 2011-12-31
=====================================================================================
Problem: ---  1: Assigning Personnel to Machines  f_k    -193.000000000000000000
                                                f(x_0)      0.000000000000000000

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

FuncEv   12 
Elapsed time: 0.003000 sec. 
Problem type appears to be: mip
Time for symbolic processing: 0.023379 seconds
Starting numeric solver
===== * * * =================================================================== * * *
TOMLAB - TOMLAB Development license  999007. Valid to 2011-12-31
=====================================================================================
Problem: ---  1: Assigning Personnel to Machines  f_k     -26.000000000000000000
                                                f(x_0)      0.000000000000000000

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

FuncEv   39 
Elapsed time: 0.006000 sec. 
Best parallel work (193) when 
   worker 5 operates machine 1
   worker 6 operates machine 2
   worker 1 operates machine 3
   worker 3 operates machine 4
   worker 2 operates machine 5
   worker 4 operates machine 6
Best serial work (26) when 
   worker 5 operates machine 1
   worker 4 operates machine 2
   worker 2 operates machine 3
   worker 6 operates machine 4
   worker 1 operates machine 5
   worker 3 operates machine 6