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 thePareto-optimal solutions with optimized makespan and energy consumption demands fastermulti-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 beenproven to be an NP-complete problem. In this work, we propose a novel energy-efficientquantum-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 theenergy consumption of processors. The stochastic processing times of tasks are drawn fromindependent probability distributions. The proposed Q-HypE algorithm evolves from combinedcharacteristics of quantum computing and a hypervolume based multi-objective optimizationHypE algorithm. The proposed Q-HypE algorithm simultaneously minimizes the makespanand energy consumption of the Pareto-optimal solutions whereas the dynamics of quantumcomputing accelerate the process of HypE to further minimize the overheads of hypervolumeestimation. Experimental results reveal the effectiveness of the proposed Q-HypE algorithmboth in terms of the number and quality of solutions offered.