Temperature aware online scheduling for throughput maximisation: The effect of the cooling factor

• We proved the competitive ratio of a large class of “reasonable” algorithms for temperature aware online throughput scheduling.
• For the case of one processor we proved matching lower bounds showing that they are optimal.
• We experimentally compared a number of algorithms and showed that their relative performance depend on the cooling factor of the system.

We consider the problem of scheduling jobs in processors with temperature constraints. In our model, unit-length jobs arrive over time, each with a deadline and a heat contribution. The objective is to maximise the total number of completed jobs while keeping the processors within a given temperature threshold. Our main result is the analysis of a large class of ‘reasonable’ algorithms. We analyse the competitive ratio of these algorithms as a function of the cooling factor of the processors. Then we present a lower bound for the problem that shows that these algorithms are optimal in the case of a single processor. We give some other lower bounds for the multiple processors case. Then we perform some computational experiments to investigate the performance of the algorithms in an average case sense, bringing some interesting observations about the performance of the algorithms with respect to the cooling factor.