Please use this identifier to cite or link to this item:
Title: Competitive ratios for preemptive and non-preemptive online scheduling with nondecreasing concave machine cost
Authors: Jiang, Y
Hu, J
Liu, L
Zhu, Y
Cheng, TCE 
Keywords: Competitive ratio
Concave function
Machine cost
Online algorithm
Issue Date: 2014
Publisher: Elsevier
Source: Information sciences, 2014, v. 269, p. 128-141 How to cite?
Journal: Information sciences 
Abstract: We consider an online scheduling problem where jobs arrive one by one and each job must be irrevocably scheduled on the machines. No machine is available initially. When a job arrives, we either purchase a new machine to process it or schedule it for processing on an existing machine. The objective is to minimize the sum of the makespan and the total cost of all the purchased machines. We assume that the total machine cost function is concave in the number of purchased machines. Considering both non-preemptive and preemptive variants of the problem, we prove that the competitive ratio of any non-preemptive or preemptive algorithm is at least 1.5. For the non-preemptive variant, we present an online algorithm and show that its competitive ratio is 1.6403. For the preemptive variant, we propose an online algorithm and show that its competitive ratio is 1.5654. We further prove that both competitive ratios are tight.
ISSN: 0020-0255
EISSN: 1872-6291
DOI: 10.1016/j.ins.2013.08.041
Appears in Collections:Journal/Magazine Article

View full-text via PolyU eLinks SFX Query
Show full item record

Page view(s)

Last Week
Last month
Citations as of Aug 12, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.