优化遗传算法求解柔性流水车间调度问题

摘要：为提高生产效率和企业竞争力，需制定合理的调度方案以优化资源分配。文章针对柔性流水车间调度问题，提出一种改进的遗传算法，通过分析柔性流水车间调度问题的特点，对遗传算法进行改进，主要包括两个方面：一是采用新的编码方式，将工序、机器和时间信息融入编码，提高编码效率；二是引入自适应交叉和变异操作，加快算法搜索速度，更快找到优解，实验结果表明，改进后的遗传算法具有良好的性能。

关键词：柔性流水车间调度问题；遗传算法；最优化算法；单目标优化

中图分类号：TP311 文献标识码：A

文章编号：1009-3044（2025）02-0015-04 开放科学（资源服务） 标识码（OSID） ：

0 引言

柔性流水线车间调度问题（Flexible Flow ShopScheduling Problem， 简称FFSP） 作为一种经典的组合优化难题[1]，已被确认属于NP难问题范畴。随着全球市场竞争的白热化，制造业企业正承受着减少成本及提升生产效率的双重压力[2]。因此，探索高效的调度策略对于促进先进制造技术的发展具有深远的理论价值与实际意义[3]。尽管FFSP已受到长期研究，但在构建系统的理论框架和方法论方面尚存空白，理论实践的融合亟待加强。目前，相关研究侧重工件调度层面，而资源分配的深入探讨略显不足，两者的整合研究成为新的趋势。鉴于车间调度问题固有的复杂性[4]，学者们通常采纳启发式算法、搜索算法等高效策略来应对挑战。其中，遗传算法作为一种模拟自然界选择与进化的计算模型，凭借其并发性、随机探索及自我适应等特点，在处理复杂度高、非线性问题时展现出独特优势[5]，尤其在传统算法难以突破的领域内效果显著[6]。有证据表明，在面对作业车间调度难题时，遗传算法相较于经典启发式方法展示出更优越的性能与更广泛的适用性[7]。本研究旨在通过引入遗传算法来优化流水线车间调度方案，核心目标在于实现总完成时间的最优化。

1 柔性流水车间调度问题

1.1 流水车间调度问题

流水车间通常用于批量生产同种或相似的产品，例如汽车制造、电子产品制造等领域。在流水车间调度问题中，加工系统有一组功能不同的机床，待加工的工件包含多道工序[8]。

流水车间调度问题是一种典型的多机器调度问题。在该问题中，需要对工件进行排序和分配，以最小化完成所有作业所需的总时间[9]。工件需要按照特定的顺序流经各个机器进行加工，因此：

1） 每个工件在每台机器上只能运行一次；2） 一台机器在同一时刻仅能处理一个工件；3） 每个工件在某一时刻仅能在一台机器上处理；4） 工件不可被抢占；5） 工件在机器上的处理时间不会随调度序列改变而改变；6） 机器的使用顺序是固定的。

1.3 解决柔性流水车间调度问题的求解方案

常见的启发式算法包括基于遗传算法、模拟退火算法、禁忌搜索算法等的进化算法，以及基于邻域搜索、动态规划等的局部搜索算法[10]。数学模型通常采用线性规划、整数规划、图论等方法进行建模和求解[11]。解决流水车间调度问题可以提高车间的生产效率，减少生产成本，提高产品的质量和产量[12]。因此，在实际生产中，流水车间调度问题具有重要的应用价值。

2 FFSP 问题数学模型

2.1 问题描述

共有i项工件历经生产线的T个加工环节进行处理，这些工件按照某种既定序列S1，S2，…，St 反复接受加工操作。每一单项工件i需在特定环节Hi重复加工，累计需经历Hi×T个工艺步骤方能完成加工流程。在每一个加工环节t，配置有5台并发设备，工件在抵达环节t时可被灵活指派至该环节内的任一可用设备上，其具体加工时长由负责处理该工件的设备性能决定。工件i依据其释放时间进入生产体系，而各加工环节之间的转运时长则依据两环节之间的物理距离来估算。加工期间，所有设备维持持续运作状态，且单台设备每次仅能处理一件工件。调度任务的核心，在于优化每个加工环节内工件至设备的分配策略及同设备上工件的作业排序，旨在实现总体加权完成时间的最小化。

2.2 定义参数和变量

定义参数与变量符号如表1所示。

利用上述符号，将遗传算法建模如下所示。

目标函数：

1） 计算总时间；2） 总工件数量；3） 在此机器上某个工件加工完成所需要的时间；4） 开工时间和完工时间；5） 机器开工时间的总和，其中包含所有工件；6） 机器的开工时间和完工时间之和；7） 计算工件在运输过程以及加工过程时间的总和；8） 工件完工时的总时间；9） 判断某个工件是否在此机器加工过；10） 判断是否有工件没有加工。

2.3 算法流程

算法流程如图1所示。

1）开始：初始化算法。

2）初始化：设置代数GEN=0 。

3）生成初始种群：创建算法的初始种群。

4）检查停止条件：判断是否满足停止条件。

如果满足，进入步骤9。

如果不满足，继续执行。

5）计算适应度：计算种群中每个个体的适应度。

6）初始化计数器：设置计数器i=0。

7） 检查迭代条件：判断i是否等于M（最大迭代次数） 。

如果是，增加代数 GEN=GEN+1，然后返回步骤4。

如果不是，继续执行。

8）选择操作：根据概率选择遗传操作（复制、交叉或变异） 。

复制：选择一个个体，执行复制，生成新种群。

交叉：选择两个个体，执行交叉，生成两个后代，并将后代插入新种群。

变异：选择一个个体，执行变异，插入新种群。

9）更新计数器：增加计数器 i=i+1 ，然后返回步骤7。

10）指定结果：当满足停止条件时，指定最终结果。

11） 结束：算法结束。

2.4 对代码优化的改进

main 函数：这是主要的函数，用于处理单个实例。首先，设置时间单位为1，并根据给定的实例名称获取相应的数据。然后，使用Utils.string2data_jsp_fsp 函数将数据转换为所需格式。接下来，根据转换后的数据创建调度问题，并初始化遗传算法的参数。最后，将遗传算法和问题设置为调度模板GaTemplate 的参数，以进行求解。

exp 函数：这是用于处理所有实例的函数。它通过将INSTANCE_LIST_FSP 字符串拆分成多个实例名称，并依次调用main 函数来处理每个实例。

if __name__ == '__main__'：这是 Python 的入口点。在这里，调用 exp 函数开始执行程序。

通过对代码进行优化，可以使代码更加规范、易读和易维护。将不同的功能封装到函数中，提高了代码的可重用性。同时，通过合理命名变量和函数，使代码更加清晰易懂。

2.5 代码优化解释

1） 引入模块时使用了from src import *语句，这种方式不够明确且容易造成命名冲突。更好的做法是明确导入需要使用的模块或函数，例如 from src im⁃port GaFspHfsp， Crossover， Mutation， Selection， Utils，Objective， Fsp， GaTemplate， fsp_benchmark， INSTANCE_LIST_FSP。

2） 将获取实例数据的代码行a = fsp_benchmark.instance[instance]修改为更具描述性的变量名in⁃stance_data = fsp_benchmark.instance[instance]。

3） 将数据转换的代码行n， m， p， tech， proc = Utils.string2data_jsp_fsp（a， int， time_unit）修改为使用更具描述性的变量名，并将instance_data作为参数传递。

4） 在创建遗传算法对象GA时，将参数设置移到一个单独的行，以提高代码的可读性。

5） 设置遗传算法的交叉操作、变异操作和选择操作时，使用具体的操作类名替代字符串名称，以提高代码的可读性。

6） 将遗传算法的禁忌参数和卸载参数的设置移到单独的行，以提高代码的可读性。

7） 将主函数的判断条件修改为if __name__ == '__main__'：，以确保只有在直接运行脚本时才执行实例处理。

8） 添加注释和解释来描述代码的功能和作用。

2.6 代码优化后结果

1） 删除了用于初始化填充的重复代码，并用使用“pop[0]”和“pop”的更有效的方法替换它。

2） 更改方法“decode”以接受先前作为全局变量传递的附加参数“mac”“route”和“wok”。这使得代码更加模块化，更易于理解。

3） 删除了不必要的“self.record”变量，并将其替换为“self.record[0]”和“self.Records”，以存储每一代的初始和最终时间戳。

4） 将方法“do_crossover”更改为使用“pop[0][i]”对象中的“ga_crossover_sequence_termutation”方法，而不是在类中再次实现它。

5） 将方法“do_mutation”更改为使用“pop[0][i]”对象中的“ga_mutation_sequence_termutation”方法，而不是在类中再次实现它。

6） 将方法“do_tabu_search”更改为使用“pop[0][i]”对象中的“ts_sequence_permutation_based”方法，而不是在类中再次实现它。

3 遗传算法

3.1 遗传算法基本介绍

遗传算法作为一种模拟自然界的优化策略，借鉴了自然选择及遗传学原理[13]。该算法通常采用二进制字符串来编码，这些字符串并不代表直接的解决方案。算法初始化阶段涉及随机生成一组染色体构成原始种群，其中染色体的数量定义了种群的规模或大小[14]。接下来，依据预设的适应度函数，评估种群中各个个体的适宜度，此函数体现了个体适应环境的能力，即解的质量高低。随后，那些展示出较高适应度的个体将得到优选，这一过程映射了自然界中适应性强的生物更易存活繁衍的现象。为了探索种群多样性和规避局部最优陷阱，实施交叉与变异操作至关重要。这些操作后产生的新一代染色体即为子代。在每一代迭代中，子代将取代父代成为新的种群，此循环往复直至预设终止条件达成，最终甄选出最优染色体作为问题的最优化解。

3.2 遗传算法的优势

遗传算法相比已有算法具有一系列优势：1） 全局搜索能力更强。2） 并行处理能力较短的时间找到最优解，提高算法效率。3） 遗传算法的编码方式和解码方式相对灵活。4） 鲁棒性，有一定的容错能力。5） 在解决特定类型FFSP 问题上的效果提升、计算效率提升。

3.3 遗传算法流程

1） 初始化种群：随机生成一个由多个个体组成的种群，每个个体都代表一个可能的解。

2） 评估适应度：计算每个个体的适应度，适应度越高表示该个体越符合优化问题的要求。

3） 选择操作：从种群中选择一些个体，用于繁殖下一代。选择操作基于适应度，通常选择适应度较高的个体。

4） 交叉操作：将选择的个体进行交叉操作，生成新的个体。交叉操作是将两个个体的某些基因组合在一起，生成新的个体。

5） 变异操作：变异操作是将某个个体的某个基因进行随机变换，生成新的个体。

6） 生成下一代：将新生成的个体加入种群中，生成下一代种群。

7） 重复执行选择、交叉、变异操作，直到达到终止条件。

4 实验结果与分析

数据分析如图2所示。

工件7在所有运行中都首先完成，这可能表明它在调度中具有优先级或其处理时间较短。

工件5在大多数情况下都是最后完成的，这可能意味着它在调度中被赋予较低的优先级或其处理时间较长。

运行时间：从7 038秒到7 049秒不等，这表明不同工件完成顺序对总运行时间有影响，但影响不大，因为时间差异较小。

最优顺序：从运行时间来看，第7次运行的顺序（7， 4， 2， 10， 6， 8， 3， 1， 0， 5， 9） 具有最短的运行时间7038秒，这可能是最优的调度顺序，如表2所示。

5 结论

本文以作业车间生产调度为研究对象，提出一种改进的遗传算法，并通过实验验证了其有效性。

本文的主要贡献如下，提出一种改进的遗传算法，设计了相应的遗传算子、适应度函数和编码方式.

本文主要研究了最小化总完工时间的车间调度问题，并采用了一种简单的编码方式。本文所研究车间调度问题主要针对多种工序可以在多台不同机床上加工的情况，在以后的研究中，考虑工艺路线可变的情况，此类问题更复杂，但进一步集成了生产计划与车间调度是一个值得研究的方向。

参考文献：

[1] 陈世佳.改进Hopfield神经网络算法求解柔性流水车间有限缓冲区排产问题[D].沈阳：沈阳建筑大学，2017.

[2] 潘帆，邹泽宇，徐小路.基于双基因遗传算法的多工序变速机调度问题研究[J].现代商贸工业，2011，23（20）：261-263.

[3] 那光宇.车辆生产管理系统的设计与实现[D].长春：长春工业大学，2018.

[4] 张慧贤.带恶化工件的车间调度模型及优化研究[D].郑州：郑州大学，2020.

[5] 佟昕，李大鹏，李宁.遗传算法参数对估算低能耗建筑能量消耗的影响[J].建筑节能，2018，46（1）：108-111.

[6] 王科雷，周洲，许晓平，等.超临界翼型低雷诺数流动分析及优化设计[J].航空学报，2015，36（10）：3275-3283.

[7] 王民生.禁忌搜索算法及其混合策略的应用研究[D].大连：大连交通大学，2005.

[8] 马欣，朱双东，杨斐.旅行商问题（TSP）的一种改进遗传算法[J].计算机仿真，2003，20（4）：36-37.

[9] 轩华，李冰，罗书敏，等.基于总加权完成时间的可重入混合流水车间调度问题[J].控制与决策，2018，33（12）：2218-2226.

[10] 姚远远，叶春明，杨枫.双目标可重入混合流水车间调度问题的离散灰狼优化算法[J]. 运筹与管理，2019，28（8）：190-199.

[11] 李俊青，潘全科，王法涛.求解混合流水线调度问题的离散人工蜂群算法[J].运筹与管理，2015，24（1）：157-163.

[12] 张维存，左天帅，张博涵.考虑有限缓存区的Job Shop加工与搬运集成调度[J].运筹与管理，2020，29（11）：213-222.

[13] 张维存，郑丕谔，吴晓丹.蚁群遗传算法求解能力约束的柔性作业车间调度问题[J].计算机集成制造系统，2007，13（2）：333-337，362.

[14] 曲媛，刘庆阁，唐晓彬，等. 基于改进遗传算法对车间调度问题的研究[J].计算机与数字工程，2020，48（2）：350-355.

【通联编辑：光文玲】

基金项目：甘肃省大学生创新创业训练项目（S202310733046）；甘肃农业大学大学生创新创业训练计划项目（202316015）