This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Anily, S. Articles by Bramel, J. Search for Related Content

Periodic Scheduling with Service Constraints

Faculty of Management, Tel-Aviv University, Tel-Aviv, Israel 69978
406 Uris Hall, Columbia University, New York, NY 10027
anily{at}post.tau.ac.il
jdb8{at}columbia.edu

We consider the problem of servicing a number of objects in a discrete time environment. In each period, we may select an object that will receive a service in the period. Each time an object is serviced, we incur a servicing cost dependent on the time since the object's last service. Problems of this type appear in many contexts, e.g., multiproduct lot-sizing, machine maintenance, and several problems in telecommunications. We assume that at most one object can be serviced in a given period. For the general problem with m objects, which is known to be -Hard, we describe properties of an optimal policy, and for the specific case of m = 2 objects, we determine an optimal policy.

Subject classifications: Inventory/production: policies, maintenance/replacement; Mathematics: Convexity; Analysis of algorithms.
History: Received October 1997; revision received September 1998; revision received December 1998; accepted January 1999.