黎英杰，刘建军，陈庆新，毛 宁

(广东工业大学 广东省计算机集成制造重点实验室,广东 广州 510006)

0 引言

装配作业车间是作业车间的一类现实化扩展，经由加工和组装两个阶段完成装配型产品制造，其调度问题既要考虑任务的工艺顺序约束，还要考虑任务间的装配关联约束，即关联零部件只有齐套才能开始装配[1]。相比作业车间调度问题(Job-shop Scheduling Problem, JSP)研究，装配作业车间调度问题(Assembly JSP, AJSP)的研究相对较少，且其生产调度更具挑战性[2]，目前主要分为不对装配体调度[3-4]和对装配体调度[5-8]两大类，前者假定最终产品的所有零部件齐套之后才开始装配作业，调度时只需附加一定的装配工期，不涉及具体的装配工序调度，适用于产品结构简单或装配时间相对加工时间较短的情况；后者需要同时考虑多层级物料清单(Bill of Material, BOM)结构中所有零部件的加工工序和装配工序调度，因此具有更高的复杂度。

多层级AJSP是将加工和装配一同处理的综合调度问题，也是一类典型的分层耦合约束(Hierarchically Coupled Constraint, HCC)优化问题[8]，其最终产品的总装开工时间受制于所需部件的完工时间，而上级部件的装配开工时间又受制于其直属零件/子部件的完工时间。随着产品复杂度的上升，多层级AJSP所含零部件工艺路径和工时需求也将呈现高度的差异性，导致满足此类分层耦合约束的进度协同更加复杂，现实生产中常表现为严重的装配前等待问题。因此，研究构建高效的多层级装配作业车间调度算法具有重要的意义，遗传算法因在理论研究和实际应用上基础很深而被广泛采用。……