Online scheduling on parallel machines with two GoS levels

Yiwei Jiang ()
Additional contact information
Yiwei Jiang: Zhejiang Sci-Tech University

Journal of Combinatorial Optimization, 2008, vol. 16, issue 1, No 3, 28-38

Abstract: Abstract This paper investigates the online scheduling problem on parallel and identical machines with a new feature that service requests from various customers are entitled to many different grade of service (GoS) levels. Hence each job and machine are labeled with the GoS levels, and each job can be processed by a particular machine only when the GoS level of the job is not less than that of the machine. The goal is to minimize the makespan. In this paper, we consider the problem with two GoS levels. It assumes that the GoS levels of the first k machines and the last m−k machines are 1 and 2, respectively. And every job has a GoS level of 1 alternatively or 2. We first prove the lower bound of the problem under consideration is at least 2. Then we discuss the performance of algorithm AW presented in Azar et al. (J. Algorithms 18:221–237, 1995) for the problem and show it has a tight bound of 4−1/m. Finally, we present an approximation algorithm with competitive ratio $\frac{12+4\sqrt{2}}{7}\approx 2.522$ .

Keywords: Online algorithm; Competitive analysis; Parallel machine scheduling; Grade of Service (search for similar items in EconPapers)
Date: 2008
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (15)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-007-9095-z 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:16:y:2008:i:1:d:10.1007_s10878-007-9095-z

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

DOI: 10.1007/s10878-007-9095-z

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 ().