JOSEPH (SEFFI) NAOR

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 any single time slot. Any given activity type is associated with a service cost and an operating cost that increases linearly with the number of time slots since the last service of this type. The problem is to find an optimal schedule that minimizes the long-run average cost per time slot. 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. Broadcast Disks recently gained a lot of attention because they were used to model backbone communications in wireless systems, Teletext systems, and Web caching in satellite systems.

The first contribution of this paper is the definition of a general model that combines into one several important previous models. We prove that an optimal cyclic schedule for the general problem exists, and we establish the NP-hardness of the problem. Next, we formulate a nonlinear program that relaxes the optimal schedule and serves as a lower bound on the cost of an optimal schedule. We present an efficient algorithm for finding a near-optimal solution to the nonlinear program. We use this solution to obtain several approximation algorithms.

(1) A 9/8 approximation for a variant of the problem that models the Broadcast Disks application. The algorithm uses some properties of "Fibonacci sequences." Using this sequence, we present a 1.57-approximation algorithm for the general problem.

(2) A simple randomized algorithm and a simple deterministic greedy algorithm for the problem. We 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.

Key words. Scheduling, maintenance service, broadcast disk, cyclic schedule, approximation algorithm.

1. Introduction.

More formally, a schedule for the Generalized Maintenance Scheduling Problem (GMSP) with m machines is S = [S.sub.1],[S.sub.2],... where [S.sub.t] [PRECEDENT TO]/EQUAL TO] {1,...,m} and [absolute value of [S.sub.t]] [less than or equal to] M for all t [greater than or equal to] 1. Here, i [member of] [S.sub.t] means that machine i is scheduled for maintenance at time slot t. The maintenance cost at time slot t is [[SIGMA].sub.i[member of][S.sub.t]] [c.sub.i]. The operating cost [O.sub.t](j) of machine j at time slot t is [a.sub.j](t - t' + b) for integer b [greater than or equal to] 0, where t' [less than or equal to] t is the largest time slot at which j [member of] [S.sub.t'].

We study a problem of scheduling activities of several types over an infinite number of time slots. We describe the model in terms of a generalized version of the maintenance service scheduling problem studied in Anily et al. (1998). In this formulation, there are m machines {1...m} that are to be scheduled for maintenance over an infinite discrete time horizon. In each time slot, at most M machines can be scheduled for maintenance....