Scheduling with Machine Cost

initially and remains unchanged for the duration of the
problem. We consider two basic online scheduling problems
($P|online|C_{max}$ and $P|online,r_j|C_{max}$) with the
modification that initially the algorithm possesses no
machines, but that at any point additional machines may
be purchased.

We have several reasons for studying this idea. Most obviously,
real machines have cost. If we do not have the necessary
machines then they must be obtained. Even if we already
possess machines we may still incur a fixed start up or
conversion cost proportional to the number of machines used.
Also, we still have an ``opportunity cost''. By this we mean
that if we use the machines for a given problem we lose the
chance to use them for something else. Further, in many cases
it is desirable to buy or lease additional machines. A second
reason we might allow the number of machines to be determined
by the algorithm is that the performance of an algorithm on a
given input can be highly dependent on the number of machines.
This seems particularly true when considering worst case
measures. A third reason is that by considering such a variant
we may find other interesting problems and/or gain insight
into the original.

Upper and lower bounds on the competitive ratio are shown
for both of the modified problems.