Worst-case analysis for on-line service policies

Zhenbo Wang () and Wenxun Xing
Additional contact information
Zhenbo Wang: Tsinghua University
Wenxun Xing: Tsinghua University

Journal of Combinatorial Optimization, 2010, vol. 19, issue 1, No 9, 107-122

Abstract: Abstract This paper considers an on-line scheduling problem occurred in a service system with two classes (ordinary and special) of customers and two types (dedicated and flexible) of servers. The customers line up with a list according to the order of their arrivals. All customers are assumed to be in the system when service starts and no preemption is allowed. The objective is to complete all services in list as early as possible. We study three classes of service policies that are commonly used in practice and analyze their worst-case performance in terms of makespan. Tight worst-case ratios have been derived for these service policies.

Keywords: On-line; Parallel machine scheduling; Service policy evaluation; Worst-case analysis (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-008-9170-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:19:y:2010:i:1:d:10.1007_s10878-008-9170-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-008-9170-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().