关键词: 继承式遗传算法, 马尔科夫链, 扇形分割, 时窗调度

Abstract: An inherited genetic algorithm based on time window scheduling is proposed to solve the dual resource constrained job shop scheduling problem with complex manufacturing environment. This algorithm makes full use of the time window of workers during the process of numerical control machines based on the intersection of time windows to actualize positive scheduling. Then the evolutionary experience of parent chromosomes is inherited with pheromone as carrier and the branch population is generated with improved pseudo-random probability transfer rule and adaptive adjusting parameters based on cloud theory. The King crossover operator is proposed on the basis of imitating animal population organization mode and some resource evolutionary operators are introduced in response to the features of dual resource constrained. At last, an efficient roulette selection operator with sector partition is used to select Pareto-optimal solutions and better chromosomes. After the theoretical analysis of the global convergence via Markov chain, the statistical analysis on the simulation results of random benchmarks shows that this algorithm has strong search ability and good convergence performance.

Key words: Inherited genetic algorithm, Markov chain, Sector partition, Time window scheduling