Assigning Personnel to Machines

Contents

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 '])
    [worker,machine] = find(x1);
    for i = 1:length(worker)
        disp(['   worker '           num2str(worker(i)) ...
            ' operates machine ' num2str(machine(i))])
    end
    x2  = sol2.assign;
    disp(['Best serial work (' num2str(-f_k2) ') when '])
    [worker,machine] = find(x2);
    for i = 1:length(worker)
        disp(['   worker '           num2str(worker(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
===== * * * =================================================================== * * *
TOMLAB - Tomlab Optimization Inc. Development license  999001. Valid to 2010-02-05
=====================================================================================
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 
Problem type appears to be: mip
===== * * * =================================================================== * * *
TOMLAB - Tomlab Optimization Inc. Development license  999001. Valid to 2010-02-05
=====================================================================================
Problem: ---  1: Assigning Personnel to Machines  f_k     -26.000000000000000000
                                         sum(|constr|)      0.000000000000004653
                                f(x_k) + sum(|constr|)    -25.999999999999996000
                                                f(x_0)      0.000000000000000000

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

FuncEv   68 
CPU time: 0.015625 sec. Elapsed time: 0.015000 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 3 operates machine 1
   worker 4 operates machine 1
   worker 5 operates machine 1
   worker 4 operates machine 2
   worker 5 operates machine 2
   worker 6 operates machine 2
   worker 2 operates machine 3
   worker 1 operates machine 4
   worker 6 operates machine 4
   worker 1 operates machine 5
   worker 4 operates machine 5
   worker 3 operates machine 6
   worker 4 operates machine 6