钟宏扬，刘建军，黎英杰，陈庆新

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

作业车间调度问题 (job shop scheduling problem,JSP) 是一类具有工程应用背景的强NP难问题，传统的作业车间调度通常假设加工工件之间完全相互独立，加工工件的所有工序完工以后即视为可交付[1]。近年来，以客户为导向的多品种小批量生产方式兴起，产品的多元化装配结构使得装配工序调度复杂化，因此装配作业车间调度问题 (assembly job shop scheduling problem,AJSP) 也成为JSP问题的一类更具现实意义的拓展研究内容[2-4]。

装配作业车间包括加工和装配两个阶段，工序顺序与装配结构的强关联耦合约束为双阶段的调度计划提出了更多的协同需求[5]。当前AJSP研究大多集中在全局性齐套的装配，即假定产品的所有零部件齐套后直接进行总装作业，如文献[6]是在产品所有关联装配任务都完工后，附加一定的装配工期后即表示产品为完工，并不涉及具体装配资源的调度。但实际生产中产品也存在渐增性齐套的装配结构，关联零件先通过部装组成部件后，待部件齐套后再执行总装[7-8]。产品存在差异化的装配层次特征，加之多产品并行生产的特点，为装配资源调度提出了更多的挑战。

另一方面，在经典的JSP与AJSP问题中，加工任务被视为一个整体不可拆分。整批流转加工的方式虽然可以减少工序的准备时间，但也降低了车间物料运输的流动性，增加了订单在高负载强度生产环境下的拖期风险。对加工任务进行合理批量划分，可以促使子批交叠并行生产，进而提升车间的设备利用率，缩短生产周期[9-11]。……