Using Linear Programming to Solve the Call Center Problem

Agents cost money. Not only will you pay for their salary but also other benefits in you compensation package. So the less agents you have to do a job, the less overhead, the more profit for you.

In the last article, we solve the call center scheduling using a manual approach. The question now is this: Does our solution give us the least possible cost to operate the call center? We cannot be sure. However, there is a technique which we can use in order to calculate the least possible cost of our schedule subject to the constraints of the required agents per time slot. This technique is called Integer Linear Programming.

Formulation of the Problem

Let x_i, 0 \le i \le 335, be the number of call center agents who comes to work at time slot i. Using this notation, we can calculate the number of call center agents current present in the office at time slot 1:

S_1=x_0 +  0 + \ldots+  0 + x_{320} + x_{321} + \ldots + x_{335}

How did we arrive with this equation? If an agent starts at time slot 320, then he/she will still be in the office at time slot 1. This is however his/her last time slot for the shift. All agents that start after 320 until 336 will also be present at time slot 1. And so is the agent that starts at time slot.

Similarly, the number of agents in time slot 2 is given by

S_2= x_0 + x_1 + 0 + \ldots + 0  + x_{321} + x_{322}  + \ldots + x_{335}

A similar pattern holds for i from 2 to 335.

Let \vec{req} be the vector of required number of agents per time slot. Then we can specify for each time slot i that the number of agents be greater than or equal to req[i].

The linear programming problem can now be specified by:

Minimize \sum_{i=0}^{335} x_i

subject to the following contraints:

constraints.jpg

We can create programmatically the matrix of these constraints using this algorithm. The code is written in R, which is an open source statistical software.

x=seq(1:336)
y=(x+17) %% 336

bigmatrix=c();
for( i in 1:336){
z=(y - i) %% 336;
tmp=rep(0,336)
for( j in 1:336){
if(z[j] < 18 ){
tmp[j] = 1;
}
}
bigmatrix=c(bigmatrix,tmp);
}

Notice that we start our index from 1 rather than 0. This is because R is a 1-based programming language.

Using the lpSolve package of R, we can compute the minimum of the objective function using the lp function of the library.

bigmatrix=matrix(bigmatrix,nrow=336,byrow=T)
f.obj=rep(1,336);
f.con=bigmatrix;
f.dir=rep(">=",336)
f.rhs=mydata2

print("computing lp");
mylp=lp ("min", f.obj, f.con,
f.dir, f.rhs, int.vec=1:336)

After executing the code above, we get the following result:

lp_result.jpg

The value of the objective function is given by:

> mylp$objval
[1] 47

If we compare this to the manual method, the value of the objective function is just the sum of the components of z:

> sum(z)
[1] 48

This means that using the Linear Programming technique, we were able to come up with a solution with the least cost.

Advertisements

Published by

Bobby Corpus

Loves anything related to Mathematics, Physics, Computing and Economics.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s