Scheduling Nurses

Contents

Problem description

Mr. Schedule has been asked to organize the schedule of nurses for the Cardiology service at St. Joseph’s hospital. A working day in this service is subdivided into twelve periods of two hours. The personnel requirement changes from period to period: for instance, only a few nurses are required during the night, but the total number must be relatively high during the morning to provide specific care to the patients. The following table lists the personnel requirement for every time period.

Question 1: Determine the minimum number of nurses required to cover all the requirements, knowing that a nurse works eight hours per day and that she is entitled to a break of two hours after she has worked for four hours.

Question 2: The service only has 80 nurses, which is not sufficient with the given requirements. Mr. Schedule therefore proposes that part of the personnel works two additional hours per day. These two additional hours follow immediately after the last four hours, without any break. Determine the schedule of the nurses in this service that minimizes the number of nurses working overtime.

Personnel requirement per time period

+------+-------------+------------------------+
|Number|Time interval|Minimum number of nurses|
+------+-------------+------------------------+
|   0  | 00am - 02am |          15            |
|   1  | 02am - 04am |          15            |
|   2  | 04am - 06am |          15            |
|   3  | 06am - 08am |          35            |
|   4  | 08am - 10am |          40            |
|   5  | 10am - 12pm |          40            |
|   6  | 12pm - 02pm |          40            |
|   7  | 02pm - 04pm |          30            |
|   8  | 04pm - 06pm |          31            |
|   9  | 06pm - 08pm |          35            |
|  10  | 08pm - 10pm |          30            |
|  11  | 10pm - 12am |          20            |
+------+-------------+------------------------+

Variables

demand                     nurses needed per shift
hoursperday                hours of work per day
breakinterval              work this long before break
breaklength                length of break
intervallength             length of an interval
maxdemand                  max number of nurses in Q 2

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

Problem setup

demand         = [15 15 15 35 40 40 40 30 31 35 30 20]';
hoursperday    = 8;
breakinterval  = 4;
breaklength    = 2;
intervallength = 2;
maxdemand      = 80;

n = length(demand);

start = tom('start',n,1,'int');
% All variables are integer
bnds = {0 <= start};

% Requirement constraints
idxvec = [1:12, 1:4];
con = cell(n,1);
for i=1:n
    idx = idxvec(i:i+4);
    idx(3) = [];
    con{i} = {sum(start(idx)) >= demand(i)};
end

% Objective
objective = sum(start);

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

overtime = tom('overtime',n,1,'int');
bnds = {bnds, overtime >= 0};

% Requirement constraints
con = cell(n,1);
idxvec2 = [1:12, 1:5];
for i=1:n
    idx = idxvec(i:i+4);
    idx(3) = [];
    idxo = idxvec2(i+5);
    con{i} = {sum(start(idx)) + overtime(idxo) >= demand(i)};
end

% Overtime less than regular (extends these)
con2 = {overtime <= start};
con3 = {sum(start) <= maxdemand};
constraints = {bnds, con, con2, con3};
objective = sum(overtime);
sol2 = ezsolve(objective,constraints,[],options);
f_k2 = subs(objective,sol2);

PriLev = 1;
if PriLev > 0
    x1        = sol1.start;                   % nurses working
    intervals = length(x1);                   % number of intervals
    work      = [x1 circshift(x1,-1) circshift(x1,-3) circshift(x1,-4)];
    work_1    = sum(work')';                  % total nurses
    n         = sol2.start;                   % regular shifts
    o         = sol2.overtime;                % overtime
    work1     = [n circshift(n,-1) ...        % regular -> 4 intervals
        circshift(n,-3) circshift(n,-4)];
    work2     = [o circshift(o,-1) ...        % overtime -> 5 intervals
        circshift(o,-3) circshift(o,-4) circshift(o,-5)];
    work_2    = sum(work1')' + sum(work2')';  % total work

    disp(['Without overtime we need ' num2str(f_k1) ' nurses.'])
    disp(['   This is the schedule:'])
    for i = 1:intervals,
        disp(['   ' num2str((i-1)*2) '.00: ' num2str(x1(i)) ...
            ' start and ' num2str(work_1(i)) ' are working.' ...
            ' ( demand is ' num2str(demand(i)) ')'  ])
    end

    disp(['With overtime we have ' num2str(sum(n)) ...
        ' nurses, and ' num2str(sum(o)) ...
        ' of them will work overtime.'])
    disp(['   This is the schedule:'])
    for i = 1:intervals,
        disp(['   ' num2str((i-1)*2) '.00: ' num2str(n(i)) ...
            ' start a regular shift, '     num2str(o(i)) ...
            ' start an overtime shift and ' num2str(work_2(i)) ...
            ' are working.' ...
            ' ( demand is ' num2str(demand(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: Scheduling Nurses              f_k     100.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: Scheduling Nurses              f_k      40.000000000000000000
                                              f(x_0)      0.000000000000000000

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

FuncEv   19 
Without overtime we need 100 nurses.
   This is the schedule:
   0.00: 7 start and 24 are working. ( demand is 15)
   2.00: 17 start and 34 are working. ( demand is 15)
   4.00: 0 start and 29 are working. ( demand is 15)
   6.00: 0 start and 35 are working. ( demand is 35)
   8.00: 0 start and 40 are working. ( demand is 40)
   10.00: 17 start and 40 are working. ( demand is 40)
   12.00: 12 start and 46 are working. ( demand is 40)
   14.00: 23 start and 36 are working. ( demand is 30)
   16.00: 0 start and 31 are working. ( demand is 31)
   18.00: 11 start and 35 are working. ( demand is 35)
   20.00: 0 start and 30 are working. ( demand is 30)
   22.00: 13 start and 20 are working. ( demand is 20)
With overtime we have 80 nurses, and 40 of them will work overtime.
   This is the schedule:
   0.00: 7 start a regular shift, 0 start an overtime shift and 17 are working. ( demand is 15)
   2.00: 5 start a regular shift, 0 start an overtime shift and 15 are working. ( demand is 15)
   4.00: 10 start a regular shift, 0 start an overtime shift and 17 are working. ( demand is 15)
   6.00: 3 start a regular shift, 2 start an overtime shift and 37 are working. ( demand is 35)
   8.00: 0 start a regular shift, 0 start an overtime shift and 55 are working. ( demand is 40)
   10.00: 0 start a regular shift, 0 start an overtime shift and 65 are working. ( demand is 40)
   12.00: 2 start a regular shift, 0 start an overtime shift and 63 are working. ( demand is 40)
   14.00: 15 start a regular shift, 0 start an overtime shift and 71 are working. ( demand is 30)
   16.00: 15 start a regular shift, 15 start an overtime shift and 57 are working. ( demand is 31)
   18.00: 10 start a regular shift, 10 start an overtime shift and 58 are working. ( demand is 35)
   20.00: 13 start a regular shift, 13 start an overtime shift and 43 are working. ( demand is 30)
   22.00: 0 start a regular shift, 0 start an overtime shift and 22 are working. ( demand is 20)