Energy-efficient quantum-inspired stochastic Q-HypE algorithm for batch-of-stochastic-tasks on heterogeneous DVFS-enabled processors

Scheduling on dynamic voltage and frequency scaling enabled processors to determine the Pareto-optimal solutions with optimized makespan and energy consumption demands faster multi-objective scheduling algorithms. In general, the problem of multi-objective optimization, ie, finding the Pareto-optimal solutions to optimize two or more QoS parameters, has been proven to be an NP-complete problem. In this work, we propose a novel energy-efficient quantum-inspired stochastic Q-HypE algorithm to schedule the batch-of-stochastic-tasks (BoT) on DVFS-enabled processors with the aim to optimize the makespan of BoT as well as the energy consumption of processors. The stochastic processing times of tasks are drawn from independent probability distributions. The proposed Q-HypE algorithm evolves from combined characteristics of quantum computing and a hypervolume based multi-objective optimization HypE algorithm. The proposed Q-HypE algorithm simultaneously minimizes the makespan and energy consumption of the Pareto-optimal solutions whereas the dynamics of quantum computing accelerate the process of HypE to further minimize the overheads of hypervolume estimation. Experimental results reveal the effectiveness of the proposed Q-HypE algorithm both in terms of the number and quality of solutions offered.