New upper and lower bounds for online scheduling with machine cost

This paper considers the online scheduling problem with machine cost. We are given a sequence of independent jobs with positive sizes. Jobs come one by one and it is required to schedule jobs irrevocably to a machine as soon as they are given, without any knowledge about jobs that follow later on. No machines are initially provided. When a job is revealed, the algorithm has the option to purchase new machines. The objective is to minimize the sum of the rnakespan and cost of purchased machines. We prove that root 2 is a lower bound of the problem, which significantly improves the previous one of 4/3. We also present a new algorithm with competitive ratio (2 + root 7)/3 approximate to 1.5486, which improves the current best algorithm with competitive ratio (2 root 6+3)/5 approximate to 1.5798. Moreover, we prove that applying only the lower bounds on the optimum objective value introduced before, no algorithm can be proven to have a competitive ratio less than 3/2. (C) 2010 Elsevier B.V. All rights reserved.