Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/15660
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
Scheduling
Issue Date: 2014
Publisher: Elsevier Inc.
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.
URI: http://hdl.handle.net/10397/15660
ISSN: 0020-0255
DOI: 10.1016/j.ins.2013.08.041
Appears in Collections:Journal/Magazine Article

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

Page view(s)

28
Last Week
1
Last month
Checked on Feb 19, 2017

Google ScholarTM

Check

Altmetric



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