Variable neighborhood search for the workload balancing problem in service enterprises

In this paper, we consider a telecommunication service company facing seasonal demand and time-varying capacity. A uniform lead-time, which is the maximum time span a customer has to wait before receiving the required service, is quoted to all customers. We present a quadratic integer programming model for the problem of scheduling jobs to meet the promised lead-time with the objective of balancing the workload across time. Since in practice solving such a problem to optimality can be very difficult, two variants of a variable neighborhood search approach are proposed. Extensive computational tests show that our heuristics are able to provide high quality solutions efficiently.