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

王 娟，唐秋华，毛永年,3

(1.湖南工程学院机械工程学院，湖南 湘潭，411104；2.武汉科技大学冶金装备及其控制教育部重点实验室，湖北 武汉，430081；3.遵义师范学院工学院，贵州 遵义，563006)

随着企业自动化和智能化程度的提高，物料搬运工作越来越多地由机器人完成。机器人搬运作业顺序不仅影响其自身的工作效率，而且影响整个自动化制造单元的生产效率及生产计划的执行效果。在制定搬运机器人周期作业顺序时，若只有一台搬运机器人，只有一种工件进入或者离开系统，且工件的加工时间仅能在给定的上、下限范围内变动，则称之为具有作业时间窗约束的单机器人单度自动化制造单元调度问题。

针对这类问题，Phillips等[1]首次建立了混合整数线性规划模型，并构建了一个基准案例P&U。此后，研究者逐步提出了各种精确算法、启发式算法、元启发式算法来求解该问题。随着制造单元中工作站数量的增加，分支定界等精确算法[2-4]在求解速度上难以令人满意；而在使用启发式或元启发式算法时，首先面临的难题是所研究问题的可行解空间狭窄，难以找到可行解，更难接近最优解。为此，人们采取多种措施，如减小搜索空间、不可行解修复等，以加快求解速度。其中，晏鹏宇等[5-6]计算出最大在制品数量，据此将解空间分割成若干子空间，将搜索过程限定在子空间内，通过无效空间的剔除提高了算法收敛速度。王跃岗等[7]在混合量子进化算法中加入基于图论的不可行解修复策略。……