Applying Quantum Principles to GAs for Multiple Objective Scheduling

Multi-objective scheduling problem has been proposed in literature (T'kindt et. al., 1996). However, conventional meta heuristics-based methods, such as GA algorithms, were studied with single objective function to derive combinatorial optimization.

Recent advances of GAs and multi-objective researches (Han et. al., 2005) applied principles of Quantum Computers to stochastic optimization problems. In addition, Q bit representation and permutation-based GA was advocated by researchers (Li & Wang, 2007). For multi-objective scheduling Q bit GA needs to obtain good approximation for both co-operative and competitive task environment. Moreover, Q bit-based permutation, crossover operators, selection, encoding, generation processes and fitness values are required to explore and exploit the large or high dimensional state spaces. It is a relaxed minimization problem with the Q-bit.

Algorithm evaluation needs to combine a vector of all local objective function values for each job. However, local optimum per job and global optimum for entire task environment indicates further layer of constraint based satisfaction with enumeration of iterative policy and state transitions. Other than the optimization of enumeration, parallelization may need to considered at both system and application level. Furthermore, pipelined processing and data parallelization are critical to reduce both time and space complexities.

Han et. al. (2005). A quantum-inspired genetic algorithm for flow shop scheduling. Springer-Velag.
T'kindt et. al.(1996). Multicriteria Scheduling: Theory, Models and Algorithms. Springer-Velag, 2002.