A request scheduling algorithm to support flexible resource reservations in advance

The request scheduling is the problem of. finding a schedule for a given set of book-ahead (BA) requests connection, with the goal of maximizing the profit obtained from the accepted BA requests. The problem is considered in a scenario with advance reservations where users can specify a flexible duration for when they want their connections to be established. In this paper, we focus the problem on a subnet. The major concerned performance metrics are the resource utilization as well as the rejection ratio of the BA requests. We introduce an oversubscribed policy to support the request scheduling in a batching fashion. The request scheduling is a combinatorial problem. We formulated the problem as the 0/1 multiple-choice multi-dimensional knapsack problem (MMKP). The 0/1 MMKP is NP-hard. Hence, algorithms for finding the exact solution of 0/1 MMKP are not suitable for the proposed request-scheduling problem, especially for a large-scale network. In this paper, we present a heuristic based upon the simulated annealing algorithms for the 0/1 MMKP. Finally, simulation results show that the proposed approach can notably improve the resource utilization.