Near-Optimal Nonmyopic Contact Center Planning using Dual Decomposition

Publication Type

Conference Proceeding Article

Publication Date



We address the problem of minimizing staffing cost in a contact center subject to service level requirements over multiple weeks. We handle both the capacity planning and agent schedule generation aspect of this problem. Our work incorporates two unique business requirements. First, we develop techniques that can provide near-optimal staffing for 247 contact centers over long term, upto eight weeks, rather than planning myopically on a week-on-week basis. Second, our approach is usable in an online interactive setting in which staffing managers using our system expect high quality plans within a short time period. Results on large real world and synthetic instances show that our Lagrangian relaxation based technique can achieve a solution within 94% of optimal on an average, for eight week problems within ten minutes, whereas a generic integer programming solver can only achieve a solution within 80% of optimal. Our approach is also deployed in live business environment and reduces headcount by a decile over techniques used previously by our client business units.


contact center, planning and scheduling


Artificial Intelligence and Robotics | Management Information Systems

Research Areas

Intelligent Systems and Decision Analytics


Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling: Portsmouth, New Hampshire, 21-26 June 2014

First Page


Last Page





AAAI Press

City or Country

Palo Alto, CA

Additional URL