On-line Service Scheduling

Zhenbo Wang(zwangmath.tsinghua.edu.cn)
Wenxun Xing(wxingmath.tsinghua.edu.cn)
Bo Chen(b.chenwarwick.ac.uk)

Abstract: This paper is concerned with a scheduling problem that occurs in service systems, where customers are classified as `ordinary' and `special'. Ordinary customers can be served on any service facility, while special customers can be served only on the flexible service facilities. Customers arrive dynamically over time and their needs become known upon arrival. We assume any service, once started, will be carried out to its completion. In this paper, we study the worst-case performance of service policies used in practice. In particular, we evaluate three classes of service policies: policies with priority, policies without priority, and their combinations. We obtain tight worst-case performance bounds for all service policies considered.

Keywords: competitive ratio, on-line, parallel machine scheduling, service policy

Category 1: Applications -- OR and Management Sciences (Scheduling )

Category 2: Combinatorial Optimization (Approximation Algorithms )

Citation: To appear in Journal of Scheduling

Download: [PDF]

Entry Submitted: 04/18/2008
Entry Accepted: 04/18/2008
Entry Last Modified: 04/18/2008

Modify/Update this entry