大规模硫化车间调度问题研究

章佳媛 张干 梁心语 叶佳林 史彬

摘  要：针对硫化车间生产调度过程中产品型号多、处理量大等难点，建立了以最小硫化时间为目标、多硫化机并行生产调度的混合整数线性规划（MILP）数学模型。采用0—1变量表示不同型号轮胎生产顺序，提出了多种约束以减少模型求解难度。为了验证模型的有效性，对文献中三个典型的小规模硫化调度算例求解，得到了比文献更优的调度方案。在此基础之上，考虑硫化车间生产实际，设计了六个贴近实际的大规模调度算例，进一步考察本文所提出方法的有效性，为实际硫化车间调度优化提供了指导。

关键词：硫化车间调度;大规模;完工时间;MILP

中图分类号：TP319.9     文献标识码：A

文章编号：2096-1472（2022）-01-18-04

Abstract： Aiming at the difficulties in the production scheduling process of the vulcanization workshop， such as multiple product models and large processing capacity， this paper proposes to establish a mixed integer linear programming （MILP） mathematical model for the parallel production scheduling of poly-vulcanizers with the minimum vulcanization time as the goal. Variables from 0 to 1 are used to represent the production sequence of different types of tires; a variety of constraints are proposed to reduce the difficulty of model solving. In order to verify the effectiveness of the model， three typical small-scale vulcanization scheduling examples in the literature are solved， and a better scheduling scheme than the literature is obtained. On this basis， taking the actual production of the vulcanization workshop into consideration， six large-scale scheduling examples close to reality are designed to further examine the effectiveness of the method proposed in this paper. The proposed method provides guidance for the optimization of actual vulcanization workshop scheduling.

Keywords： vulcanization workshop scheduling; large-scale; completion time; MILP

1   引言（Introduction）

在轮胎生产过程中，硫化工序[1]耗时最长，其科学排产是提高轮胎生产率的关键。近年来，国内外轮胎厂生产已经基本实现了自动化，但轮胎硫化排产依然需要依靠调度人员的经验来安排，这种靠基本经验的人工方式很难使机器的利用率达到最大。充分利用有限的硫化机，合理排产，在最短的时间内完成轮胎的生产，是提高企业生产力和竞争力的关键。本文以最小硫化时间为目标，对硫化车间的调度进行优化。

近年来，调度优化问题引起了广泛的关注[2-5]：郑必鸣等人[2]提出了一种基于混合整数线性规划（MILP）的鲁棒优化模型，来优化不确定条件下的生产调度决策;耿佳灿等[3]建立了以最小化模糊最大完工时间的值及不确定度作为调度目标的数学模型，使用基于改进粒子群和分布估计的混合算法求解该调度问题;HE等人[4]建立混合整数线性规划模型求解并行设備的调度优化问题;李作成等人[5]使用遗传分布估计算法求解化工生产中的并行机调度问题。

硫化车间调度优化问题是一种典型的调度优化问题，近年来不少学者都对此做过研究[6-8]：张守刚等人[6]使用分布估算算法对硫化车间调度问题进行求解，结果显示该算法可以较好地求解小规模硫化车间调度算例;吴龙成等人[7]采用改进和声算法对该类调度问题进行求解，经过改进的和声优化算法有较好的求解性能，能较快地求解小规模调度算例，并且每次运行程序得到的最优解在小范围内波动;王辉等人[8]使用改进粒子群算法对该类调度问题进行求解，结果显示该算法在求解过程中可以较好地避免过早陷入局部最优解。上述求解方法为小规模硫化车间调度问题的求解提供了思路。由于实际硫化车间调度问题规模较大，因此本文建立包含0—1变量的混合整数线性规划数学模型[9-10]，将生产顺序用多组线性约束表示，使用GAMS求解相关算例，得到了较为满意的结果。

2  硫化车间调度问题建模（Modeling of vulcanization workshop scheduling problem）

2.1   问题描述

轮胎厂的硫化车间共有台硫化机，共需生产种规格的轮胎，订单中每种规格轮胎的需求数为（=1，2，3，…，）。

每台硫化机可以硫化订单中所有规格的轮胎，由于各台硫化机的硫化能力不同，其硫化不同种类轮胎的时间也不尽相同。每台硫化机上每次仅可硫化一条轮胎，并且同一条轮胎只能在一台硫化机上硫化。同一台硫化机硫化不同种类的轮胎需要进行换模，换模时间取决于硫化机的性能以及轮胎模具的型号和更换顺序，每台硫化机上最初生产的轮胎不需要更换模具。由于硫化车间的生产是多台机器同时运行，因此硫化车间的调度问题是一个多机器并行生产的调度问题[11-12]，如图1所示。

已知每种规格轮胎的需求数量，不同硫化机上硫化不同轮胎的时间和不同硫化机上各种轮胎之间的换模时间，第台硫化机上轮胎是否紧接着轮胎生产，第台硫化机上生产轮胎的数量，硫化机上总硫化时间，调度优化目标为最大完工时间最小化，可用式（1）和式（2）表示：

式（1）为每台硫化机硫化时间，式（2）中为总生产时间，即所有硫化机中硫化时间最长的硫化机耗时。

2.2   约束条件

根据确定的调度优化目标，结合轮胎硫化实际情况，需要考虑如下约束条件。

（1）轮胎生产种类与换模约束

其中，代表轮胎种类，表示硫化机，表示第台硫化机上是否生产轮胎，为0—1变量。式（3）—式（5）表示轮胎换模种类与换模次数之间的关系，在同一台硫化机上换模次数不大于硫化轮胎种类数，并且硫化轮胎种类数之和比换模次数恒少1。

（2）生产顺序约束

在式（6）—式（9）中，为在第 台硫化机上第一个生产的轮胎是否为，为在第台硫化机上最后一个生产的轮胎是否为，与均为0—1变量。式（6）和式（7）表示硫化的每种轮胎最多只能有一个前相邻生产轮胎和后相邻生产轮胎。式（8）和式（9）表示每台硫化机中有且仅有一种最初和最后生产的轮胎。

式（10）表示了同一台硫化机上初始生产轮胎、最后生产轮胎和轮胎换模之间的内在联系。假设在第台硫化机上的硫化顺序为1—2—3—4—5，则的取值均为1。除了最初生产的轮胎1与最后生产的轮胎5，其他轮胎均出现了两次（例如轮胎2在和中各出现了一次，和取值均为1）。约束9中引入最初生产轮胎和最后生产轮胎，使轮胎1和轮胎5共出现两次（和取值为1，和取值为1），然后建立轮胎生产顺序约束。

式（11）表示如果在某台硫化机上轮胎是紧接着轮胎生产的，那么轮胎的初始加工時间一定大于轮胎的完工时间。其中为轮胎在硫化机上的初始生产时间，B为一个足够大的数。

（3）生产数量约束

在式（12）中，为订单中需求量最大轮胎的需求数。该约束将0—1变量与整数变量通过线性不等式进行联系，当取1时，此时取值不受该约束限制;当取0时，此时只可以取0。

在式（13）中，为硫化机订单中各种轮胎所需硫化的数量，该式表示所有硫化机生产该种型号轮胎的总数需要满足订单需求。

3  计算结果对比与分析（Comparison and analysis of calculation results）

3.1   文献算例对比

根据文献[6]和文献[7]提供的算例，实验以最小化最大完工时间为调度的优化目标，算例规模分别是3×4（3 台硫化机硫化4 种型号轮胎）、4×3和7×10。下列计算结果采用本文所建立的数学模型，在GAMS平台使用CPLEX的MIP求解器进行计算求解[13-15]，硬件配置为内存12 GB、处理器i7-4710HQ，与相关文献对比结果如表1所示，排产顺序如图2—图4所示。

在图2、图3和图4中，柱状图中的数字代表在该时间段内硫化轮胎的型号，每一条柱状图下方的数字表示硫化该型号轮胎的数量，柱状图与柱状图之间的空缺代表硫化机进行了换模。

通过表1的结果对比可以看出，在求解同样规模的硫化车间调度问题上，本文求解结果均好于文献中多次使用智能优化算法求得的最好结果。求解上述三种规模硫化车间调度问题时，求解时间均在1 s左右。

3.2   大规模调度优化算例

为了验证本文所提出模型求解实际硫化车间生产问题的有效性，共设计六个算例，不固定换模时间为200—300 min，固定换模时间为210 min。任意硫化一条轮胎的时间均是18—50 min的随机数，每种型号的轮胎需求数量均为400—1000 条，详情如表2、表3所示。从求解结果中不难发现，随着算例规模的增大，变量数与不等式个数也随之呈指数型增长，求解时间也随之增长，但是即使求解100×100的大规模硫化调度问题，求解时间也仅在20 min内。表2与表3中最大完工时差为每个算例的调度方案下耗时最长硫化机台与耗时最短硫化机台的完工时差，从中不难发现，相较于总完工时间，最大完工时差均在0.03%以内，说明硫化机都得到了合理的安排。

4   结论（Conclusion）

本文根据硫化车间的调度问题，以最小硫化时间为目标，使用13 个约束组，并添加了启发式约束，建立了MILP数学模型。为了验证模型的准确性，使用该模型在GAMS平台上求解相关典型文献算例，每个典型算例求解时间在1 s左右，得到的调度方案相较于相关文献均较为满意。且为了进一步验证该模型的有效性，本文设计了六个大规模调度算例，并使用该数学模型进行求解，求解结果均显示硫化机利用率较高，为实际硫化车间的排产提供了一定的指导。

参考文献（References）

[1] 刘明举.硫化车间的系统化管理[J].轮胎工业，2017，37（10）：625-629.

[2] 郑必鸣，史彬，鄢烈祥.多因素不确定条件下的间歇生产调度优化[J].化工学报，2020，71（03）：1246-1253.

[3] 耿佳灿，顾幸生.不确定条件下中间存储时间有限多产品间歇生产过程调度[J].化工学报，2015，66（01）：357-365.

[4] HE Y H， LIANG Y Z， LIU Z M， et al. Improved exact and meta-heuristic methods for minimizing makespan of large-size SMSP[J]. Chemical Engineering Science， 2017， 158：356-359.

[5] 李作成，钱斌，胡蓉，等.遗传-分布估计算法求解化工生产中一类带多工序的异构并行机调度问题[J].化工学报，2014，65（03）：981-992.

[6] 张守刚，吴龙成，王艳，等.基于分布估计算法的硫化车间调度[J].系统仿真学报，2017，29（09）：2182-2188，2197.

[7] 吴龙成，黄松，王艳，等.改进和声搜索算法在硫化车间调度中的应用[J].系统仿真学报，2017，29（03）：630-638.

[8] 王辉，张亚妮.基于多种群协同进化的改进粒子群算法在轮胎硫化车间调度中的应用[J].橡胶工业，2010，57（06）：354-358.

[9] 潘明，钱宇，李秀喜.一种改进的顺序型多目的间歇工厂生产调度的MILP模型[J].化工学报，2006，57（04）：861-866.

[10] CHEN X Y， REINELT G， DAI G M， et al. A mixed integer linear programming model for multi-satellite scheduling[J]. European Journal of Operational Research， 2018， 275（2）：694-707.

[11] 史彬，鄢烈祥.有并行设备的多目的间歇生产调度[J].化工学报，2010，61（11）：2875-2880.

[12] 史彬.流程工业间歇生产调度中并行列队竞争算法的应用研究[D].武汉：武汉理工大学，2010.

[13] 閆献国.GAMS——求解数学规划的强大软件[J].计算机世界，1995（11）：91-92.

[14] SELLE B， KNORR K H， LISGHEID G. Mobilisation and transport of dissolved organic carbon and iron in peat catchments-insights from the lehstenbach stream in Germany using generalised additive models[J]. Hydrological Processes， 2019， 33（25）：3213-3225.

[15] JAIN R， KINGSLY I， CHAND R， et al. Methodology for region level optimum crop plan[J]. International Journal of Information Technology， 2019， 11（4）：619-624.

作者简介：

章佳媛（2000-），女，本科生.研究领域：化学工程与工艺.

张   干（1996-），男，硕士生.研究领域：过程系统工程.

梁心语（2000-），女，本科生.研究领域：工业工程.

叶佳林（1998-），男，本科生.研究领域：化学工程与工艺.

史  彬（1982-），男，博士，副教授.研究领域：过程系统工程.本文通讯作者.