赵晓飞，郭秀萍

(1.西南交通大学 经济管理学院，成都 610031； 2.重庆文理学院 经济管理学院，重庆402160)(*通信作者电子邮箱guoxiuping0029@sina.com)

0 引言

机器人制造单元是一种先进生产系统，广泛应用于机械制造、电路板印刷(Printed Circuit Board, PCB)以及半导体制造等行业[1-4]。典型机器人制造单元由一个输入装置、一个输出装置、多个工作站以及一个由计算机控制的机器人组成。

由于市场需求由大批量、少品种向小批量、多品种转变，且机器人制造单元技术改进，使得机器人制造单元由生产同类型工件向生产多类型工件转换[5-6]。为了合理生产多类型工件，提高系统效率，将待加工的多类型工件组成一个最小工件集(Minimum Part Set, MPS)，按照混流方式周期生产。

由于文献[7]证明了工作站数大于2的混流生产机器人制造单元调度问题是非确定性多项式(Non-Deterministic Polynomial， NP)难的，因此以工作站个数为分类标准，将该问题分为两大类：一类是工作站数等于2；一类是工作站数大于2。工作站数等于2时，该问题可以转化为推销员旅行问题(Travel Saleman Problem, TSP)[8-10]，易于求解，但仅限于1-度生产策略情形。工作站数等于3时，研究者通过枚举机器人运行顺序[7,9,11-12]，设计了多种启发式方法，但这些方法没能同时优化工件加工顺序和机器人运行顺序。文献[13]首次同时优化了工件加工顺序和机器人运行顺序，并证实了同时优化工件加工顺序和机器人运行顺序优于固定一个顺序优化另一个顺序，但该研究前提是工作站数等于3。文献[14-15]在文献[13]研究基础上，首次设计化学反应优化求解该问题，得到了更好解。……