Online algorithms for scheduling with machine activation cost

Online algorithms for scheduling with machine activation cost

0.00 Avg rating0 Votes
Article ID: iaor20073637
Country: Singapore
Volume: 24
Issue: 2
Start Page Number: 263
End Page Number: 277
Publication Date: Apr 2007
Journal: Asia-Pacific Journal of Operational Research
Authors: , ,
Abstract:

In this paper, we consider a variant of the classical parallel machine scheduling problem. For this problem, we are given m potential identical machines to non-preemptively process a sequence of independent jobs. Machines need to be activated before starting to process, and each machine activated incurs a fixed machine activation cost. No machines are initially activated, and when a job is revealed the algorithm has the option to activate new machines. The objective is to minimize the sum of the makespan and activation cost of machines. We first present two optimal online algorithms with competitive ratios of 3/2 and 5/3 for m = 2,3 cases, respectively. Then we present an online algorithm with a competitive ratio of at most 2 for general m ≥ 4, while the lower bound is 1.88.

Reviews

Required fields are marked *. Your email address will not be published.