The selection and scheduling of telecommunication calls with time windows

We consider the bandwidth scheduling problem that consists of selecting and scheduling calls from a list of available calls to be routed on a bandwidth-capacitated telecommunication network in order to maximize profit. Each accepted call should be routed within a permissible scheduling time window for a required duration. To author's knowledge, this study represents the first work on bandwidth scheduling with time windows. We present an integer programming formulation of the problem. We also propose a solution procedure based on the well-established Lagrangean relaxation technique. The results of extensive computational experiments over a wide range of problem structures indicate that the procedure is both efficient and effective.