基于多层编码优化算法的汽车生产物流调度

郭 跃，卫 丹，郑晨樱

（1.宁波工程学院，浙江 宁波 315211；2.长安大学，陕西 西安 710064）

1 引言

中国物流与采购联合会发布的《中国汽车物流发展报告(2018)》[1]展现了中国对汽车生产物流行业的重视。汽车生产物流行业的核心问题是物流调度的问题，为提高汽车制造企业的核心竞争力，企业必须充分利用资源，并设置合理的生产调度以确保交付时间、降低生产成本、提高设备利用率。所以，良好的生产物流调度系统是提高生产效率、增加经济效益的一个重要构成要素，有效的物流调度优化算法可以减少商业周转时间、提高产量、降低库存，达到最低生产成本的目的。因此调度优化算法是否有效，对于汽车生产企业有着重要影响，故该研究具有重要的现实意义。

2 国内外研究现状

目前对于汽车制造业的研究，学术界已有较为详尽的论述，对于汽车生产的物流调度以及关于各种路径优化算法的研究，近年来也有许多学者从不同的角度进行探讨和实证研究，主要观点如下：

2.1 汽车制造业与生产物流之间的联系

全球汽车制造业经过不断的革新和发展，目前已经进入成熟期，成为世界上规模最大的产业之一。由于汽车制造业的产业链长、覆盖面广、综合性强、技术要求高、附加值高，在全球主要工业国家的产业结构中占据重要地位。

Gabriela Slusariuc[2]认为汽车行业现在是世界上最大的加工生产行业。汽车工业不仅是能源和原材料的巨大消费国，也是一个巨大的就业来源。Dario Dunkovic和Goran Jukic[3]在分析现代生产物流变化的起源时，考虑到这些变化是由供应链末端的业务供应商关系模式的发展所造成的，为了缩短交货期，预计生产商越来越多地根据市场需求调整生产动态和产能。周维[4]提出在汽车制造业企业各项生产要素成本逐年上涨、竞争环境压力增大、资源配置有限等众多因素的影响下，汽车制造企业所面临的挑战不断增加，因此汽车制造业转型和升级并进一步提升企业的核心竞争力变成了一项艰巨而紧迫的任务。

汽车制造业经历了单件生产、大量生产、精益生产和模块化生产的发展过程。20 世纪90 年代，随着汽车制造业模块化时代的到来，加强汽车生产物流成为增强企业核心竞争力的关键因素。通过对汽车制造业的现状分析，可以看到生产制造与物流系统的关系如同人体中血液循环系统与内脏器官的关系一样，物流系统是生产制造各环节组成有机整体的纽带，又是生产过程维持有序发展的基础。现代制造企业的生产物流具体是指工厂中从支持生产活动所需要的原材料进厂管理开始，经存储、装配、加工、包装，直至成品出厂这一整个过程的物料流动及与之有关的管理活动，生产物流担负运输、储存、装卸物流等任务。由于传统的生产物流设备落后，物流信息管理分散、不准确、传送速度慢，落后的生产物流将会牵制生产的高速发展。生产制造系统规模不断扩大、生产的柔性化水平和自动化水平日益提高，要求生产物流也要相应地发展，使之与现代生产制造系统相适应。

近年来国内学者对生产物流也有了大量的研究。龚波[5]把Petri网和计算机仿真技术结合起来，论证了计算机仿真和Petri网技术在生产物流研究中的可行性和优势，研究了联合使用Petri 网和计算机仿真，对企业生产物流系统进行优化的方法。岳卫宏[6]运用粒子群算法，探讨了某造船企业分段生产过程中的资源合理配置问题，以平面分段流水线为例，利用SIMIO仿真工具，对平面分段的生产流程进行仿真，认为将先进的生产管理模式引入造船企业的生产物流管理，可实现流程的优化和资源的合理配置。朱华炳[7]采用基本Petri网对制造物流系统各个子系统进行建模，提出了面向对象的着色赋时Petri网(OCTPN)的物流系统建模方法，同时对制造加工及物流系统进行集成建模,建立了包含制造加工系统和物流系统的层次化模型，并就汽车后桥车间物流系统规划的实例基于OCTPN方法进行建模和分析，采用E-Factory、Witness软件进行计算机辅助建模和仿真，对汽车后桥车间生产物流系统进行了设计与优化。

2.2 汽车生产物流算法问题的研究

结合算法对物流调度进行优化的研究在国内外已有建树。Sakawa等[8]从个体间相似度着手，完成了一种算法，将模糊生产周期和出货时间进行多目标调度。华山[9]在研究AGENT－生产调度系统时，结合蚂蚁算法对JSSP问题进行了仿真优化。吴卫忠等[10]利用多目标优化法求解多目标混合流水车间调度问题。Lei等[11]利用粒子群优化算法求解作业车间调度问题，并将调度问题有效转化为连续优化的策略，提出帕累托存档PSO 优化算法。Ju 等[12]提出建立多目标优化调度模型，批量生产优化调度策略，将多种PSO 搜索的优点、遗传算法的优点进行整合，得出自旋性PSO 搜索的多种群混合算法，达到高效率和高质量的目的。潘胜[13]基于准时化模式的生产理念，研究考虑机器准备时间的两阶段生产流水线物流的工件最佳排序问题，以最小化最大拖期和提前期为目标函数，提出了一种变邻域遗传搜索算法。

有许多学者对生产物流遗传算法进行了更加深入的研究。Falkenauer和Bouffouix[14]结合遗传算法进行编码，编码时还使用了交叉算子，利用函数法对物流配送大、中、小型生产物流调度优化模型进行分析，得到最优调度。Jain和Eimaraghy[15]在研究灵活性制造系统中应用了遗传算法，并得到了较好的生产物流调度优化结果。Esquivel[16]等在流水车间和单元制造系统中使用遗传算法解决调度问题，实现了最高效率完工的目的。王成尧[17]等在研究E/T 调度问题时，应用模糊生产时间法、遗传算法，指出遗传算子与调度优化结果的最优性相关联。王凌[18]等在研究混沌优化法时结合遗传算法，使得混沌优化法有了进一步的改进。林博[19]在遗传算法的基础上,提出了改进遗传算法,主要针对选择和交叉两个部分进行了改进，并通过一个物流配送车辆路径问题的实例，用改进遗传算法求解,进行MATLAB 编程仿真，得到了较为理想的效果。支姝[20]采用自然数编码的方法，初始群体的生成采用混合方式，即部分随机生成、部分根据初始解生成，选择策略采用轮盘赌选择法和截断选择法相结合的方法,用改进的边重组法代替常用的PMX、OX、CX交叉法。根据设定的终止条件，最终取得满意解。最后，通过C++实现了算法，用Solomon 测试数据里C101 中25 个客户集的数据进行验证，并与不同算法所得解进行对比，其求解结果和计算时间都有明显改进。所得结果在基于遗传算法求解城市物流配送车辆路径问题领域和物流系统的开发中具有一定的参考价值。

2.3 文献评述

上述文献主要研究了汽车制造业生产物流的特征与现状以及生产物流与汽车制造业之间存在的紧密联系，提出传统汽车制造业的转型与升级已经迫在眉睫，应重视发展汽车制造业生产物流，使之与现代生产制造系统相适应的观点。对于汽车生产物流算法的研究，主要介绍了国内外运用算法改进物流调度的研究，但发现对于使用算法改进汽车制造业物流调度的实证研究还比较缺乏，有必要紧密结合我国汽车制造业特点并运用算法加强物流调度的实证研究，通过算法优化解决汽车生产物流调度中存在的一些问题。而本文所提出的多层编码优化算法便是基于遗传算法，在遗传算法的基础上进行创新和改进。多层编码优化算法的数学模型采用遗传算法进行计算并在遗传算法的基础上运用了双层编码方法设计了一种交叉方法，改进了遗传算法的执行流程，有一定的创新性。

3 数学建模

3.1 汽车制造业生产物流特点

随着汽车制造业的信息化程度加深，汽车制造工厂自动化物流不断创新。汽车制造业生产物流作为汽车制造的关键环节，对其成本控制和效益提高不可忽视。一般的汽车制造工厂均包括仓储、短驳、拣货、上线等操作。根据文献[21-22]，可以得出汽车制造业生产物流的定义：汽车制造业生产物流就是把要增值的金属原材料以最短的时间、最小的成本完成从供应端到需求端的实体流动过程。

汽车生产物流过程中，存在零部件供应商、入厂检验、仓库和生产车间三个重要环境。零部件由零部件供应商整装发运送到整车厂，在入厂检查处进行卸货，并对零部件的数量、质量以及批次和收货单进行核对，核对无误后运到仓库进行存储。仓库根据先到期先出库的原则，将收到的零部件送到适当的库位上[23]。同时，将生产现场的空箱装车后运回零部件供应商，从而形成了一个闭环，整个过程如图1所示。这一环节的主要任务是如何在工作流畅的前提下降低成本。

图1 汽车生产物流过程

汽车生产物流与其他生产物流相同，也与整个企业生产过程紧密相连。只有合理的组织生产物流活动才能够发挥出最大的生产能力，否则再好的生产设备也不能顺利的完成生产。汽车制造企业的生产活动主要是以装配式生产为主，但其不同于其他类型企业的生产模式，其生产过程装配流程长且工序繁多，故其生产物流有以下基本要求：

（1）连续性。汽车制造企业的生产连续进行，每道工序都按照生产工艺提前安排好，需要实现零部件在恰当的时间出现在恰当的地点，不延迟也不提前实现供货。

（2）平衡性。汽车制造企业生产时一般都需要装配半成品，每个半成品都需要多种零部件进行组合。所以在装配生产时，需要将需要的零部件合理分配在对应工序上，因此需要各支流平行移动。

（3）节奏性。汽车生产物流各个流程是一定的，一般工序间不能跳跃进行。保证生产过程的节奏性是指在生产的各个阶段，从零部件出库到成品车入库，要求在相同的时间间隔内，生产大致相同数量的部件或成品。

3.2 数学模型设计

汽车生产物流的调度直接影响汽车生产的进度和订单的响应速度。当客户订单对一些工件需求较为集中时，就会造成生产线的堵塞甚至停工。针对如何合理分配生产设备、提高订单的响应速度，本文设计了根据工序数、耗费时间及需求量提供优化的车间调度决策功能。

车间生产线可以描述为：有n个工作任务需要在m台设备上生产，Oij表示工件i的第j道工序。每个工件的工序一定且已知，工序j在不同机器上加工，加工时间不同。除了操作内容的限制，生产车间生产线的加工过程还应满足以下要求：

（1）一台机器在一个时间点能且只能处理一个任务；

（2）在加工过程中，工件能且只能被一个机器加工；

（3）所有的工作都是同等优先级的；

（4）工序与工序之间转移时间被忽略，仅运算加工时间；

（5）每道工序在不同机器上处理时间已知，且不变。

车间调度优化的任务是合理安排处理顺序，在可行的机器上分配每个操作，以优化给定的目标。本文以每台机器最大工作量最小化、单个工件最大完成时间最小化、总工作量最小化和最大提前或延迟时间最小化为四个目标。数学模型如下：

（1）设f1为工件完成的最大时间，其中Ci为工件i的完成时间，则有：

（2）设f2为机器最大工作量，其中Sij为工件i的第j道工序加工所用时间，则有：

（3）设f3为机器总工作量，则有：

（4）设f4为总延迟时间，其中[tei,tti]为工件i的交货窗口，实际完成时间为Ci，当Ci ＜tei时，表示工件i提前完工，其惩罚值系数为hi；当Ci ＞tei时，表示工件i延期完成，其惩罚系数为wi，则有：

综合上述四项，得出目标函数为：

本文比较当前较为流行的几种算法，发现遗传算法可以快速计算出最优解并可以很大限度的避开局部最优解；可以同时处理多个个体，易于实现并行化；具有自适应、自组织和自我学习的特性，符合本文系统基于智能工厂模式的大前提[24]。结合前面三点，因此本文提出的数学模型采用遗传算法进行计算。

4 研究结果

4.1 编码设计

传统汽车配件生产工件与机器是一一对应的，每道工序都有对应的加工机器，多工件加工时，编码只需要对不同工件之间的加工工序进行编码，不需要对机器进行编码。但随着汽车生产机器的发展，生产设备不仅仅可以生产加工单一工件的某一道工序，传统的仅对工序进行编码已不能满足生产调度的需求[21]。基于智能工厂模式的生产调度编码采用双层编码方式，一层是对不同的工序进行编码，称为操作顺序编码层；另一层对加工机器进行编码，称为机器编码层。

操作顺序编码层是基于偏好加权进行编码，每个染色体代表一个偏好。机器分配层的编码采用整数编码，整数表示机器的编号，每个操作选取的机器编号都是从可选机器编号集合中选取，从而解决机器限制问题。如表1 所示实例，表示的是由4 台机器、3 个工件，每个工件由2-3 各工序组成的生产时间表。

表1 生产加工时间表

（1）基于工序的编码。基于工序的编码是基于偏好加权编码，每个矩阵对应一条染色体，矩阵中的行代表工件，列代表工序，Oij表示工件i的第j道工序，元素Z表示所有待完成工序总数，工件中不存在的工序在矩阵中对应的元素值设为0。对于表1，有矩阵编码E1，矩阵E1表示每个工序的先后，因工件3没有第3道工序，所以E1的第三行第三列为0。

表1中工序的原始矩阵E为：

可以得出基于工序编码的生产顺序为：O11、O21、O31、O32、O12、O13、O22、O23。

（2）基于机器的编码。矩阵E2中行代表工序，列代表机器数。其中行对应基于工序编码的矩阵E1中的生产顺序。将表1中的数据按照此规律排列，其中不能使用的机器矩阵元素设为-1，可得到矩阵E2：

矩阵E3中行代表机器，列代表工序。其中列对应基于工序编码的矩阵E1中的生产顺序。将表1中的数据按照此规律排列，其中不能使用的机器矩阵元素设为0，可得到矩阵E3：

对矩阵E2进行抽象，将选择的机器设为1，其余未选择的设为0，得到矩阵E4：

由第一行可以读出O11由机器2 生产，第二行可以读出O21由机器3 生产...；总的可以看出这八道工序的加工机器分别为：M2、M3、M2、M3、M1、M3、M4、M1。

4.2 解码

（1）基于工序编码的初始解。矩阵元素总数Z为待生产工件的总工序数，其中元素值为0的个数为P，则有非零元素个数Q=Z-P，首先在非零元素的位置上随机放置1 ∼Q 的自然数，再按从小到大的顺序将每行元素排列就会得到初始解，其产生过程如下：

整理可得初始解E5：

（2）基于机器编码的初始解。为了避免加工机器产生冲突，在矩阵进行抽象后要对不同工序间使用的机器是否在时间上存在冲突进行判断。例如第道工序的开始时间为tis，加工时间为ti，在工序i后的第i+j道工序也要使用此机器，就需要判断tis+ti≤t(i+j)是否成立，若成立则第i+j道工序可直接进行，否则将需要等待。

以上文所举的例子，若要计算每道工序的加工时间，则矩阵E4×E3得到的矩阵E6的主对角线的数值即为工序所选加工机器所需加工时间。即第一道工序3.4h，第二道工序3.1h...以此类推。结合每道工序的开始时间可以得出总的加工时间。

4.3 交叉操作

交叉可以看作是遗传算法的主干，它决定了整个算法的质量。为了避免产生不可行的解，我们设计了一种新的交叉方法，它由两部分组成，一部分为基于工序的交叉方法，另一部分为基于机器的交叉方法。

结合上文提出的双编码方法。操作序列层的编码基于偏好权编码方法，每个基因代表一个偏好。可以对一个生产车间由3个工件和4台机器组成，每个工件由3 个工序，两条染色体p1和p2的问题进行见表2的描述。

表2 双层编码例子

在进行偏好交叉时，我们改变了偏好的顺序，每次操作的加工机器没有改变，避免选择不合适的机器，产生不可行的解。在基于工序的交叉方法中，首先选择一个工序作为交叉工序，随机选择两个染色体作为父母。然后，交换交叉工序的所有偏好，并对另一个工序的偏好进行统计分析，找出缺失的和重复的偏好号，用缺失的替换重复的。最后，从小到大重新安排每个工序的偏好。

例如，随机确定两条染色体的第二行为交叉行，交叉后P1会出现重复基因3和5，所以要用2代替第一行的5，8 代替第三行中的3，然后按照偏好大小进行排列，染色体P2给予同样的处理，就可以得到子代C1和C2见表3。

表3 基于工序交叉后的后代

机器交叉时，保持操作工序不变，这里随机选择一个偏好数作为机器的交点，如果偏好数小于交点，且两个父结点有相同的操作，交换加工机器。例如，随机选择偏好6作为机器的交点，操作偏好数要比6小，并且p1和p2的父母都是O11,O21,O31,O32，交换他们的加工机器，得到后代C3和C4，见表4。

表4 基于机器交叉后的后代

4.4 变异操作

为了保持种群的多样性，防止早熟，本文在算法中引入了变异操作。由于采用了双重编码方法，因此采用了两种类型的变异算子，即偏好变异算子和机器变异算子。

（1）突变的偏好。选择一条染色体，交换两个属于不同工序的偏好，然后将每个工序的偏好从小到大重新排列。同时保持每一个操作的处理机器不变。

（2）机器突变。选择一条染色体，随机选择它的一个偏好，然后用一个新的可行的染色体替换它的加工机器。

5 研究结果分析

5.1 汽车制造业生产方式分析

汽车制造企业属于离散型企业，从细分生产模式分以按订单设计、按订单生产（装配）和按库存生产三种模式为主。

其中最普遍的是按库存生产型（BTS）。全球汽车行业普遍存在产能过剩、产销率明显下降的问题。究其原因，一方面，市场趋于成熟，消费者趋于理性；另一方面消费者的要求更加个性化，单一的、大众的商品已经无法满足消费者的需求。传统的面向库存的预测推动的生产方式已经不能适应激烈的全球竞争。传统生产方式将会形成如图2 所示的恶性循环[26]。

图2 BTS模式下的恶性循环

BTS模式基于“准确预测”的假设进行生产，但这个假设并不符合汽车市场的真实情况。当前，汽车制造企业面临不断变化的外部环境，顾客需求越来越细化。在市场全球化、技术更迭加速的背景下，竞争环境更加激烈。“以客户为中心”的企业管理要求企业能够对客户的多元化需求做出快速响应，响应速度很大程度上决定了竞争优势[27]。

随着企业生产车间智能化、数据化转型的加深，生产效益和对订单的反应力由硬件设施转向如何很好的利用硬件设施上。而生产模式的转换不是一蹴而就的，需要逐渐过渡。面向库存的生产模式要想向面向订单的生产模式转换，首先需实现商务与生产合同制，在最小库存下有了生产订单才进行生产、库存系数研究，对安全库存进行调整，逐步实现以客户需求订单拉动生产。

5.2 智能工厂生产物流管理新特性的思考

智能工厂相较于传统的生产工厂已经结合了先进的通信技术、物联网技术和控制技术，实现了生产全过程的信息化、产品全生命周期的智能化、标准化，具有自我信息更迭、优化、分析筛选的性能，传统的生产物流管理已经不能满足其生产需要，因为智能工厂的生产物流应具备以下几点性能：

（1）生产数据的收集。传统的制造业生产设备大都是数控机床，每个生产单元都是孤立的，但经过智能化升级改造后的智能工厂已经实现生产设备的智能化，将智能生产终端嵌入到生产现场中，并且利用物联网技术实现各终端的互联互通、智能感知。传统的制造业生产物流没有对生产数据进行利用，没有感知生产参数，无法帮助智能工厂实现最大生产效益。

（2）物流数据的集成化。生产物流与整个生产过程紧密相连，生产物流数据的集成不仅仅包括现场生产原料的数据和仓库存储的数据，还应该包含生产各环节的物流数据，这样才能真正实现物流的集成，使得物流模块成为各个管理模块的纽带。

（3）生产数据的分析与反馈。智能工厂里的智能设备保证生产物流数据实时有效的更新、获取、集成，还要对数据进行分析、处理，并将分析后的结果反馈给管理人员，使生产过程实现闭环控制，为生产管理者的决策提供参考。

5.3 改进遗传算法执行流程延伸性思考

在针对单目标遗传算法问题时，一般选择最优解，但当涉及到多目标优化时几个目标会出现冲突，很难说哪个更好，所以多目标问题的最优解是一个帕累托最优解集。当处理多目标优化问题时，想要得到帕累托最优解，首先需要先做非支配排序。传统的一种非支配排序方法是在排序时一个解必须与所有解进行比较，该方法要进行大量计算，效率很低。为了快速高效地进行排序，本文设计了一种新的排序方法。

（1）设帕累托等级s=1。

（2）随机选择一个个体。

（3）将这个个体与整个群体进行比较，找出它的所有非支配解，支配解；在q1集中保留非支配解，q3集中保留支配解，q2集中保留其他解。

（4）如果q1不为空，从q1中随机选择一个个体，从第3 步执行；如果q1为空，对于q2中的每一个个体，在q2中寻找它的非支配解，如果在q1中找到这个个体，则将这个个体的帕累托等级设为s，并保持在q0中。

（5）如果q1和q2都为空，从第6 步执行，否则从第4步执行。

（6）s=s+1。

（7）从第2步执行到q1、q2和q3都为空。

6 结论

本文分析了汽车制造业生产物流的特征，得到基于智能工厂模式的汽车制造业生产物流管理系统的需求，并给出生产物流在仓储上如何利用QR二维码实现双向定位；并针对工件需求较为集中时造成生产线堵塞甚至停工的情况给出综合最小的最大完成时间、最小的单个设备工作量、最小总工作量的三个目标的数学模型。基于多目标的优化得到帕累托解集，设计了新的对比流程，可以快速求出最优解。