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

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

　　郭 宇[1]

　　（沈阳理工大学 理学院，辽宁 沈阳 110159）

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

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

　　中图分类号：TP301.6 文献标识码：A

　　调度问题一般是指在一个给定的时间展望期内，将有限的资源分配给不同的任务，以使得某一目标达到最优。调度问题广泛存在于制造行业当中，对提高制造行业的生产效率等具有重要的作用。其中工件调度问题是实际生产中最为常见的一类调度问题。设有n个工件，m台机器，每台机器只能进行一类操作，工件i需依次经过

　　步操作，而每一步操作都需要在一台特定的机器上进行，同时每个工件的每一步操作的加工时间是已知的，在整个时间展望期内，所有机器都是连续可用的，并且在同一时刻只能进行一种操作，而每步操作一旦开始进行，直至操作完成，中间不会被中断。工件调度问题已经被证明是NP难问题[1]，由于问题的实践性以及求解的困难性，工件调度问题已经受到许多学者的关注，并进行了广泛的研究。

　　而在现代制造环境中，每台机器的加工类型趋于柔性化，即一台机器可以进行多种类型的操作，进而提出了柔性工件调度问题（FJSP），该问题在理论上和实践上都具有更加重要的意义。

　　1 FJSP问题描述

　　FJSP问题是指将

　　个工件分配给m台机器进行加工，其中每个工件需依次经过

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

　　在本文中，将做下列合理的假设：1）工件之间相互独立；2）机器之间相互独立；3）机器的调试时间和工件的运输时间忽略不计；4）同一操作不能同时在两台机器上进行；5）所有工件的加工优先级相同；6）所有工件以及所有机器在零时刻可用。

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

　　算法中将要用到的符号定义如下：

　　：工件i所需要的操作j；

　　：操作

　　在机器y上的加工时间；

　　：操作

　　的完工时间；

　　： 能够加工操作

　　的机器集合；

　　：机器集合

　　中包含的机器台数；

　　：操作

　　的平均加工时间，有

　　；

　　： 工件i的平均总加工时间，有

　　；

　　： 机器y的总加工时间，有

　　；

　　构造的启发式算法如下：将工件和机器分别按照

　　的降序和

　　的升序排列，为操作

　　选择机器的总体思路为，首先依次调度所有工件的第一步操作，再调度所有工件的第二步操作，以此类推，直至所有工件的所有操作均调度完成，此时即可得到一份完整的工件调度结果。具体来说，针对操作

　　，对每台机器

　　，分别计算评价函数

　　其中

　　表示机器y的最大完工时间；

　　表示机器y的闲置时间；

　　表示工件i的等待时间；

　　表示操作

　　在机器y上的加工时间；

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

　　令

　　，即针对操作

　　，找到最小评价函数值所对应的机器

　　，则将操作

　　安排在机器

　　上加工，同时该机器的最大完工时间变为

　　，继续根据上述评价函数调度下一操作

　　，直至所有工件的操作j均调度完成。此时开始对所有工件的操作j+1按照同样的办法分配机器，直至所有工件都分配完毕，则可获得一份完整的工件调度。

　　该启发式算法的流程图如图1所示。

　　3 数据测试

　　为了测试算法的有效性，本文从Brandimarte[2]中选取了5组经常被其它文献引用的基准问题（benchmark problem）进行测试，并与近期的四篇文献[3-6]中的结果进行了比较。其中评价函数中四项标准的权重分别取为

　　。本文在求解时间、最大完工时间以及与下界的相对误差等方面，对本文所提的启发式算法及其它四篇文献中的算法进行了比较，比较结果如表1所示。该实验结果表明，

　　图1 启发式算法流程图

　　表1 启发式算法与其它四种算法的结果比较

　　(续表1)

　　4 结论

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

　　参考文献：

　　[1]Garey MR, Johnson DS, Sethi R. The complexity of flow shop and job-shop scheduling[J]. Mathematics of Operations Research, 1976,1(2):117-129.

　　[2]Brandimarte P. Routing and scheduling in a flexible job shop by tabu search[J]. Annals of Operations Research, 1993,41(1):157-183.

　　[3]Li J-Q. 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(5-8):683-697.

　　[4]Xing L-N. A knowledge-based ant colony optimization for flexible job shop scheduling problems[J]. Applied Soft Computing, 2010,10(2):888-896.

　　[5]Wang L. An effective artificial bee colony algorithm for the flexible job-shop scheduling problem[J]. International Journal of Advanced Manufacturing Technology, 2012,60(4):303-315.

　　[6]Yuan Y. A hybrid harmony search algorithm for the flexible job shop scheduling problem[J]. Applied Soft Computing, 2013,13(2):3259-3272.