基于遗传模拟退火算法的自动化制造单元周期调度

Cyclic scheduling for robotic cell via genetic simulated annealing algorithm

鉴于有时间窗约束的单机器人单度自动化制造单元周期调度问题的可行解极少且难以找到最优解,提出一种带有不可行解修复机制的遗传模拟退火算法,以提高解的搜索效率。采用基于跨周期决策的先后次序约束修复、联动修复等机制,对不可行解进行修复,提升其逼近可行解的概率;结合遗传算法的多点初始和模拟退火的靶向搜索能力,强力筛查可能存在的可行解;根据模拟退火的降温速度,利用Metropolis准则以逐渐变小的概率接受交叉和变异后产生的劣解,促进种群跳出局部最优。实验证明所提出的算法在保证解的质量的前提下,计算时间更短,求解效率更高,可较好地满足自动化制造单元的周期调度要求。

In order to improve the search efficiency of feasible and optimal solutions,a genetic simulated annealing algorithm with repair mechanisms for infeasible solution is proposed to solve the problem of cyclic scheduling for single-robot and single-degree robotic cell with the time window constraint.Specifically,the first repair mechanism is to make the robot’s moving sequence comply with the order limitation because some processes should not cross over two production cycles,and the second repair mechanism is to make the processing time comply with the time window constraint as much as possible.Global exploration via genetic algorithm and intensified exploration via simulated annealing are balanced to targetedly search for more feasible solutions.Metropolis criterion is employed to accept the inferior solutions generated by the crossover and mutation operators with a gradually decreasing probability directly related to the cooling rate,so as to promote the population to jump out of the local optimum.Experimental results show that the proposed algorithm can solve the cyclic scheduling problem in shorter computational time and with higher efficiency under the premise of ensuring the solution quality.