A Multi-Objective Quantum-Inspired Genetic Algorithm (Mo-QIGA) for Real-Time Tasks Scheduling in Multiprocessor Environment
Debanjan Konar, Kalpana Sharma, Varun Sarogi, Siddhartha Bhattacharyya · Procedia Computer Science · 2018
This paper aims at providing a multi-objective real-time scheduling algorithm suitable for scheduling of real-time tasks in multiprocessor system with multi-objective criteria. In this proposed Mo-QIGA, scheduling of multi-objective realtime tasks have been targeted for minimizing completion time and total tardiness of each real-time task simultaneously. The exploration of quantum computation in the suggested Mo-QIGA mimics the principles and basic concepts of quantum mechanics. Variable length chromosomes are used in Mo-QIGA and in order to exhibit full Hilbert hyperspace, qubits representation is preferred. In addition, Quantum rotation gate is employed to update the schedules and it obviates classical genetic operators. In order to obtain Pareto-optimal solutions, a random key distribution has been adopted to convert the qubits particles to valid schedule solutions. Moreover, permutation based trimming technique has been introduced for population diversification which leads to good quality schedules. The experiments have been carried out using number of processors varying with real-time tasks priority and processing time. It has been found that the suggested multi-objective quantum inspired genetic algorithm outperforms its classical counterpart in terms of scheduling accuracy and time in multi-objective sense.