秦俭 茹海鹏

摘要：柔性工件调度问题（FJSP）是一个强NP难问题，尽管对于一个小规模问题，也很难在多项式时间内最优求解。本文针对目标函数为最小化总完工时间的FJSP提出一种有效的启发式算法。该启发式算法易于实现，并能快速获得高质量的解。为验证该启发式算法的有效性，从文献中找出10组基准问题进行测试，并将求解结果与问题下界进行比较，结果表明本文设计的启发式算法能够在极短时间内获得相对误差较低的解。

关键词：柔性；工件调度；启发式

调度问题一般是指在一个给定的时间展望期内，将有限的资源分配给不同的任务，以使得某一目标达到最优。调度问题广泛存在于制造行业当中，对提高制造行业的生产效率等具有重要的作用。其中工件调度问题是实际生产中最为常见的一类调度问题。而在现代制造环境中，每台机器的加工类型趋于柔性化，即一台机器可以进行多种类型的操作，进而提出了柔性工件调度问题（FJSP），该问题在理论上和实践上都具有更加重要的意义。

1 FJSP问题描述

FJSP问题是指将个工件分配给m台机器进行加工，其中每个工件需依次经过步操作，而每一步操作都可以在某一可选机器集合中选择一台进行，每台机器可进行多种类型的操作。需要为每一步操作选择一台机器进行加工，同时还需决定在该台机器上开始加工的时间。显然，相较于经典的工件调度问题，FJSP还需为每步操作选定一台机器，这就使得FJSP更加复杂，该问题已经被证明是强NP难问题。……