Optimization Online


On-line Service Scheduling

Zhenbo Wang (zwang***at***math.tsinghua.edu.cn)
Wenxun Xing (wxing***at***math.tsinghua.edu.cn)
Bo Chen (b.chen***at***warwick.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: Journal of Scheduling; DOI: 10.1007/s10951-008-0075-7


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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society