顾幸生，丁豪杰

（华东理工大学信息科学与工程学院，上海200237）

调度是一个决策过程，是在规定的时间内进行有限资源的合理化配置，其目的是优化一个或多个目标［1］。而生产调度则是企业针对生产过程，进行有效、合理地规划，以便正常组织和开展产品的生产、加工或制造。生产调度问题是企业资源规划（enterprise resource planning，ERP）之后，制造执行系统（manufacturing executive system，MES）高效、顺利地完成产品制造的核心和关键［2］。根据系统的复杂性划分，柔性作业车间调度问题（flexible jobshop scheduling problem，FJSP）是最具代表性的一类调度问题。它将“在一组设备上加工完成一件产品”定义为一个作业（Job），其中参与加工的每台设备被定义为机器（Machine）；而一个作业根据加工工艺等限制，常被分成几个连续且相关的加工环节（单元）依次进行加工，这些加工环节被定义为工序（Operation）；工序是生产制造过程中最小的调度单元，每个工序每次只能被一台机器加工处理［3］。由于并行机等柔性设备的引入，柔性作业车间调度问题的求解需要同时对工序排序和机器选择两个子调度问题进行求解。

随着研究的深入，大量元启发式算法被用于对FJSP进行求解［4］。在对元启发式算法的改进和FJSP求解的研究过程中，Mesghouni等率先使用遗传算法对FJSP进行了求解［5］；Ong等进一步使用克隆和选择规则模拟人类免疫系统对FJSP进行求解［6］；Zribi等将遗传算法和局部搜索算法相混合对FJSP进行求解［7］；Tay和Ho混合遗传规划算法与调度分发规则求解FJSP［8］；Liouane等通过混合蚁群算法和禁忌搜索算法对FJSP进行求解［9］。21世纪以来，粒子群算法因其简捷、易于实现且便于与其他算法融合的特点而被国内外学者大量地尝试用于求解FJSP，并取得了丰富的成果。……