In this paper, we consider a major 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 quadratic integer programming model for the problem of scheduling jobs to meet the promised lead-time with objective of workload balancing across time. Since in practice, solving such a problem to optimality can be very dicult, two variants of a variable neighborhood search heuristic are proposed. Extensive computational tests
show that our approaches are able to provide high quality solutions efficiently.