We consider the shift scheduling problem in call centers [1]. Suppose a call center is operational during I=13 intervals. At the beginning of K=4 specified intervals, employees can start working, and each employee works for M=5 consecutive intervals. Shift k starts at the Ik-th interval and thus finishes at the beginning of interval Ik +M. We assume that I1 = 1, I2 = 3, I3 = 6, I4 = 9.
![]()
For each interval i (i=1, . . . , I) there is a function gi representing the service level as a function of the number of employees working in that interval. Let yk be the number of employees of shift k for k = 1, . . . ,K. Then the number of employees hi(y) working at interval i is given by
![]()
The value of gi at this point is the attained service level in interval i. The overall service level is defined by
![]()
Now consider the following problem, which maximizes the service level for a given number of employees:
![]()
We assume that call arrivals are Poisson. The service criterion is the fraction of customers that has to wait longer than c seconds, e.g., c=11 seconds, before getting an operator, which should be below 5% in general. (We assume that no customers leave the system before getting an operator.)
Assuming that a statistical equilibrium is attained in each time interval, we use the formula for the stationary waiting time in an M|M|n queue as the service level. Let
![]()
then the expected service level of an arbitrary customer under schedule y is equal to
![]()
where
and
are the waiting time in an M|M|n queue with arrival rate
and service rate
. Thus we take
![]()
This function is indeed monotone increasing and concave for each i. Therefore,
is multimodular. We can minimize
by ODICON because multimodular functions and L
-convex functions are equivalent objects that can be related through a simple coordinate transformation.
This web application minimizes
using ODICON .
[1] G. Koole and E. van der Sluis (2003): Optimal shift scheduling with a global service level constraint, IIE Transactions, Vol. 35, pp. 1049-1055.
Satoko Moriguchi, Nobuyuki Tsuchimura