混合流水车间调度（HFSP）

学习文献 【混合流水车间调度问题研究综述】 –华中科技大学机械科学与工程学院

1.引言

        混合流水车间指的是按照流水式生产线布置，包含多道工序且每道工序有一台或多台并
行机器的生产车间，也称为柔性流水车间。如下图所示：

 1.1 HFSP 问题分类

        1）并行机类型HFSP分为三类：并行同速机 HFSP(Pm)，即工件在各阶段的每台机器上的加工时间是相同的；并行异速机 HFSP（Qm），指某一阶段的并行机有相同的功能但加工速度不同，工件在该阶段的每台机器上的加工时间是不同的；不相关并行机 HFSP(Rm)，即某一阶段的每台机器有不同的功能，且加工时间不同。目前，超过70％ 的文献集中在HFSP(Pm)，而HFSP（Qm）和 HFSP(Rm)的文献占比不足 30％ 。

        2）阶段数量的不同HFSP为三类:两阶段HFSP、三阶段HFSP、k阶段HFSP。目前，超过50%的文献集中在k 阶段HFSP。

        3）其他 ：考虑阶段间的有限缓冲区、机器的模糊加工时间、序列相关的准备时间等时间约束的HFSP研究等。

1.2 HFSP 和四类经典问题比较

 2.混合流水车间调度问题及数学模型

2.1问题描述

        HFSP可以描述为:n个工件在c(c≥2)个阶段上进行连续加工,阶段i有mi(mi≥1 ; i=1，2,…,c)台机器，且至少存在一个阶段有多台机器。HFSP需要根据各阶段上工件的加工顺序和机器分配,来优化某项或多项性能指标。

2.2数学模型

        基本HFSP的数学模型以完工时间为优化目标:

 公式1：最小化最大完工时间（目标）

公式2：各工件必须经过所有阶段，且每个阶段只能在一台机器上加工（单独对于每个工件）

公式3：表示同一阶段不同工件的先后约束顺序（工件之间存在约束）

公式4：一个约束条件。

公式5：表示同一台机器上的加工顺序。（公式4和5没看懂！有人看懂的可以评论区回复一下）

公式6：决策变量

公式7：定义工件第一阶段开始时间

公式8：表示各阶段上工件完工时间由上一个阶段完工时间和当前加工时间决定

 3.常用目标函数

4. HFSP的求解算法

4.1整数规划算法        

        最开始使用传统的整数规划算法，可以用来求解两阶段的问题，延申到k阶段有点吃力。之后，针对不同目标的多约束多阶段HFSP,需要建立MIP模型来了解问题的特征。针对k阶段的HFSP问题,SAWIK分别采用整数规划和一种层次结构方法求解了带多处理器的HFSP(Rm)。

4.2启发式算法       

        1）分派规则：通过工件的优先级和机器规则， HFSP的分派规则可以有效优化某一性能目标。分派规则可以在单一目标（完工时间或延迟时间）下找到合理的调度方案，也可以快速
求解较大规模的问题。但是，实际的目标设定往往非常复杂，尤其是一些复杂的扩展问题，由于分
派规则的设计对问题的研究不够深入，一般很难求得问题的较好解。

         2）局部搜索算法：局部搜索算法对当前解的关键路径上的工序块进行有效的扰动来更新当前解。对非关键路径上工序块的扰动不能有效地更新当前解，所以，常用的 VNS ( variable neighborhood search)、ILS(iterated local search)和 IG (iterated greedy)等局部搜索算法需要进行贪婪式的搜索﹐以调整关键路径上的关键工序。上述的局部搜索算法可以求解较大规模的HFSP,具有较好的实用性,但邻域结构的设计不是基于关键路径,搜索较慢且效果较差。另外，HFSP的一个可行调度解包含多条关键路径,这使得查找关键路径的工作难度大,现有的HFSP研究还未涉及。

 4.3 元启发式算法

        元启发式算法将随机因素引入整个搜索过程，并多次调用和引导算法产生更优解。设计元启发式算法的关键是算法框架的构建、编解码的设计、结合问题特征迭代算子的设计、权衡全局搜索与局部搜索和算法参数设定等。基础的元启发式算法的计算量大、迭代时间长、局部搜索能力较差，导致进化后期的搜索效率较低。因此，将分派规则和局部搜索算法与元启发式算法相结合，分别用于优化初始种群、强化局部搜索能力。

4.4 学习型算法

学习型算法采用大型复杂系统来提取离散型 HFSP的有效信息，构建问题框架，通过可靠可行的数据点来分析和调控搜索过程。与HFSP的启发式和元启发式算法相比，学习型算法研究较少.

5.标准测试集

        标准测试集( Benchmark)是求解问题的一个基准,是验证算法有效性的可靠标准。算法要在测试集上不断地验证其效力,才能更好地用于实际的问题。HFSP(Pm)的测试集一共17类。CARLIER等提出的77个经典算例、LIAO等提出的10个算例使用较多。FERNANDEZ-VIAGAS等总结这17类测试集,提出了新的HFSP( Pm)标准测试集:240个小规模算例和240个大规模算例,采用IG算法对新算例进行了求解﹐并给出了上界值,但未给出理论下界值。HFSP(Qm)和 HFSP(Rm)的研究较少,没有学者提出标准测试集,而其他扩展HFSP的研究只是延续了HFSP( Pm)的阶段数和机器特征,采用随机算例来验证所提出的算法性能。