具有安装时间的置换流水车间组合干扰管理研究

王建军，侯晓文，刘晓盼，缪鸿儒

具有安装时间的置换流水车间组合干扰管理研究

王建军，侯晓文，刘晓盼，缪鸿儒

（大连理工大学 经济管理学院，辽宁 大连 116023）

针对安装时间与次序相关的置换流水车间环境，研究随机机器故障、加工时间改变、安装时间改变、工件优先级提高、新工件到达、工件取消加工六类常见干扰事件部分或者全部组合发生情况下，考虑初始目标最大完工时间和扰动目标次序变动总量的干扰管理问题。经分析，该问题为NP难问题。通过改进初始种群构建策略以及全局搜索和局部搜索间权衡策略，提出改进文化基因算法对该问题进行求解。最后设计随机干扰算例，分别在初始种群改进前后同经典的NSGA-II算法进行对比，结果验证了本文所提初始种群构建策略和改进文化基因算法在应对不同组合干扰事件和不同问题规模下的有效性。

干扰管理；组合干扰；安装时间；文化基因算法；有效前沿

0 引言

流水车间调度问题（Flow shop Scheduling）作为实际生产加工环境可广泛抽象化的模型，在冶金、食品加工和手术排程等制造、服务领域有着较为普遍的应用[1]。绝大多数情况下属于NP-难问题，求解较为困难；再加之具有较强的实际应用背景而备受学者们青睐，虽然目前已取得较为丰硕的理论研究成果[2]。但大部分理论成果却很难运用到生产实践，其中一个重要的原因是：大部分流水车间调度研究往往忽略了在实际生产过程中面临的诸多不确定性因素，如机器故障、订单变更等干扰事件，这些干扰事件常常造成初始调度方案执行不畅、效率低下、甚至不再可行[3]。近年来，流水车间干扰管理问题已引起学术界和产业界的广泛关注度[3-17]。

近几年来，已有部分研究者考虑在流水车间环境下进行基于单一干扰事件的研究。如李铁克等[4]针对生产过程中可能会出现的机器故障干扰事件，通过一致性权重来量化工件间对时间安排一致性和机器指派一致性要求的差异，并设计局部性修复算法求解有效的生产调度干扰管理方案。Wang等[5]研究了机器故障后的最大完工时间最小化问题，通过将原问题分解为多个简单集群排序问题来获得有效解。与前者目标一致，Wang等[6]提出基于模糊逻辑的混合分布估计算法（FL-HEDA）对问题进行求解。针对新工件到达干扰事件，Weng等[7]研究了新到达工件的JIT(Just In Time)生产问题，设计基于分布计算的路径选择策略，并与指派规则结合使问题得到了有效的求解。王建军等[1]则考虑了人的“有限理性”行为，提出基于前景理论的综合扰动度量，并设计了具有一般通用性的元启发式算法混合策略对问题进行求解。此外部分学者还对产品返工、紧急订单等干扰事件进行了研究，但相对较少。Rabiee等[8]针对无等待的两台机器流水车间中出现返工时的最小化平均完工时间问题；提出称为适应性帝国竞争算法的元启发式算法进行求解。Hu等[9]针对紧急订单到达后的加权平均流程时间最小化问题，考虑到紧急订单的加工优先级较高从而赋予更大的权重，并设计蚁群算法对问题进行有效求解。

然而现实加工过程中单一干扰事件发生的情形较少，通常是多种干扰事件组合发生，该情况的处理相对于单一干扰事件更为复杂[11]，并且在这种情况下有可能对当前的调度方案产生更大的影响，因此有研究者提出：如何应对组合干扰事件至关重要[10]。Katragjini等[10]研究了新工件达到、机器故障、加工时间可变三种干扰事件同时发生情况下的干扰管理问题，并提出有效的重调度方法来权衡调度的性能和稳定性。相较于前者，Li等[12]增加了工件取消加工和工件就绪时间可变干扰事件，并提出了基于教与学的离散优化算法对问题进行了有效求解。与上述文献中的应对方式不同，Rahmani等[13]提出预测-反应式策略来应对不确定加工时间和新工件到达组合干扰事件，第一步是利用鲁棒优化方法获得对加工时间变动不敏感的鲁棒初始调度方案；第二步则是当新工件到达后选择合适的反应式方法优化调度的最大完工时间、鲁棒性度量和稳定性度量三个目标，并通过线性加权将其转化为单目标问题求解。然而相对于不考虑干扰事件或单一干扰事件的研究而言，考虑多种干扰事件组合发生情况下的调度研究还较少。

除了干扰事件的影响之外，理论研究工作无法应用到实践中的另外一个重要原因，则是在加工不同工件的过程中往往需要进行设备清洗、模具更换、工件运输等额外操作，因此通常在相邻工件间存在一定的安装时间[2]。然而，绝大多数流水车间下的干扰管理研究假设是没有安装时间，或者安装时间与加工次序无关从而视为加工时间一部分不予考虑。然而当安装时间与次序相关时，就会对调度结果产生无法忽视的影响[14]。Gholami等[15]研究了在安装时间与次序相关的混合流水车间环境下，出现随机机器故障时完工时间期望的优化问题；运用遗传算法来获取最优解，并结合由事件驱动策略与右移启发式方法所构造的模拟器来评价完工时间期望。同样的研究问题，Zandieh等[16]则通过将模拟仿真与免疫算法相结合的方式对问题进行了求解。与上述干扰事件不同，Kianfar等[17]研究了柔性流水车间下工件动态到达时的平均延迟时间最小化问题，提出以协同调度为主并结合柔性流水车间、安装时间、延迟性能度量三因素的基于搜索的指派规则，以及基于遗传算法的混合方法，使问题得到了有效的解决。

由文献综述可知，第一，流水车间环境下的组合干扰事件和安装时间与次序相关的干扰管理问题在现实生活中普遍存在，且已引起部分学者的关注；虽然已有相关学者对单一干扰事件或较少干扰事件发生的情况展开了研究，但对六类常见干扰事件部分或全部组合发生的干扰管理研究较少。其次虽已有相关文献说明相邻工件间存在的安装时间对车间调度的实际应用有着很大的影响，但大部分研究都是未考虑安装时间的，或者简单的将安装时间视为加工时间的一部分，尤其是对结合多种干扰事件组合发生和安装时间与次序相关的干扰管理问题研究较为匮乏。因其模型构建较为复杂，通常均为NP-难问题，求解较为困难。第二，现有干扰管理研究大部分为单目标问题或者多目标通过线性加权转化为单目标进行处理，而忽略了干扰管理问题中初始目标与扰动目标之间的权衡影响。

针对以上两点研究不足，本研究在置换流水车间环境下，考虑安装时间与次序相关以及六类常见干扰事件部分或全部组合发生情况下，同时最小化重调度后初始目标最大完工时间和扰动目标次序变动总量。为了求解此复杂的多目标干扰管理问题，本文以文化基因算法为框架，基于问题和算法的特性，通过改进初始种群构建策略以及全局搜索和局部搜索权衡策略，提出改进文化基因算法对问题进行有效求解。并且通过数值实验验证本文所提出的改进策略和算法的高效性以及所提初始种群构建策略和改进文化基因算法在对不同组合干扰事件和不同问题规模时的普遍适用性。

1 问题描述

图1 初始加工时间表

Figure 1 The baseline schedule

然而实际生产加工过程中往往存在众多干扰事件，基于干扰事件来源的不同可分为外部干扰事件和内部干扰事件两大类。外部干扰事件指由于外部市场需求改变而造成的干扰事件，如工件优先级变化、工件取消加工、新工件到达等。内部干扰事件则是指因车间内部生产设备老旧或技术变更而导致的干扰事件，如随机机器故障、加工时间改变、安装时间改变等。由于以上干扰事件的存在，初始加工时间表通常无法顺利执行。这种情况下则需要在干扰事件发生后，对还未加工的工件进行重调度来尽可能的减小由于干扰事件对初始排序造成的影响。本文在上述所提到的六种常见干扰事件部分或全部组合发生的情况下，对各干扰事件的处理方式参考文献[12]并做出如下假设：

（1）对于任何机器故障事件，其故障发生时刻和持续时间都是事先未知的；因机器故障而被迫中断加工的工件待机器恢复后，接着之前未完成的操作继续加工，即执行“中断-继续”操作。

（2）受加工时间改变、安装时间改变、优先级提高、取消加工四类干扰事件影响的加工工件在未加工工件集中随机产生。

（4）当工件优先级提高后，将其安排在已加工工件集后进行及时加工；当新工件到达生产加工系统时，将其安排到初始加工次序最后进行加工；当工件取消加工任务时，将其从初始加工次序中删除。

（5）所有受干扰事件影响的工件，按照假设（1）~（4）进行处理后，其它工件依次顺延，加工时间表也进行相应调整。

2 求解算法

安装时间与次序相关的单机最大完工时间max最小化调度问题可视为旅行商问题的特例，属于典型的NP-难问题。本文在此基础上将问题扩展到更为复杂的置换流水车间环境，因此求解更为困难，同样也意味着难以通过精确型算法进行有效求解[18]。而智能优化算法则是从若干初始解开始，通过进化搜索能够在有效时间内获得较好的解集，也是目前解决置换流水车间调度问题最为广泛的方法[1]。

随着现实问题的日趋复杂及求解难度的不断加大，单一智能优化算法已无法取得满意的结果，进行算法混合实现优势互补已成为目前的研究趋势和热点[19]。其中全局搜索与局部搜索相结合的算法混合思路在解决复杂组合优化问题中表现出较好的性能，而文化基因算法(Memetic)正与此相契合。因此本文在求解算法方面借助于文化基因算法的思想框架，针对所提出的双目标干扰管理问题，通过改进多目标初始种群构建策略和全局搜索与局部搜索的权衡策略，在全局搜索和局部搜索的关键环节中选择合适的处理方式，最终提出改进文化基因算法对问题进行求解。

2.1 初始种群构建策略

2.2 改进文化基因算法

如前文所述，本文提出的多目标干扰管理问题是一个复杂的组合优化问题，而文化基因算法中的全局搜索与局部搜索相结合的算法混合思路在解决复杂组合优化问题中表现出较好的性能，能够有效提高算法的收敛速度；同时也增加了每代消耗时间，从而减少了搜索代数[21]。其中全局搜索是对解空间全局性探索的过程，直接影响着算法的收敛性和多样性。而局部搜索则是对遗传操作后的个体进一步改进的过程，影响着最终解的质量好坏。为了满足在合理时间能得到质量较好的近似解的要求，除了在2.1节对初始种群的生成策略进行改进外，还需要根据问题和算法的特性对全局搜索和局部搜索中关键的步骤进行设计和改进处理。

2.2.1 全局搜索策略

2.2.2 局部搜索策略

（2）在邻域结构确定上，本文为了能够继承父代的优良基因且具备多样性，借鉴已在相关置换流水车间调度研究[21,23]中获得较好结果的方法：选择为连续多基因位插入操作，连续基因的个数控制在三个以内，如图2所示。

图2 邻域结构示意图

Figure 2 Neighborhood structure

（3）在新个体的接收准则上，常见的做法是若新个体相较于目标个体更优，则用新个体来替换目标个体[21]，然而这样容易错失一些整体较优的目标个体。本文最终想要给出质量较好的帕累托最优解，为了避免丢弃一些支配其它个体的帕累托最优解。算法采取只要新个体不被目标个体所支配则接收该个体为新解，并保留目标个体的做法。并在种群更新时进行整体排序，择优进入下一代。

图3 改进文化基因算法流程图

Figure 3 The framework of improved memetic algorithm

在更新种群时为了能够改善每代种群的整体质量，采用的种群更新机制为择优进入下代。首先将上代种群与本代产生的新解合并去重，然后对其进行非支配排序，最后选择排序靠前的满足种群数量的个体构成下代种群参与后续操作。而算法的终止条件同文献[21]采用函数评价10万次。

综上所述，通过对初始种群构建的改进，对全局搜索和局部搜索中关键步骤的设计，以及提出局部搜索效率的设定对局部搜索的强度进行改进，从而使得算法满足本文问题的实际求解要求，平衡计算资源在全局搜索和局部搜索之间的分配，并且极大程度的提高了算法的性能。本文提出的改进文化基因算法流程图如图3所示。

3 数值实验

针对本文提出的具有安装时间的置换流水车间组合干扰管理问题，为了验证所提初始种群构建策略和改进文化基因算法在求解六种干扰事件部分或者全部组合情况下的有效性，我们分别在运用初始种群构建策略前后与目前最为流行的多目标算法NSGA-II进行对比。为了比较的公平性，其中NSGA-II算法遗传操作与文化基因算法保持一致。本部分首先对实验算例参数和算法参数进行设计说明，给出对比实验中的五个有效前沿比较指标；最后通过对比实验结果并对其进行分析。

3.1 数值实验设计

（4）新到达工件：新工件的加工时间和安装时间的设置与初始调度问题设置一致。

为了验证对于不同干扰事件组合的普适性，每个算例分别考虑常见的三种干扰事件组合情况。第一种由于外部需求而发生的组合干扰事件，包括新工件到达、工件优先级变化、取消工件加工任务；第二种则是由于加工车间内部设备老旧或者技术改变而发生的组合干扰事件，包括随机机器故障、加工时间改变、安装时间改变。第三种则是上述外部干扰事件和内部干扰事件同时发生的全部组合干扰事件。

为了更有效地比较本文提出的改进策略和改进算法的有效性，借鉴文献[24-27]中的五个性能指标，分别从非支配解集的临近性、多样性、综合性三个方面对有效前沿进行评价。五个比较指标如下所示（比较指标的具体定义和计算公式，可查阅对应文献）：

本文算法采用MATLAB语言进行编程，运行环境为MATLAB7.10.0，；计算机CPU为Intel(R) Core(TM)2 Duo CPU，内存为2G，主频为3.00GHz。在对比实验的算法参数设置上，通过预先在100个工件10台机器规模下六种干扰事件组合发生情况下的进行随机数值实验，从而对NSGA-II算法和改进文化基因算法中的参数进行调整和确定。首先对NSGA-II算法进行调参，该算法共涉及种群规模、交叉概率、变异概率三个参数，分别取100、150、200； 0.7、0.8、0.9；0.05、0.10、0.15，共27种组合，取五次实验结果中平均超体积最小的参数组合。然后对改进文化基因算法的参数进行调整和确定，涉及到与NSGA-II共有的参数取值与其保持一致；而复制淘汰比例、局部搜索周期、局部搜索步长三个参数，分别取0.1、0.2、0.3；3、4、5；1、2、3，确定过程与前面三个参数相同。最后算法所涉及的参数值如表1所示。

表1 算法参数设置

3.2 实验结果与分析

3.2.1 不同组合干扰事件时有效性分析

为了验证本文提出的初始种群构建策略与改进文化基因算法，在应对不同组合干扰事件时的普遍适用性；因此在5台机器50个工件的问题规模下针对外部组合干扰事件、内部组合干扰事件、全部组合干扰事件3种不同组合分别进行了10组随机数值实验。

将改进文化基因算法和NSGA-II算法，同随机初始种群策略和所提构建初始种群策略进行相互组合，可以得到4种策略，并对就其有效前沿进行对比，如图4所示。可以看到不同组合干扰事件时，在初始种群生成策略相同的情况下，改进文化基因算法所得有效前沿完全支配NSGA-II算法所获得的有效前沿解；而在算法相同的情况下，运用所提构建初始种群策略得到的有效前沿解要完全支配随机初始种群产生的解。因此，从有效前沿对比图中可以较为直观得验证所提初始种群构建策略与改进文化基因算法的有效性。

由图4可见，相比外部组合干扰事件，内容组合干扰事件对企业的生产管理造成的影响更大，所以生产管理者应更加关注内部干扰事件组合发生的情况。内外干扰事件组合发生时，对企业初始目标和扰动目标都会造成较大的影响，但扰动目标变化更加敏感。因此，生产管理者应尽量避免内外干扰事件组合发生情况的出现；如果内外干扰事件组合发生，建议生产管理者采取首先确定扰动目标范围，然后获取初始目标的策略，这样有望获得更佳的管理效果。

同时就不同算法与初始种群生成策略相互组合得到的4种策略，针对不同组合干扰事件分别计算10个随机算例下的有效前沿指标均值，并对其进行了归一化处理。在图5中我们针对每个有效前沿指标，按照越向外越优的方向进行绘制，图形面积可直观地反应出策略整体性能。因此可得出“文化基因算法+构建初始种群”表现最佳，随后为“NSGA-II算法+构建初始种群”、“文化基因算法+随机初始种群”，表现最差的则是“NSGA-II算法+随机初始种群”。并且可以发现相对于外部组合干扰事件和内部组合干扰事件，当全部组合干扰事件发生时，有效前沿变得非常陡峭，表明此时目标函数对决策的权衡取舍非常敏感，同时也说明在这种情况下为不同决策者提供有效前沿是十分必要的。

图4 不同组合干扰事件时的有效前沿对比

Figure 4 Pareto front comparison of different combinational events

图4（续） 不同组合干扰事件时的有效前沿对比

Figure 4(continue) Pareto front comparison of different combinational events

除此之外，对4种策略的不同指标进行分析。综合性指标超体积HV，以及临近性指标世代距离GD和非支配距离NDS_DIS三个指标上策略的优劣顺序与整体性分析所得一致。在多样性指标有效前沿解数量ONVG上，文化基因算法与NSGA-II算法不相上下，而所提构建初始种群策略相较于随机初始种群策略依然具有较强的优势；同时在另一多样性指标非支配解数量NDS_NUM上，文化基因算法与所提构建初始种群策略都表现出较强的优势，反应了有效前沿解较好的质量。

图5 不同组合干扰事件时的有效前沿指标分析

Figure 5 Index analysis of different combinational events

注：按照越向外越优的方向进行绘制，图形面积越大反应出策略整体性能越好

3.2.2 不同问题规模情况下有效性分析

为了验证所提初始种群构建策略与改进文化基因算法，在不同问题规模情况下的普遍适用性；因此分别考虑工件个数=25、50、100，机器台数=3、5、10的情况，同一问题规模下针对外部组合干扰事件、内部组合干扰事件、全部组合干扰事件3种不同组合分别随机进行10组数值实验。

针对不同算法与初始种群生成策略相互组合得到的4种策略，分别计算在9种不同规模下综合性指标超体积HV的误差棒图，如图6所示。在同一问题规模下，4种策略的表现优劣顺序依然为“文化基因算法+构建初始种群”表现最佳，随后为“NSGA-II算法+构建初始种群”、“文化基因算法+随机初始种群”，表现最差的则是“NSGA-II算法+随机初始种群”。

表2 数值实验结果指标对比分析

在机器数量相同，工件数量规模不断增大过程中，改进文化基因算法相较于经典NSGA-II算法，所提构建初始种群策略相较于随机初始种群的优势开始体现的越明显。原因可以归结为两点：第一，随着工件数量的增加，解空间也在增加；此时改进文化基因算法能够利用局部搜索将有限计算资源集中运用到较优解的搜索方向，避免了资源的浪费。第二，所提构建初始种群能够一定程度上给后期搜索工作指明方向，避免了盲目的搜索。而工件数量相同，机器数量规模不断增加的过程中相应HV的增加，仅仅是由于相应的最大完工时间增加的原因，因此不做过多分析。

同时就不同算法与初始种群生成策略相互组合得到的4种策略，针对不同规模下不同组合干扰事件分别计算10个随机算例下的有效前沿指标均值，并对其进行了归一化处理。如表2所示。就综合性指标而言，全部数据所呈现的超体积HV大小关系，显示4种策略优劣顺序与之前分析一致，再次表明改进文化基因算法和所提初始种群构建策略的有效性。下面分别对有效前沿的临近性和多样性分别进行分析。

图6 不同问题规模情况下超体积HV的误差棒图

Figure 6 The error bBar chart of hyper-volume in different scale

在临近性方面，世代距离GD指标和非支配距离NDS_DIS指标，绝大多数是在初始种群生成策略相同的情况下，改进文化基因算法比NSGA-II算法的指标值小；在算法相同的情况下，运用所提构建初始种群策略要比随机初始种群得到的指标值小。因此，可以验证改进文化基因算法和所提初始种群构建策略在有效前沿临近性具有优越性。

在多样性方面，从有效前沿解的数量ONVG指标上可以看出，在初始种群生成策略相同的情况下，改进文化基因算法与NSGA-II算法的表现不相上下；而在算法相同的情况下，所有运用构建初始种群策略的要比随机初始种群的有效前沿数量多。构建初始种群策略在ONVG指标上的优势，主要原因是初始种群中所加入的两个单目标较优种群具有一定的相似性，这样有利于广度搜索更加有效，增加了非支配排序中相同层级的解。从非支配解的数量NDS_DIS指标上，可以得出与之前4种策略优劣顺序一致的结果。之所以此时改进文化基因算法能够具有明显的优势，主要原因是通过适度有效的局部搜索，有利于解的深度搜索更加有效，提升了非支配排序中解的层级。

4 结论

在安装时间与次序相关的置换流水车间环境下，研究机器故障、加工时间改变、安装时间改变、新工件到达、工件优先级提高、工件取消加工六类常见干扰事件部分或者全部组合发生情况下的干扰管理问题。组合干扰事件发生后为了保持良好的调度性能(最大完工时间)而进行重调度，同时考虑给生产车间带来的扰动目标次序变化，因此为多目标重调度问题。为了获得较好的有效前沿，提出各单目标较优种群与随机生成种群相结合的初始种群构建策略，以及通过权衡全局搜索和局部搜索关系的改进文化基因算法来对问题进行求解。

通过数值实验表明：（1）通过单目标较优种群与随机生成种群相结合的初始种群构建策略能够有效改善帕累托有效前沿的质量。（2）通过调整局部搜索强度来平衡全局搜索和局部搜索的改进文化基因算法比单纯的NSGA-II算法获得的有效前沿性能更优。（3）所提初始种群构建策略和改进文化基因算法对不同组合干扰事件和不同问题规模具有普遍适用性。

本研究在理论上进一步完善和丰富了考虑安装时间和次序相关的置换流水车间环境下的干扰管理研究，而在实践上有助于为生产加工企业在面临较为复杂的组合干扰事件时，提供有效且多样化的重调度方案，指导生产实践。未来进一步的研究方向可聚焦于以下两方面，在问题方面，所构建的组合干扰管理模型应能够涵盖更多干扰事件；尤其是加工时间不确定此类在初始调度制定过程中就需要考虑的干扰事件。在求解算法方面，可以尝试在文化基因算法全局搜索部分应用其它多目标算法；也可以提出新的多目标智能优化算法进行求解，并尝试从算法实践中提炼挖掘对管理者有益的潜在管理启示。

[1] 王建军,刘亚净,刘锋,等.考虑行为主体的置换流水车间干扰管理研究[J].系统工程理论与实践,2015,35(12):3092-3106.

Wang J J, Liu Y J, Liu F,. Disruption management considering real-word behavioral participators in permutation flowshop [J]. Systems Engineering-Theory & Practice, 2015,35(12):3092-3106.

[2] 徐建有,董乃群,顾树生.带有顺序相关调整时间的多目标流水车间调度问题[J].计算机集成制造系统,2013,19(12):3170-3176.

Xu J Y, Dong N Q, Gu S S. Multi-objective permutation flowshop scheduling with sequence-dependent setup times[J]. Computer Integrated Manufacturing Systems, 2013, 19(12):3170-3176

[3] 刘乐, 周泓. 一种常见干扰条件下的开放式车间重调度研究[J].管理科学学报, 2014,17(6): 28-48.

Liu L, Zhou H. Open shop rescheduling under a common disruptive condition[J]. Journal of Management Sciences in China, 2014, 17(6): 28-48.

[4] 李铁克,肖拥军,王柏琳. 基于局部性修复的HFS机器故障重调度[J]. 管理工程学报,2010,24(3):45-49.

Li T K, Xiao Y J, Wang B L. HFS rescheduling under machine failures based on local repair[J]. Journal of Management in Engineering, 2010, 24(3):45-49.

[5] Wang K, Choi S H. A decomposition-based approach to flexible flow shop scheduling under machine breakdown[J]. International Journal of Production Research, 2012, 50(1): 215-234.

[6] Wang K, Huang Y, Qin H. A fuzzy logic-based hybrid estimation of distribution algorithm for distributed permutation flowshop scheduling problems under machine breakdown[J]. Journal of the Operational Research Society, 2016, 67(1): 68-82.

[7] Weng W, Wei X, Fujimura S. Dynamic routing strategies for JIT production in hybrid flow shops[J]. Computers & Operations Research, 2012, 39(12):3316-3324.

[8] Rabiee M, Zandieh M, Jafarian A. Scheduling of a no-wait two-machine flow shop with sequence-dependent setup times and probable rework using robust meta-heuristics[J]. International Journal of Production Research, 2012, 50(24): 7428-7446.

[9] Hu Yanhai, Yan Junqi, Ye Feifan,. Flow shop rescheduling problem under rush orders[J]. Journal of Zhejiang University Science A, 2005, 6(10): 1040-1046.

[10] Katragjini K, Vallada E, Ruiz R. Flow shop rescheduling under different types of disruption [J]. International Journal of Production Research, 2013, 51(3):780-797.

[11] 王旭坪, 阮俊虎, 张凯,等. 有模糊时间窗的车辆调度组合干扰管理研究[J].管理科学学报, 2011, 14(6):2-15.

Wang X P, Ruan J H, Zhang K,. Study on combinational disruption management for vehicle routing problem with fuzzy time windows [J]. Journal of Management Sciences in China, 2011, 14(6):2-15.

[12] Li J, Pan Q, Mao K. A discrete teaching-learning-based optimisation algorithm for realistic flowshop rescheduling problems [J]. Engineering Applications of Artificial Intelligence, 2015, 37:279-292.

[13] Rahmani D, Heydari M. Robust and stable flow shop scheduling with unexpected arrivals of new jobs and uncertain processing times [J]. Journal of Manufacturing Systems, 2014, 33(1):84-92.

[14] 刘锋,王建军,饶卫振,等.安装时间与次序相关的生产调度干扰管理研究[J].中国管理科学,2014, 22(1):45-54.

Liu F, Wang J J, Rao W Z,. Machine scheduling disruption management with sequence dependent setup times [J].Chinese Journal of Management Science, 2014, 22(1):45-54.

[15] Gholami M, Zandieh M, Alem-Tabriz A. Scheduling hybrid flow shop with sequence-dependent setup times and machines with random breakdowns[J]. The International Journal of Advanced Manufacturing Technology, 2009, 42(1-2): 189-201.

[16] Zandieh M, Gholami M. An immune algorithm for scheduling a hybrid flow shop with sequence-dependent setup times and machines with random breakdowns[J]. International Journal of Production Research, 2009, 47(24): 6999-7027.

[17] Kianfar K, Fatemi Ghomi S M T, Oroojlooy Jadid A. Study of stochastic sequence-dependent flexible flow shop via developing a dispatching rule and a hybrid GA[J]. Engineering Applications of Artificial Intelligence, 2012, 25(3): 494-506.

[18] Mirabi M. A novel hybrid genetic algorithm to solve the sequence-dependent permutation flow-shop scheduling problem [J]. The International Journal of Advanced Manufacturing Technology, 2014, 71(1-4): 429-437.

[19] Pan Q K, Wang L, Li J Q,. A novel discrete artificial bee colony algorithm for the hybrid flowshop scheduling problem with makespan minimisation[J]. Omega, 2014, 45:42-56.

[20] 王凌, 吴昊, 唐芳, 等. 混合量子遗传算法及其性能分析[J]. 控制与决策, 2005, 20(2): 156-160.

Wang L, Wu H, Tang F,. Hybrid quantum genetic algorithms and performance analysis[J]. Control and Decision, 2005, 20(2):156-160.

[21] Ishibuchi H, Yoshida T, Murata T. Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling [J]. IEEE Transactions on Evolutionary Computation, 2003, 7(2): 204-223.

[22] Pan Q, Wang L, Sang H,. A high performing memetic algorithm for the flowshop scheduling problem with blocking [J]. IEEE Transactions on Automation Science and Engineering, 2013, 10(3): 741-756.

[23] Anand S, Maria B, Chris N. An iterated local search heuristic for the single machine total weighted tardiness scheduling problem with sequence-dependent setup times[J]. International Journal of Production Research, 2014, 52(9): 2729-2742.

[24] Robič T, Filipič B. DEMO: Differential evolution for multiobjective optimization[C]. Evolutionary multi-criterion optimization. Springer Berlin Heidelberg, 2005: 520-533.

[25] Qian B, Wang L, Huang D,. Scheduling multi-objective job shops using a memetic algorithm based on differential evolution[J]. The International Journal of Advanced Manufacturing Technology, 2008, 35(9-10): 1014-1027.

[26] Li B, Wang L. A hybrid quantum-inspired genetic algorithm for multiobjective flow shop scheduling[J].IEEE Transactions on Systems, Man and Cybernetics, Part B: (Cybernetics), 2007, 37(3): 576-591.

[27] Bhuvana J, Aravindan C. Memetic algorithm with preferential local search using adaptive weights for multi-objective optimization problems[J]. Soft Computing, 2016, 20(4): 1365-1388.

Combinational disruption management in permutation flow shops with sequence-dependent setup times

WANG Jianjun, HOU Xiaowen, LIU Xiaopan, MIAO Hongru

(School of Economics and Management, Dalian University of Technology, Dalian 116023, China)

The flow shop scheduling problem, as one that can be widely abstracted in the actual production and processing environment, is common in manufacturing and service areas such as metallurgy, food processing, and surgical scheduling. Although relatively rich theoretical research results have been achieved, most of these developed solutions are difficult to apply to production practices. A key issue is that most flow shop scheduling research to date ignores the impact of various disruption events in the actual production process. As such, the problem of flow shop disruption management has gradually attracted widespread attention. In recent years, some researchers have begun to consider approaching their analysis from the point of a single disruption event in a flow shop environment. However, in most practical situations, multiple disruption events occur in combination. The processing of such situations is more complicated than for those involving a single disruption event, and in this case, may have a greater impact on the current scheduling scheme. Some researchers have put forward combinational disruption management as a very important research focus and have started to carry out corresponding analysis. However, relative to the number of studies that do not take disruption events into consideration, the body of scheduling research with a focus on combinational disruption events is inadequate. In addition, most of the existing research on disruption management in permutation flow shops assumes that setup time is negligible, or otherwise factored into the processing time. Where the setup time is relatable to the setup sequence, it will have an impact on the scheduling results that cannot be ignored. Finally, most of the existing body of disruption management research tackles single-objective problems, or converts multi-objective problems to single-objective ones through a linear weighted method, while neglecting the impact of the trade-off between the initial objective and the disruption objective in the disruption management problem.

In light of the various deficiencies within the existing body of research, this paper studies six types of common disruption events: random machine failure, processing time variation, setup time variation, job priority update, new job arrival, and job cancellation, in a permutation flow shop environment where setup time and sequence are relevant factors. Disruption management problems are framed as a consequence of either partially or fully combinational events. In order to meet the preferences of different decision makers, in reference to the existing literature on the treatment of various disruption events, we are committed to simultaneously minimizing the initial objective (make span) and the disruption objective (sequence deviation) to better performance and obtain a Pareto optimal solution.

After analysis, this problem appeared to be difficult to solve. However, we proposed an improved memetic algorithm to solve it. Based on our memetic algorithm, we implemented an initial population construction strategy. First, the optimal population under two single objectives is obtained by minimizing the initial objective and the disruption objective by sorting using a non-dominant sorting method, and then selecting the individuals who reign superior after the non-dominant ones are selected out. Second, the remaining initial population is supplemented with randomly generated individuals to construct a final initial population. For some key elements of local search (such as the selection of objective individuals or the criteria for receiving new individuals), the characteristics of the problem and the algorithm are further analyzed to determine the appropriate processing method that will allow the algorithm to better meet the problem-solving requirements. Finally, the concept of "local search efficiency", defined as the ratio of the number of receiving individuals to the number of searching individuals, is introduced and used to balance the allocation of computing resources between global search and local search. By adjusting the search period and search probability of the local search at different stages through local search efficiency, the diversity and practical effectiveness of the Pareto solution can be significantly improved.

We referenced the existing five effectiveness comparison indicators, and designed numerical experiments for different combinational disruption events, to test the effectiveness of the proposed initial population construction strategy and improved memetic algorithm. To facilitate a more effective comparison, this paper improved the memetic and NSGA-II algorithms, and combined them with the random initial population and initial population construction strategies to obtain four hybrid conditions: “memetic algorithm + initial population construction", "NSGA-II algorithm + initial population construction", "memetic algorithm + random initial population", " NSGA-II algorithm + random initial population". Through numerical experiments, we found that, given the same initial population, the improved memetic algorithm proposed in this paper provided a better Pareto frontier; and, given the same algorithm, the initial population construction strategy proposed in this paper significantly improved the performance of the algorithm, thus demonstrating its advantages. This study further improves and theoretically enriches the body of research on combinational disruption management in a permutation flow shop environment where setup time and sequence are relevant factors, and in practice, can help facilitate effective production and the implementation of rescheduling programs to guide production practices, at times when enterprises may face combinational disruption events.

Disruption management; Combinational disruption; Setup times; Memetic algorithm; Pareto front

2018-01-25

2018-05-08

Supported by the National Natural Science Foundation of China (71672019, 71271039, 71421001) and the Program for New Century Excellent Talents in University（NCET-13-0082）

C939

A

1004-6062(2020)04-0144-010

10.13587/j.cnki.jieem.2020.04.016

2018-01-25

2018-05-08

国家自然科学基金资助项目（71672019、71271039、71421001）；教育部新世纪优秀人才支持计划资助项目（NCET-13-0082）

王建军（1977—），男，河北保定市人，大连理工大学经济管理学院教授，博士生导师，研究方向：服务管理、运作管理等。

中文编辑：杜 健；英文编辑：Boping Yan