Abstract: We study the problem of scheduling activities of several types,
under the constraint that at most a fixed number of activities can be
scheduled in a single period. An activity type is associated with a service
cost, and an operating cost that increases with the number of periods
since the last service of this type. The problem is to find an optimal
schedule that MINIMIZES the long-run average cost per period.
Applications of such a model are the scheduling of maintenance service to
machines, multi-item replenishment of stock, and minimizing the mean
response time in broadcast disks. In the broadcast disks, m pages of a
database are repeatedly broadcast, at most k per time slot. These pages
are accessed by clients: page i has probability p_i of being accessed by
a client. A client who wishes to access page i listens to the broadcast
until the end of the time slot in which i was broadcasted. The goal is to
find an infinite schedule of which pages to broadcast at each time slot.
An efficient schedule is one which minimizes the expected waiting time.
We describe a simple randomized algorithm and a simple deterministic greedy
algorithm for this problem, and prove that both achieve approximation
factor of 2. To the best of our knowledge this is the first worst case analysis
of a widely used greedy heuristic for this problem.
(Joint work with Amotz Bar-Noy, Seffi Naor and Baruch Schieber.)