Energy efficient scheduling of parallelizable jobs (Q1743718)

A special scheduling environment is analyzed: Jobs may be processed with a scalable speed and the number of parallel machines is also to choose. The objective is a mix of early completion times (weighted by an importance factor) and minimal used energy for the processing. The jobs arrive dynamically and their processing times are not known in advance (non-clairvoyant). An algorithm is presented with a performance which can be chosen and the runtime is then proportional to the inverse squared performance level chosen. The main idea is to classify the jobs in four different categories and to select the job assignment accordingly. The criteria for the jobs are: \(\bullet\) Small or large (beyond or over a specified level), \(\bullet\) Energy consumption compared to processing time or importance. The article gives an overview and insight to the current state of the art of this kind of scheduling and presents a new algorithm to heuristically solve a class of problems with given performance accuracy.