求解柔性工件调度问题的启发式算法

秦俭 茹海鹏

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

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

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

1 FJSP问题描述

FJSP问题是指将个工件分配给m台机器进行加工，其中每个工件需依次经过步操作，而每一步操作都可以在某一可选机器集合中选择一台进行，每台机器可进行多种类型的操作。需要为每一步操作选择一台机器进行加工，同时还需决定在该台机器上开始加工的时间。显然，相较于经典的工件调度问题，FJSP还需为每步操作选定一台机器，这就使得FJSP更加复杂，该问题已经被证明是强NP难问题。[1]本文将针对目标为最小化总完工时间的FJSP设计一种有效的启发式算法，可以在极短时间内获得高质量的解。

2 设计启发式算法求解FJSP问题

构造的启发式如下：将工件和机器分别按照的降序和的升序排列，为操作选择机器的总体思路为，首先依次调度所有工件的第一步操作，再调度所有工件的第二步操作，以此类推，直至所有工件的所有操作均调度完成，此时即可得到一份完整的工件调度结果。具体来说，针对操作，对每台机器，分别计算评价函数

分别为上述四项标准的权重，即表示各自的重要程度。

令，即针对操作，找到最小评价函数值所对应的机器，则将操作安排在机器上加工，同时该机器的最大完工时间变为，继续根据上述评价函数调度下一操作，直至所有工件的操作j均调度完成。此时开始对所有工件的操作j+1按照同样的办法分配机器，直至所有工件都分配完毕，则可获得一份完整的工件调度。

3 数据测试

为了测试算法的有效性，本文从Brandimarte[2]中选取了5组经常被其它文献引用的基准问题（benchmark problem）进行测试。本文在求解时间、最大完工时间以及与下界的相对误差等方面，对本文所提的启发式算法及文献[3]中的算法进行了比较，比较结果如下表所示。该实验结果表明：

4 结论

本文通过构造启发式算法求解柔性工件调度（FJSP）问题。针对一组基准问题，可获得高质量的解。结果表明，针对40个和50个工件的问题，获得最优解的比例分别可以达到100%以及80%，对于100个工件的问题，相对误差率也仅有0.99%。这说明该算法对于大规模的SMTWT问题也可以获得质量较高的解。

参考文献：

[1]Garey MR，Johnson DS，Sethi R.The complexity of flow shop and jobshop scheduling[J].Mathematics of Operations Research，1976，1（2）：117129.

[2]Brandimarte P.Routing and scheduling in a flexible job shop by tabu search[J].Annals of Operations Research，1993，41（1）：157183.

[3]Li JQ.A hybrid tabu search algorithm with an efficient neighborhood structure for the flexible job shop scheduling problem[J].International Journal of Advanced Manufacturing Technology，2010，52（58）：683697.

作者简介：秦俭（1981），女，汉族，辽宁沈阳人，硕士，讲师，研究方向：应用数学；茹海鹏（1983），男，汉族，辽宁葫芦岛人，本科，工程师，研究方向：壓缩机。