吕媛媛，樊 坤，瞿 华，周 浪

(北京林业大学 经济管理学院，北京 100083)

1 引 言

制造业是国民经济的基础与重要支柱，是我国市场程度比较高的领域，对经济发展有十分重要的作用.制造车间调度问题关系到企业整个生产系统的正常运转，关系到制造企业的生产效率与成本，因此，一直以来都是众多学者关注的热点问题.目前，针对多品种、小批量和个性化的市场需求，越来越多的离散制造企业采取面向订单的生产方式，同时具有可以并行、机器功能多、多处理机任务等生产特征，即车间生产往往会出现工件的一个或多个工序需要多台处理机同时进行加工的情况，因此无法用传统的具有单处理机任务约束的作业车间调度方法解决.基于此，有学者提出混合多处理机任务作业车间调度(Hybrid Job-shop Scheduling with Multiprocessor Task，HJSMT)模型[1].该模型中，多个工件具有多个不同加工工序，每个工序由一到多台处理机同时进行加工，显然它是作业车间调度(Job-shop Scheduling Problem，JSP)与多处理机任务调度(Multiprocessor Task Scheduling，MTS)相结合的新型混合车间调度问题.

目前混合车间调度领域研究多集中于柔性作业车间调度[2-4](作业车间调度混合并行机调度)和柔性流水车间调度[5,6](流水车间调度混合并行机调度)的研究.而HJSMT问题是多处理机任务调度与作业车间调度混合的调度问题，对于该问题研究相对较少.Brucker&Kramer[1]证明即使只有两台处理机的HJSMT问题已经是NP-hard难题.Brucker & Neyer[7]针对具有柔性特性的最小化总完工时间的 HJSMT模型提出一种禁忌搜索算法求解该模……