Minimizing service and operation costs of periodic scheduling

• 成果类型: Article; Proceedings Paper
• 署名作者: Bar-Noy, A; Bhatia, R; Naor, JS; Schieber, B
• 署名单位: City University of New York (CUNY) System; Brooklyn College (CUNY); AT&T; Alcatel-Lucent; Lucent Technologies; Technion Israel Institute of Technology; International Business Machines (IBM); IBM USA
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.27.3.518.314
• 发表日期: 2002
• 页码: 518-544
• 关键词: one machine; lot sizes; feasibility; systems

摘要

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 An 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 typed 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 propertied 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 knock ledge this is the first worst-case analysis of a widely used greedy heuristic for this problem.