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 I

_{k}-th interval and thus finishes at the beginning of interval I_{k}+M. We assume that I_{1}= 1, I_{2}= 3, I_{3}= 6, I_{4}= 9.

For each interval i (i=1, . . . , I) there is a function g

_{i}representing the service level as a function of the number of employees working in that interval. Let y_{k}be the number of employees of shift k for k = 1, . . . ,K. Then the number of employees h_{i}(y) working at interval i is given by

The value of g

_{i}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