Efficient algorithms for periodic scheduling

In a perfectly periodic schedule, time is divided into time slots, and each client gets a slot precisely every predefined number of time slots. The input to a schedule design algorithm is a frequency request for each client, and its task is to construct a perfectly periodic schedule that matches the requests as "closely" as possible. The quality of the schedule is measured by the ratios between the requested frequency and the allocated frequency for each client (either by the weighted average or by the maximum of these ratios over all clients). Perfectly Periodic schedules enjoy maximal fairness, and are very useful in many contexts of asymmetric communication, e.g., push systems and Bluetooth networks. However, finding an optimal perfectly periodic schedule is NP-hard. Tree scheduling is a methodology for developing perfectly periodic schedules based on hierarchical round-robin, where the hierarchy is represented by trees. In this paper, we study algorithms for constructing scheduling trees. First, we give optimal (exponential time) algorithms for both the average and the maximum measures. Second, we present a few efficient heuristic algorithms for generating schedule trees, based on the structure and the analysis of the optimal algorithms. Simulation results indicate that some of these heuristics produce excellent schedules in practice, sometimes even beating the best known non-perfectly periodic scheduling algorithms. (C) 2004 Elsevier B.V. All rights reserved.