考虑预防性维护的分布式柔性作业车间调度问题研究

郑景文 付亚平

摘  要：随着全球制造业的快速发展，物流企业竞争加剧，生产制造缺乏有效协同，企业急需更加高效的生产运作模式。分布式制造可以将位于不同地点的原材料、机器设备、操作人员等资源进行有效地整合协同并充分利用。此外，设备维护是企业运营管理的核心内容，直接关系到企业的生产成本、质量与交货期。基于以上背景，文章提出了考虑机器预防性维护的分布式柔性作业车间调度问题，建立了目标为最小化最大完工时间的数学模型，提出了协同进化算法对问题进行求解。通过与两种经典的元启发式算法进行对比实验，结果表明所提出的算法能较好地求解所研究的问题。

关键词：分布式柔性作业车间;预防性维护;协同进化算法

中图分类号：F403.3文献标志码：ADOI：10.13714/j.cnki.1002-3100.2024.11.004

Abstract： With the rapid development of the global manufacturing industry， the competition of logistics enterprises has intensified， and the production and manufacturing lack of effective coordination， and enterprises are in urgent need of more efficient production and operation mode. Distributed manufacturing can effectively integrate and coordinate raw materials， machinery and equipment， operators and other resources located in different locations and make full use of them. In addition， equipment maintenance is the core content of enterprise operation management， which is directly related to the production cost， quality and delivery time of the enterprise. Based on the above background， this paper proposes a distributed flexible job shop scheduling problem considering machine preventive maintenance， establishes a mathematical model with the goal of minimizing the maximum completion time， and proposes a coevolutionary algorithm to solve the problem. Compared with two classical meta-heuristic algorithms， the results show that the proposed algorithm can solve the problem well.

Key words： distributed flexible job shop; preventive maintenance; cooperative evolutionary algorithm

0  引  言

随着经济全球化的发展，科技不断进步，物流企业竞争也日益激烈，现代物流管理要想在竞争中脱颖而出，就必须把科技手段转化为企业的生产力，其中，调度问题是急需解决的重要问题。由于市场中产品需求多变，需要企业具备快速响应市场的能力，众多企业纷纷引进柔性制造系统，逐渐具备了柔性制造的能力[1]。基于此背景的分布式柔性作业车间调度问题（Distributed Flexible Job Shop Scheduling Problem， DFJSP）一经提出就成为了研究热点。由于分布式柔性作业车间调度问题本身的复杂性，使得考虑其维护任务时更加困难。为了描述这个问题，本文建立了目标为最小化最大完成时间的数学模型，设计了一种协同进化算法对该模型进行求解。通过对一组测试算例进行仿真实验，并与两种流行的元启发式算法进行比较，实验结果验证了所提方法的有效性。

1  相关研究

目前，分布式车间调度问题备受关注，理论研究的重心转移到将算法与实际问题的结合上[2]。Jiang等[3]提出了考虑节能的分布式作业车间调度问题，通过改进带有分解的多目标进化算法来解决这个问题。为了最小化分布式作业车间调度问题中的完工时间，Xie等[4]设计了人工蜂群算法。方潇珞等[5]建立了设备随机故障下的经济生产批量模型，目的是求得使单位费用期望值最低的最优经济生产批量和检查次数。Ahmadi等[6]提出了进化算法来解决机器故障下的多目标柔性作业车间问题。Park等[7]提出了一种基于遗传规划的超启发式方法来解决机器故障下的动态车间调度问题。Zandieh等[8]提出了改进的帝国主义竞争算法，用于基于条件的柔性作业车间调度问题的维护。

基于上述情况，本文以最小化最大完成时间为目标建立数学模型，针对考虑预防性维护的分布式柔性作业车间调度问题，设计了一种协同进化算法（Cooperative Evolutionary Algorithm， CEA），并与两种经典算法进行比较，通过对一组测试算例进行仿真实验，验证了所提方法的有效性。

2  问题描述及数学模型

本文研究了考虑预防性维护的分布式柔性作业车间的单目标调度问题。该问题涉及三个调度决策：工件分配到工厂;工序分配到机器;工序的排序。同时，在实际的加工过程中，往往会出现由于机器故障导致加工中断的情况，这会使加工完成时间、加工成本、加工能耗增加，导致企业的生产效率降低，进而影响企业的效益。因此，在生产调度的过程中提前考虑机器的维护任务，更加符合企业的实际需要。因此，本文以最小化最大完成时间为目标建立模型，在表1中定义了相关符号。

在该问题中，可行的调度必须满足以下约束条件：（1）所有工件都在零时等待处理;（2）所有机器在零时可用;（3）每台机器一次只能加工一道工序;（4）每道工序一次只能在一台机器上进行加工;（5）禁止机器中断;（6）如果一个工件被分配到一个工厂，那么这个工件的所有工序都在同一个工厂进行加工;（7）预防性维护操作可以在任何时间执行;（8）同一时刻在同一台机器上工件的操作和预维护任务不能同时进行。基于上述描述，建立数学模型如下：

其中：式（1）表示目标是最小化最大完成时间;式（2）表示任意工厂中一台机器上的操作排序;式（3）表示如果一个工件被分配到一个工厂，那么这个工件的所有操作都在同一个工厂进行加工;式（4）表示一个操作只能在一个工厂的一台机器上进行加工;式（5）表示每个工件上各个操作的排序;式（6）表示在加工o之前进行维护任务;式（7）表示所有工件上的操作都要进行，且不能同时进行加工;式（8）表示必须在时间窗口内进行预维护任务;G表示一个极大数。

3  算法的设计与实现

协同进化算法（Cooperative Evolutionary Algorithm， CEA）的基本思想是将一个系统划分为多个子系统，每个子系统独立进化。通过整合子系统形成一个新的系统，以实现整体进化的目标[9]。本文将协同进化算法应用于种群和染色体。由于解的表示涉及三个问题，而这些问题是相互独立的，因此，协同进化方法非常适合解决所研究的问题。

3.1  编码与解码。在所提出的方法中，使用三个向量来表示一个解。这三个向量分别是工厂分配向量FA、机器分配向量MA、工序序列向量OS。工厂分配向量的长度等于工件的数量。工序序列向量和机器分配向量具有相同的长度，并且等于所有工件的工序总数。同时，采用Wang等[10]设计的左移解码方案，将解决方案转解码为一个可行的解。在本文中，使用以下启发式方法动态调度维护任务[11]：在每台机器的时间窗口开始时调度维护任务;在进行工件加工的总时间内进行维护;如果维护任务与工序o不重叠，则分别进行维护和调度操作的任务;维护任务与工序o有时间重叠时，若开始进行维护任务会中断工序操作，则先完成该工序再进行维护任务，若工件的工序会中断维护任务，则在调度工序之前进行维护。

3.2  初始化种群与种群划分。种群的质量对种群智能算法的求解速度和求解能力有很大的影响。因此，本文采用几种策略，通过所研究问题的特点来初始化种群。

对于操作序列向量，在初始种群中，使用两个启发式规则生成两个个体的工序序列，即优先选择余下加工时间最长[12]的工件和优先选择余下工序数最多[12]的工件，其余的随机生成。对于所有工厂分配向量，其中50%是随机产生的，另外50%是通过以下启发式规则生成的：首先，通过生成的工序序列向量获得工件序列，迭代生成工序序列向量;其次，计算每个工件的平均工作量;然后，通过策略将每项工件连续地分配到特定的工厂;最后，根据获得的工件顺序，将每个工件依次分配给最先完成该作业的工厂。对于所有机器分配向量，有50%的部分是随机生成的，其余50%是通过结合最小完成时间启发式规则获得的[12]。

根据编码方法和问题的特点，将工厂分配、机器分配和工序序列三个子问题独立进化，种群P可分为三个子种群，分别是工厂分配种群P，机器分配种群P，工序序列种群P。

3.3  交叉与变异。为了实现更高效的搜索，对子种群P采用了多重工序交叉[13]，其目的是通过使用工序序列来增加种群多样性;对于子种群P，采用均匀交叉[1];对于子种群P，采用随机概率交叉[14]。本文设计了四种变异算子，对于种群P，使用交换和插入方法;种群P使用随机选择方法，随机选择一个工件，并将其工厂更改为另一个工厂;种群P使用随机选择方法，随机选择一种工序，并将其机器更改为所选工厂中另一台可用的机器。其中，交换方法即交换两个随机选择的工序的位置;插入方法即随机选择一个工序并插入到其他位置。当每个子种群发生变异时，需要注意以下方面：所有种群的每个个体都需要进行变异;新个体直接取代父个体;各个种群的变异率相同。

3.4  局部搜索。在生产中，解决方案的加工时间取决于关键路径的长度，在关键路径保持不变的情况下，加工时间无法缩短。为了减少加工总时间，通过在执行本地搜索时打破关键路径，来获得更好的解。因此，设计三种打破关键路径的方法，分别是工序位置变换方法、改变工件所属工厂的方法和改变某一工序的加工机器的方法。此外，设计了一种迭代局部搜索方法[15]来优化最优个体。

3.5  更新种群的方法。为了保证下一段种群具有更高的质量，首先，将当前种群中的最优个体直接保留到下一代种群。其次，下一代种群的其他个体通过交叉、变异和局部搜索方法产生。

3.6  CEA的算法步骤

步骤1：初始化算法参数，即种群大小PS，变异率Pm;

步骤2：使用启发式规则生成初始种群;

步骤3：评估初始种群并确定最佳个体;

步骤4：重复以下步骤，直到满足给定的停止条件;

步骤4.1：交叉。对子种群P进行多重工序交叉;对子种群P进行均匀交叉;对子种群P进行随机概率交叉;

步骤4.2：变异。从区间0，1中生成随机数r，如果r小于p，继续步骤4.1，否则，请转步骤4.3;从区间0，1中获取随机小数r，如果r<0.5，则对子种群P执行交换方法，否则，对子种群P执行插入方法;对子种群P和子种群P执行随机选择方法;

步骤4.3：评估各个种群;

步骤4.4：局部搜索。通过迭代局部搜索方法，寻找找获得新个体的最优解;

步骤4.5：更新种群;

步骤4.6：如果给定条件不满足，返回步骤4.1，否则，执行步骤5;

步骤5：输出最佳个体及其目标值。

算法流程图如图1所示。其中包括各种工厂分配规则、机器分配规则和工序顺序规则;工厂分配向量、机器分配向量和工序序列向量协同优化;打破关键路径，增强局部搜索能力。该算法通过多种搜索策略的协同使用，有望在考虑的问题上取得优异的性能。

4  算例分析

4.1  参数设置及比较算法。为了评估CEA在处理所提问题方面的性能，本文采用关于柔性作业车间的Hurink， Jurisch和thole基准[19]测试问题构建了一组测试实例。此外，选择了两种著名的智能优化算法，即混合遗传算法（Hybrid Genetic Algorithm， HGA）[16]和混合教学优化算法（Hybrid Teaching-Learning-Based Optimization， HTLBO）[17]进行比较。为了公平比较，CEA的参数设置如下：种群规模为30，变异概率为0.20，局部搜索次数为12。HGA的参数设置如下：种群规模为30，变异概率为0.15。HTLBO的参数设置如下：种群规模为50，TS搜索次数为15，适应值评估次数为150n，n表示工件数，将适应值评估次数设置为算法停止准则。

4.2  评价指标。本文选用相对百分比偏差（Relative Percentage Difference， RPD）指标[18]CEA与其比较算法的结果进行比较，RPD指标的计算公式如下：

RPD=  （9）

其中：θ为最佳目标函数值，θ为某算法在第v次复制时的目标函数值。在接下来的实验中，计算20个重复的平均RPDaRPD、最优RPDbRPD和RPD的标准差sRPD，并对实验结果进行分析。

4.3  结果分析。CEA及其对比算法对aRPD、bRPD和sRPD的实验结果如表2所示。从表2中可以发现，几乎在所有情况下，CEA都明显优于HGA和HTLBO。通过比较CEA和HTLBO的sRPD值，我们可以看到HTLBO只有一组数据优于CEA，有一组数据表现相同。对于HGA而言，CEA在所有情况下都优于它。HGA、HTLBO和CEA的平均aRPD值分别为1.027 8、0.370 4和0.024 8，平均bRPD值分别为0.333 0、0.305 4和0.000 0，平均sRPD值分别为0.058 6、0.036 7和0.017 4。三种算法的平均aRPD值、平均bRPD值和平均sRPD值的比较结果也进一步证明了CEA比其比较算法具有更好的性能。

此外，还使用Friedman检验，Nemenyi后续检验和Wilcoxon符号秩检验比较了CEA与比较算法之间的差异[19]。

（1）通过对三种算法的实验结果进行Friedman检验，可以得到p值为0.000 0，说明三种算法的实验结果是有明显差异的，结果如图2所示。

（2）在Friedman检验结果的基础上，进行了Nemenyi后续检验。可以发现CEA和HGA的秩平均值之差为1.75，此值大于临界范围值0.781 3，说明CEA的实验结果是显著优于HGA的实验结果的。此外，CEA和HTLBO的秩平均值之差为1.166 6，此值也大于临界范围值0.781 3，同样说明CEA的实验结果是显著优于HTLBO的实验结果的。

（3）另外，对实验结果进行了Wilcoxon符号秩检验。第一步，对于每个实例，计算两种算法之间的差异。第二步，根据每个指标的差的绝对值对每个实例进行排序。第三步，通过秩值得到两两比较的“R”和“R”值。用“R”表示第一种算法优于第二种算法的秩和，用“R”表示第二种算法优于第一种算法的秩和。p值可以由“R”和“R”值确定。在实验时，第一种算法是CEA，第二种算法是比较算法。两两比较的Wilcoxon符号秩检验结果如表3所示。符号“w”、“w”和“w”分别表示测试实例中的CEA优于、等于和低于其比较算法。

通过分析表3可以发现，与HGA算法相比，在aRPD、bRPD和sRPD的18个测试实例中，CEA在性能方面优于HGA。与HTLBO算法相比，CEA分别在17、17和16个测试实例上获得了更好的结果。通过观察“R”和“R”的值可以发现，对于aRPD、bRPD和sRPD，每次两两比较的“R”值都大于“R”值。此外，CEA与其他两种比较算法两两比较的P值均为0.000 0。

5  总  结

分布式制造系统有助于降低运营成本和提高生产效率，因此它正在逐步取代单一工厂生产流程。为了充分利用分布式柔性作业车间的优势，提高企业竞争优势，分布式柔性作业车间调度方法被用于各个行业。在实际生产过程中，机器不可避免地会出现不可用期。这种情况将给企业带来一定的生产成本和经济损失。因此，基于以上现实需求，本文设计了一种协同进化算法来解决带有预防性维护的分布式柔性作业车间调度问题，选择两种比较算法进行仿真实验，实验结果表明所提出的算法性能更好。本文从理论上设计了考虑问题特点的算法，针对预防性维护问题，丰富了分布式柔性作业车间调度问题的研究内容。帮助企业降低成本、提高生产效率，进一步促进企业效益的提高，有一定的实践意义。从管理学角度分析，考虑预防性维护的分布式柔性作业车间调度问题能够将生产出现的问题提前了解并做好防护，有效调动各个生产装置，消除安全隐患，保证生产安全有序地运行。本文限制了一个工件只能在一个工厂进行加工，不同工厂之间不可转移，然而在企业真实的制造系统中，可能由于环境污染等因素造成某些操作必须在某一工厂进行加工的情形。因此，未来研究可以考虑工件在工厂之间可以转移的情况，建立新的考虑工件转移的问题模型。

参考文献：

[1]  FU Y， WANG H， HUANG M. Integrated scheduling for a distributed manufacturing system： A stochastic multi-objective model[J]. Enterprise Information Systems， 2019，13（4）：557-573.

[2] 郑睿. 制造业的车间调度问题优化算法比较研究[J]. 物流科技，2008（6）：117-119.

[3]  JIANG E D， WANG L， PENG Z P. Solving energy-efficient distributed job shop scheduling via multi-objective evolutionary algorithm with decomposition[J]. Swarm and Evolutionary Computation， 2020，58：100745-100760.

[4]  XIE J， GAO L， PAN Q， et al. An effective multi-objective artificial bee colony algorithm for energy efficient distributed job shop scheduling[J]. Procedia Manufacturing， 2019，39：1194-1203.

[5] 方潇珞，吕文元. 设备随机故障条件下的经济生产批量模型[J]. 物流科技，2015，38（12）：78-83.

[6]  AHMADI E， ZANDIEH M， FARROKH M， et al. A multi objective optimization approach for flexible job shop scheduling problem under random machine breakdown by evolutionary algorithms[J]. Computers & Operations Research， 2016，73：56-66.

[7]  PARK J， MEI Y， NGUYEN S， et al. Investigating the generality of genetic programming based hyper-heuristic approach to dynamic job shop scheduling with machine breakdown[C] // Australasian Conference on Artificial Life and Computational Intelligence. Springer， Cham， 2017.

[8]  ZANDIEH M， KHATAMI A R， RAHMATI S. Flexible job shop scheduling under condition-based maintenance： Improved version of imperialist competitive algorithm[J]. Applied Soft Computing， 2017，58：449-464.

[9]  LEI D. Co-evolutionary genetic algorithm for fuzzy flexible job shop scheduling[J]. Applied Soft Computing Journal， 2012，12（8）：2237-2245.

[10]  WANG L， ZHOU G， XU Y， et al. An effective artificial bee colony algorithm for the flexible job-shop scheduling problem[J]. International Journal of Advanced Manufacturing Technology， 2012，60（1-4）：303-315.

[11]  JQLA B， QKPA B， MFT C. A discrete artificial bee colony algorithm for the multi-objective flexible job-shop scheduling problem with maintenance activities[J]. Applied Mathematical Modelling， 2014，38（3）：1111-1132.

[12]  KAI Z G， SUGANTHAN P N， TASGETIREN M F， et al. Effective ensembles of heuristics for scheduling flexible job shop problem with new job insertion[J]. Computers & Industrial Engineering， 2015，90：107-117.

[13]  LU C， GAO L， GONG W， et al. Sustainable scheduling of distributed permutation flow-shop with non-identical factory using a knowledge-based multi-objective memetic optimization algorithm[J]. Swarm and Evolutionary Computation， 2021，60：100803.

[14]  GONG G， CHIONG R， DENG Q， et al. A hybrid artificial bee colony algorithm for flexible job shop scheduling with worker flexibility[J]. International Journal of Production Research， 2019，58（14）：1-15.

[15]  HOU Y， FU Y， GAO K， et al. Modelling and optimization of integrated distributed flow shop scheduling and distribution problems with time windows[J]. Expert Systems with Application， 2022，187：115827.

[16]  CHENG R， GEN M， TSUJIMURA Y. A tutorial survey of job-shop scheduling problems using genetic algorithms： Part II. Hybrid genetic search strategies[J]. Computers & Industrial Engineering， 1999，37（1-2）：51-55.

[17]  DING Y， ZHANG Q， LEI D. A novel hybrid teaching learning based optimization algorithm for function optimization[C]

// 2017 Chinese Automation Congress （CAC）. IEEE， 2017：4383-4388.

[18]  HURINK J， JURISCH B， THOLE M. Tabu search for the job-shop scheduling problem with multi-purpose machines[J]. Operations-Research-Spektrum， 1994，15（4）：205-215.

[19]  DERRAC J， GARC?A S， MOLINA D， et al. A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms[J]. Swarm and Evolutionary Computation， 2011，1（1）：3-18.

收稿日期：2023-06-12

作者简介：郑景文（1996—），女，山西侯马人，青岛大学商学院硕士研究生，研究方向：工业工程与管理;付亚平（1985—），男，山东平度人，青岛大学商学院，教授，博士，研究方向：复杂系统计划与调度、多目标优化。

引文格式：郑景文，付亚平. 考虑预防性维护的分布式柔性作业车间调度问题研究[J]. 物流科技，2024，47（11）：19-23.