Weighted periodic scheduling of a shared resource

We study a perfectly-periodic scheduling problem of a resource shared among several users. Each user is characterized by a weight describing the number of times it has to use the resource within a cyclic schedule. With the constraint that the resource can be used by at most one user in each time slot, we would like to find a schedule with a minimal time period (number of time slots), in which each user is served once in a fixed number of time slots according to its required total number of times. As many other variants of periodic-scheduling problems, we first prove that the problem is NP-hard. We then describe different cases for which we can calculate the exact value of the optimal time period and present algorithms that obtain optimal schedules. We also study the optimal time period in the case of two users with random weights drawn according to known distributions. We then discuss the general case of arbitrary number of users with general weights and provide approximation algorithms that achieve schedules with guaranteed time periods. Last, we conduct simulations to examine the presented analysis.