带运输的混合流水车间调度问题的改进遗传算法

Improved Genetic Algorithm for Scheduling Problem of Hybrid Flow Shop with Transportation

为实现分布式制造环境中上下游工序和机器间的协同生产,研究了带有运输的混合流水车间调度问题。以包含加工时间、运输时间和加工等待时间的完工时间最小为目标,建立了带有运输约束的混合流水车间调度模型,基于Q-learning设计了改进的遗传算法(QGA)求解该模型。在该算法中,首先基于工件序号设计编码和遗传算子等遗传操作;然后根据种群适应度函数构建种群的状态集合,以交叉概率和变异概率的取值作为动作,以最佳个体适应度和种群平均适应度作为奖励;最后采用Q-learning对交叉和变异参数进行智能调整,提高算法的收敛速度与全局搜索能力。仿真实验结果表明,与改进的遗传算法(GA-TS)相比,本文QGA的最大完工时间平均减少了2.0%,收敛速度提升了18.1%。

In order to realize the cooperative production between upstream and downstream processes and machines in distributed manufacturing environment,the scheduling problem of hybrid flow shop with transportation is studied.A scheduling model of hybrid flow shop with transportation constraints is established to minimize the completion time including processing time,transportation time and processing waiting time.An improved genetic algorithm(QGA)based on Q-learning is designed to solve the model.Firstly,in this algorithm,genetic operations such as coding and genetic operators are designed based on the job sequence number.Secondly,the state set of the population is constructed according to the fitness function of the population,the values of the crossover probability and mutation probability are taken as the action,and the best individual fitness and the average population fitness are used as rewards.Finally,Q-learning is used to intelligently adjust the crossover and mutation parameters,the convergence speed and global search ability of genetic algorithm can be improved.The simulation results show that compared with genetic algorithm,the makespan of QGA in this paper is reduced by 2.0%on average,and convergence speed is increased by 18.1%.