轩 华，郑倩倩，李 冰

(郑州大学 管理工程学院，河南 郑州 450001)

0 引 言

柔性流水车间问题(flexible flowshop problem，FFP)最初是从石油工业提炼出来的[1]，它由多个生产阶段组成，至少有一个阶段含两台或两台以上的并行机。在经典FFP中，多假定同一阶段的并行机是同构的，然而完成同一工序的机器由于新旧程度等可能会导致加工时间有所不同，因此，引起含不相关并行机的FFP的研究，考虑到实际生产中很多车间无中间缓冲，即当工件完成一道工序后若下游机器正处于繁忙状态，则它需停留在该工序的机器上直至下游机器空闲。这类问题称之为含不相关并行机的阻塞FFP(blocking FFP with unrelated parallel machines，BFFP-UPM)，由于一般的多阶段FFP是NP-hard[2]，故所研究的更复杂的BFFP-UPM也是NP-hard问题。

针对带阻塞约束的车间调度问题多围绕流水车间展开[3-7]，但近几年也有一些文献关于带阻塞约束的FFP进行了研究，在同构机环境下，以最小化最大完成时间为目标，文献[8,9]研究了含阻塞约束的两阶段可重入FFP，分别提出了元启发式和混合粒子群优化算法；文献[10]将同贝同步装卸抽象为柔性流水车间，结合阻塞、批处理和无等待要求，提出了一种融和启发式分配规则和禁忌搜索的优化方法；文献[11]以外科资源成本为目标，构造了两种混合整数规划模型。在不相关并行机条件下，文献[12]结合双信息素和遗传算法提出了蚁群优化解决带运输时间和释放时间的FFP；文献[13]提出了一种离散布谷鸟分散算法，测试了多达20个工件的小规模问题；文献[14]为最小化最大完成时间建立了4个混合整数线性规划模型，设计了改进回溯搜索算法求解中大规模问题；……