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|
|Source:||Information sciences, 2014, v. 269, p. 128-141 How to cite?|
|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.|
|Appears in Collections:||Journal/Magazine Article|
Show full item record
Checked on Jan 22, 2017
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.