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.
Original language | English |
---|---|
Pages (from-to) | 128-141 |
Number of pages | 14 |
Journal | Information Sciences |
Volume | 269 |
DOIs | |
Publication status | Published - 10 Jun 2014 |
Keywords
- Competitive ratio
- Concave function
- Machine cost
- Online algorithm
- Scheduling
ASJC Scopus subject areas
- Control and Systems Engineering
- Theoretical Computer Science
- Software
- Computer Science Applications
- Information Systems and Management
- Artificial Intelligence