An Adaptive Hyper-Heuristics genetic algorithm for stochastic job shop scheduling problem

Abstract

Stochastic job - shop scheduling problem (SJSSP) is a kind of stochastic programming problem which transformed from job - shop scheduling problem (JSSP). The current methods to solve SJSSP ignored characteristics of SJSSP， which lead to large solution times and inefficient solution. Aiming at the problem， Adaptive Hyper-Heuristics genetic algorithms (AHHGA) is proposed combing with characteristics of SJSSP to solve SJSSP with the objective to minimize the expected value of makespan. Four heuristics rules for SJSSP were designed. Portfolios of processing times of job can be seen as a scenario. The outer loop of the proposed algorithms is to determine heuristics rules on each scenario in scenario set. The inner loop is that a genetic algorithm is employed on the high level and Heuristics rules on each scenario in scenario set are used for constructing scheduling timetables are work on the low level within the hyper-heuristic framework. Thus, the proposed algorithm ensures to find a better solution in a limit search scope with respect to characteristics of SJSSP. FT benchmark-based problems where the processing times are subjected to independent normal distributions are solved effectively by AHHGA. The experiment results achieved by AHHGA are compared with quantum-inspired genetic algorithm (QGA) and standard genetic algorithm (GA) and a novel competitive co-evolutionary quantum genetic algorithm (CCQGA),which shows that AHHGA has better feasibility and effectiveness.