SMU Faculty Wins ICAPS Best Paper Award

Assistant Professor Akshat Kumar from the SMU School of Information Systems was presented with the “Outstanding Application Paper Award” at the International Conference on Automated Planning and Scheduling (ICAPS) on 23 June 2014 for his paper entitled “Near-Optimal Nonmyopic Contact Center Planning Using Dual Decomposition”.

The ICAPS conference series is the premier forum for exchanging news and research results on theories and applications of intelligent planning and scheduling technology. It aims to promote research in automated planning and scheduling through the analysis and dissemination of foundational theories, technologies, and their application to significant problems.

Professor Kumar’s paper was selected for the award by its programme committee under the ICAPS 2014 Novel Applications Track (NAT). The goal of the NAT within the ICAPS conference is to encourage the submission of papers describing all aspects of the development, deployment and evaluation of planning and scheduling systems for real-world problems. Papers submitted to this track are evaluated base on:

• Significance of the application problem being addressed
• Importance of planning and scheduling technology to solution of the problem
• Novelty of the application and technical approach to the application
• Evaluation of the system
• Clarity of the descriptions of the application problem, techniques used, and results

A summary of the paper is provided as follows:

Near-Optimal Nonmyopic Contact Center Planning Using Dual Decomposition
Akshat Kumar, Assistant Professor of Information Systems
Co-authors: Sudhanshu Singh and Pranav Gupta and Gyana Parija of IBM India Research Lab

Staffing in call centres has received significant attention from the operations research and management communities. Around 60 to 80 per cent of the operating budget of call centres is spent on staffing cost. As cost effective staffing that meets service level requirements is crucial to the profitability and sustainability of technology firms, optimising staffing cost in these settings becomes an important issue.

To facilitate adequate time for the hiring and training of agents, long-term planning and staffing decisions must be made in advance. Practical constraints observed by the researchers through client engagement have led them to develop an approach that effectively handles capacity planning and agent scheduling for contact centre management.

Test results showed that their approach was able to provide near-optimal staffing for 24/7 contact centres over a period of up to eight weeks. This is in contrast to conventional approaches that plan myopically on a week-on-week basis. Based on the Lagrangian relaxation method, the approach is usable in interactive online settings whereby staffing managers who are using the system can expect customisation of system parameters, and generation of high quality plans within a very short time.

Iterative and scalable in nature, the approach is capable of creating a staffing plan for an eight-week period every minute (approximately), while allowing a linear increase in runtime and space complexity according to the number of weeks planned for. Furthermore, it generates a quality bound that shows how far the current solution is from the optimal.

The approach was tested on both challenging synthetic instances, as well as large real world datasets provided by clients. Bounds generated by the approach showed that it could achieve up to 94 per cent of optimal staffing on an average eight-week horizon within ten minutes. In comparison, a generic integer programming solver could only attain up to 80 per cent optimisation within the same duration.

Lastly, a variant of the developed approach, which had been deployed in a live business environment, demonstrated the ability to reduce headcount by five to ten per cent more than custom techniques that were used previously by the business units.

Back to Research@SMU Issue 16 (Jul 2014)