Scheduling Two Machines with Dissimilar Costs

Madhurupa Moitra


We consider two devices, which has states ON and OFF. In the ON state, the devices use their full power whereas in the OFF state the devices consume no energy but a constant cost is associated with switching back to ON. Such two devices are configured with different run and power-up costs on which a sequence of jobs must be processed. The object is to minimize the cost. Such systems are widely used to conserve energy, for example, to speed scale CPUs, to control data centers, or to manage renewable energy.

The problems are studied in the framework of online competitive analysis and we analyze a number of online algorithm and give lower bounds. The objective of the algorithm is to optimize the budget and analyzing how effectively it works.