曾创锋，刘建军，陈庆新，毛 宁

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

家电企业总装车间中，来自客户的工单具有多品种、小批量的特征，每一张工单都将生产某一型号的一款产品，生产该型产品需要指定的型号物料；加工单元由多条异构的并行加工线体构成，加工线体所采用的技术、线体新旧程度有所不同，部分型号的物料只能在指定的部分线体上进行加工，同时，根据相邻工单所加工的产品型号及其使用的物料型号的异同，需要对线体的设置进行相关调整。这类问题属于典型的带工单加工约束和序相关设置时间的无关并行机调度问题(unrelated parallel machine scheduling problem with job processing constraints and sequence-dependent setup times，UPMSP_JPCSST)，即同一张工单在不同线体上的加工时间不尽相同，且工单只能在特定的部分线体上进行加工，同时，工单上机的设置时间取决于前后相邻工单的顺序。该问题以极小化最大完工时间(Cmax)为优化目标，使用三元组[1-2]可以将其描述为Rm|si,j,Mj|Cmax。UPMSP_JPCSST是UPMSP中非常复杂的一类，属于NP完全问题，对其进行求解非常困难。因此，对UPMSP_JPCSST求解算法的研究具有较高的理论和应用价值。

目前对于UPMSP_JPCSST的求解方法主要有精确算法、启发式规则和元启发式方法。其中，精确算法经常使用混合整数规划(mixed integer programming, MIP)模型、分枝定界[3]等方法以求得问题的最优解，但求解费时并受限于问题的规模，难以对问题进行快速求解；而启发式规则[4]虽然易于实施，但所得解的质量难以保证；而元启发式方法则有较大的塑性空间，其求解……