This problem I got from someone working in a call center. The call center operation in question operates 24 hours a day, 7 days a week. Every 30 minutes, there is a projected number of agents that need to be present in order to handle calls. Here is an example of such a requirement:

The data shown is truncated. The should be 48 rows corresponding to 48 half-hour intervals in a day. The whole data can be downloaded from here.

Assuming that an agent works 9 hours per day, how do you schedule your staff in such a way that you can meet the required number of agents required per 30 minute interval using a minimum number agents.

**Approach to solving this problem**

Imagine for a moment that you are the manager of this call center and you want to solve this problem manually. Looking at the first row and first column of the data, you’ll see that at 12:00 am to 12:30 am on Mon you need 1 agent to be in the office. Since an agent works 9 hours per day, this agent’s duty will end at 9:00 am. If n is the total number of agents in the office at 9:00, then by the next interval, there will be agents left ( Assuming there is no new agent who comes to work).

Looking down the row under Monday, you will see that a new person is required to be in the office at 6:00 am. You then assign a new person to come to the office at this time.

Further down, another person is required at 8:30 am. However, at 9:00 am, the first person’s shift is up but the requirement is still 3 persons. So you need to assign another person to come to office a 9 am to meet the requirement. Continuing the process in this way, you can ultimately come up with a schedule of your call center agents.

**Complication**

You have to notice that people working at 3:30 pm will intersect the next days shift. They will leave the office at 12:30 am the next day. The same is true for all agents who come to the office between 3:30 to 12:30 pm. To make matters worse, those agents who come to work Sunday starting at 3:30 pm will have to intersect monday’s shift. This means that the one person you initially scheduled above will not be alone, but will have a companion coming from the sunday’s shift.

**Big Question**

The big question therefore is this: Is the schedule you came up with using the manual approach the best schedule in terms of minimizing the number of staff?

We will answer this question in our next article.

### Like this:

Like Loading...

*Related*

baka related lang itong problem to timetabling problem that we already published in parallel algorithms????

why reinvent the wheel, when we can rather fine tune and continually improve on its quality for faster but cheaper products???

Hi Auggie,

A person from a call center actually gave me this problem because this is how they want to schedule their staff. I initially tried to apply genetic algorithms to this but Ernie told me to use linear programming. He also told me how to setup the equations. I find the linear programming more elegant in solving this problem.

actually, that problem, as well as Adora’s timetabling problem, are basically LP in model. Classic LP may not give problems in the computation if small size lang siya, but for large size, baka gagapang yan to have slow convergence. Computational Complexity is the problem, with heuristics, especially if hybridized and parallelized, may give better performances than the classic solvers. As a kind of research, puede mo i-compare, contrasts, say, similarities and differences (especially, on convergence time and quality of solutions) between the classic solvers and your developed hybridized and parallelized heuristics. If you have time, study the other alternatives to like the classic simplex methods for classic LP models, viz. the interior point algorithms, e.g., Karmarkar, which is theoretically proven to perform better than the classic methods!!!

i-try mo kaya i-apply ang ginawa natin sa thesis ni Adora of parallelized heuristics applied to this problem. paper na yon if maganda ang lalabasan!!

Hi Auggie,

I think that with this problem, this is already the maximum size, which is 2x24x7. I’ll try to look for more exciting problems and on a bigger scale.

is it too small a problem for heuristics to be useful kasi classic solvers can do the job? Surely, if large scale, they can be useful kasi yan ang beauty ng heuristics to deal with computational complexity that classic solvers may get bogged down when it comes to convergence!!

There can be more than one minimal solution to the problem!!!