基于改进型批决策与调度建模的生产计划调度系统的研究*

花季伟，李晓婷

(1.天津师范大学计算机与信息工程学院，天津 300074；2.河北省新闻出版广电监管中心局，河北 石家庄 050031)

基于改进型批决策与调度建模的生产计划调度系统的研究*

花季伟1，李晓婷2

(1.天津师范大学计算机与信息工程学院，天津 300074；2.河北省新闻出版广电监管中心局，河北 石家庄 050031)

热轧型钢生产工艺复杂，其生产中极易出现由于计划调度安排不当而产生的交货期延误、库存超负荷等问题。针对以上问题研究设计了MES生产计划调度系统，改进了批决策调度策略用于数学建模，利用自适应遗传算法求解生产调度计划。以此为基础，为某热轧企业设计实现了生产计划调度系统，并通过真实的热轧型钢订单、原料、设备等数据，对模型改进前后的计划编制方法进行模拟与比较，验证了利用该改进型批决策与调度模型编制的热轧型钢生产调度计划可节省生产时间、降低设备调度时间，以此来指导热轧型钢的生产可切实减少交货延误和减少库存占用率，并提高企业利润率。

生产计划与调度；热轧型钢；批决策与调度；遗传算法

1 引言

合理的生产计划与调度是保证企业长期规划顺利、顺畅实施和企业生产能力充分发挥的关键所在[1]。制造执行系统MES(Manufacturing Execution System)旨在加强物料需求计划的执行功能，把物料需求计划通过执行系统同车间作业现场控制系统联系起来。生产计划与调度系统是MES系统的重要组成部分。但是，由于热轧型钢的产品规格众多、生产工艺复杂，以至于国内自主研发的面向热轧型钢的MES系统并不多见。并且在实际生产中常常以人工操作进行生产计划的编制与生产调度操作，由此计划与调度方案往往难以达到较优水平。本文以某中型钢铁企业的实际生产调度为基础，以提高企业利润、优化生产方案为目标，研究了面向中型企业的MES生产计划调度系统，其主要功能包括计划编制、生产调度与核发等。

现有的热轧生产与调度计划建模策略主要有串行和并行两种。其中，串行建模策略[2]属于贪婪策略且容易陷入局部最优；并行策略[3]的数学模型模型每运行一次得到多个轧制单元，但是多个轧制单元之间的生产顺序无法确定，当对轧制单元排序后容易出现大量钢坯拖期的现象。针对以上策略的优缺点，文献[4～6]论述了一种新的并行建模策略，它集成了批决策与调度问题，在组批过程中考虑了轧制单元之间的生产顺序以及交货日期等时间因素。但是，它也有局限性，即计划编制轧制单元的数量需为固定数值。而目前求解计划编制问题时通常采用智能优化算法，它们能较好地解决复杂系统中出现的组合爆炸问题，常见的有模拟退火算法、粒子群算法、神经网络算法、蚁群算法、遗传算法等等[7]，其中被应用最广泛的是遗传算法[8,9]。

2 生产计划与调度系统设计

2.1 问题描述

生产计划的求解问题是极其复杂的：解的数量巨大，不易寻求最优解；计划必须满足负荷工艺约束条件，具有可行性；评估每一个解的优劣很费时等等。并且，如果编制以单个钢坯为单位的生产计划，这个求解的过程将更加复杂。在以往的实际热轧型钢生产中，生产计划的编制为了达到减少更换轧辊次数、降低生产产品的波动性，经常按照班次或者轧辊的最大轧制重量来编制生产单元。为凑满一个生产单元，经常需要凭借人工经验来调整生产计划，这样编制的计划很难成为较优的方案。

生产计划的编制受到众多条件的制约，例如在轧制生产线上如何调度各个生产环节设备的使用，最大化地利用设备产能，而又要考虑到设备的检修维护，以确保设备的使用寿命和产品的质量；在不同钢种、规格和交货期需求下订单的组批，既要保证不能延误交货期，又要尽量减少库存的积压；如何调度钢坯的使用以缩短生产周期、确保生产的顺利进行等等。生产计划编制完成，执行生产计划的过程中依然充满了干扰因素。如紧急订单的加入、设备故障、原料钢坯不到位等，当面对此类事件时计划的调整、实际生产的配合调度就需要及时发挥作用。生产计划的及时调整，既要满足订单的生产需要，又要保证整体计划实施的稳定性。生产调度既要保证原材料钢坯的及时调度到位，又要考虑热轧前加热炉的充分使用与不同加热炉之间的配合。所以，建立一个高效准确、可灵活应对突发事件而做出调整的计划自动编制系统具有重要意义。

2.2 系统设计及功能描述

本系统设计以可靠性、实用性、易维护性和行业特殊性为原则，从河北某热轧型钢企业的特点出发，如产品品种繁多、型号规格复杂、订单数目大、订货吨位少、轧钢轧辊需根据成品种类变换等等，并且还兼顾此行业的通用性，避免同行业重复开发造成浪费。该MES生产调度系统采用浏览器/服务器模式，简称B/S模式(Brower/Server)，它可以大大简化客户端电脑的载荷，减少系统升级和维护的工作量，以降低总体成本。生产调度系统的功能模块如图1所示。

Figure 1 Function modules图1 系统功能模块设计

生产计划与调度系统主要模块的功能如下：

(1)销售订单转换：销售订单指客户对轧钢企业购买成品下达的订单，包括交易金额、数量、交货日期等信息；生产订单指包括了原料、钢种、规格等生产参数的用于车间作业的指导性文件。两者的转换加上系统读取的原料、设备等基础数据，进行原料损耗的计算，使得生产更加精确。

(2)生产计划编制：根据订单要求以及生产约束等信息编制生产计划。

(3)生产计划修改与调整：有紧急订单、设备故障、钢坯等原料不到位等扰动出现时，则需要对生产计划执行时间、优先级等参数进行调整，调整完毕后系统自动重新编制新的生产计划。如即将执行的计划，正常情况下数据库中的状态位为0，当钢坯供应未到位时状态位为1，此时就会触发生产计划与调度系统的扰动处理程序，临时调用其他计划下已就位的钢坯。若无钢坯可调用，系统自动修改该计划的优先级状态位，重新编制未完成的订单的生产顺序；同时系统界面对工作人员进行预警提示，工作人员可随时停止或者调整计划的实施。

(4)生产计划核发与调度：调度原料与设备的使用，核实调度情况，确认开始生产。

3 生产计划与调度模型与遗传算法

3.1 难点分析

热轧型钢生产计划与调度的最主要对象为原材料钢坯，它的使用状况、调度状态直接影响着生产能否顺利进行。钢坯调度原则是优先清库存，并且当钢坯还未铸造完成时，在计划中将产生一个虚拟的钢坯号以表示未入库的钢坯。计划的编制过程需要从可选用的钢坯中选出订单要求的数量，依据工艺约束等信息将其编制为若干个轧制单元。在传统生产中，生产计划的编制为了达到减少更换轧辊次数、降低生产产品的波动性，经常按照班次或者轧辊的最大轧制重量来编制轧制单元。为凑满一个轧制单元，经常需要凭借人工经验来调整生产计划，这样编制的计划很难成为较优的方案，并且人工的计划与调度经常造成生产不能按时完成，以至于合同交货期的延误，又如不合理的生产计划易导致成品不合理地长期占用库存等问题。

3.2 改进型批决策与调度模型

批决策与调度是一种新的并行策略，在组批过程中同时考虑到了轧制单元之间的生产顺序以及交货期等时间因素。批调度就是要确定轧制单元之间的生产顺序和时间表，进而确定各轧制单元中钢坯的生产顺序。

首先对数学模型中的参数和变量进行说明：n为订单总数；x若为j订单不拆分且在i订单之后生产，则xij为1，否则为0；tij为i订单之后生产j订单的时间，且j订单不拆分，若i订单和j订单为不同品种则其中包括换轧辊的时间；m为j订单拆分为m个部分生产；当j订单的第k部分在i订单之后生产，则yij为1，否则为0；tijk为在i订单之后生产j订单的第k部分，若i订单和j订单为不同品种则其中包括换轧辊的时间；t为换辊时间、换轧辊导卫时间、设备检修时间等余量时间总和；Tj为j订单的交货时间；τs为当前系统时间；g为相邻两次换轧辊之间的订单的原料重量；G为轧辊最大轧制重量；τz为所需钢坯的连铸完成时间；τr为钢坯经过加热炉到达轧机的时间；τi为i订单开始生产的时间；τΔ为前一个订单生产完和后一个订单开始生产之间的时间差；Pmin为相邻两次换轧辊之间轧制的最小钢坯数；p为相邻两次换轧辊之间轧制的钢坯数；Pmax为相邻两次换轧辊之间轧制的最大钢坯数；gt为存放在成品库里的成品重量；Gc为最大库存量。

传统批决策与调度的数学模型可描述为：

目标函数为：

(1)

约束条件为：

(2)

(3)

(4)

其中，目标函数式(1)表示尽量使总生产时间最短；约束条件式(2)表示合同交货期窗口约束，生产计划尽量使合同拖期总惩罚最小，即满足交货时间Tj；约束条件式(3)表示钢坯的重量约束，轧制完成一定重量的钢坯后，轧辊轧制能力已大幅度下降，需要更换轧辊；约束条件式(4)表示时间窗约束，即生产订单的开始生产时间τi应保证在钢坯连铸完成时间τz之后，或者满足钢坯库中可以直接调用的钢坯经过加热炉后到达轧机的时间τr。

为了适应热轧型钢的品种规格多、生产数量灵活、轧制工艺复杂等特点，对现有的批决策与调度模型进行改进。即以生产一个订单所需的一批钢坯为组批单元来编制生产计划，且完全放开轧制单元的数量限制，也可称为可拆分订单的计划编制模型。就是一个生产订单可以以约束条件为基础拆分成若干部分，它们与其他生产订单或其他订单的某些部分，混合编制生产计划，如图2所示。

Figure 2 Split production order图2 生产订单的拆分

热轧生产调度计划需要在不同钢种、规格和交货期需求下订单的组批，既要保证不能延误交货期，又要尽量减少库存的积压；在轧制生产线上如何调度各个生产环节设备的使用，最大化地利用各个设备的产能，而又要考虑到设备的维护。计划的编制要尽量减少总的生产时间，以确保真正地降低成本。

该问题的数学模型可描述为：

目标函数为：

(5)

约束条件为：

(6)

(7)

(8)

(9)

(10)

(11)

(12)

目标函数式(5)表示尽量使总生产时间最短，跟传统模型相比，由于加入了拆分订单的因素，所以目标函数式也变为由不拆分的和拆分的订单的生产时间相加。约束条件式(6)～式(8)同传统模型相同。根据热轧型钢企业的生产特点，如不同品种型钢需要不同的轧辊轧制等，约束条件式新增了：(1)约束条件式(9)表示同品种合并生产约束，在一个生产订单生产完毕后，如果轧辊还未达到轧制限制量并且和下一生产订单的最迟生产时间之间有余量，可以将同品种的订单提前一部分合并生产；(2)约束条件式(10)表示相邻两次换轧辊之间的轧制钢坯数必须达到计划人员规定的上下限；(3)约束条件式(11)表示钢坯调度约束，保证一块钢坯只出现在一个轧制单元中，保证钢坯处理的唯一性；(4)约束条件式(12)表示库存约束，编制计划时应考虑提前完成订单时库中是否有能力存入此批成品，并且尽量减少成品库存的占用。

3.3 遗传算法求解

遗传算法将问题的求解表示成“染色体”的适者生存过程，通过“染色体”群的一代代不断进化，最终收敛到“最适应环境”的个体，从而求得问题的最优解或满意解。相比其他算法，遗传算法的编码技术和遗传操作比较简单，算法进行全空间并行搜索，从而能够提高效率且不易陷入局部极小[8,9]。为了求解改进型批决策与调度的生产调度计划编制模型，系统采用了自适应遗传算法[10]。传统遗传算法中交叉概率和变异概率是固定的，为了提高遗传算法的收敛速度，将其设置改为自适应遗传算法的交差概率pc和变异概率pm，计算公式如下：

该遗传算法的具体实施步骤如下：

步骤1模型初始化。在算法初始时进行模型转换及约束处理，根据生产工艺流程和相关参数的模型初始化，并施加相关约束。

步骤2初始化种群。对生产订单进行编码，每个个体中包含表示订单、重量、拆分标识等信息的基因。设定种群数量为50，随机生成初始个体100个，通过计算其适应值来选出较优的50个个体作为初始种群。

步骤3求各个组合方案最优解。由于编制生产计划时订单数量的不确定性，在此为使计算简化，直接将模型中的目标函数转化为适应度函数。该目标函数为最小化问题，设定适应度函数为：

Figure 3 Interface of plan图3 计划编制界面

步骤4遗传操作。选择操作采用适应度比例方法即轮盘赌选择法，且为了避免轮盘赌选择法容易引起的早熟收敛和搜索迟钝问题，在此采用有条件的最优保留策略进行辅助。对于交叉操作，使用由Reeves[10]提出的专门为调度问题设计的改进型单点交叉算子和部分映射交叉算子。为了满足生产计划调度的实际需要，即保证订单的唯一性，改进型单点交叉流程在进行了传统单点交叉操作之后，还需要进行对非交换位置基因的变换操作。为了提高遗传算法的收敛速度，本文采用了自适应遗传算法[11]的交差概率pc和变异概率pm。

步骤5重复步骤3和步骤4，直到达到预定迭代次数而终止，并输出末代最优个体对应的问题解。

3.4 算例比较与分析

分别随机取该热轧钢铁企业的20个、50个不同实际销售合同的数据作为第一组和第二组实验数据。这些销售合同包括多种成品种类，如方钢、圆钢、角钢、工字钢、乙字钢等，并且有多种重量要求，如500吨、700吨、1 000吨、2 000吨等。按照成品种类的不同，销售合同可以分解成若干生产订单。生产中更换生产的成品种类或达到轧辊轧制吨数极限时必须更换轧辊，轧制吨数均设定为1 000吨，换辊时间设定为2小时。设定设备检修日历：每周一次小型检修4小时，每两周一次大型检修15小时，检修可与更换轧辊同时进行。在此热轧型钢MES项目中，利用ASP.NET技术制作了B/S模式的生产计划与调度系统，并且选用了适合大型企业的Oracle数据库作为支持。生产计划调度系统的计划编制界面如图3所示。

以实际的生产计划调度系统为运行环境，采用数据库的数据库语言对四种生产计划排序方法进行编程：

方法一按照销售合同中要求的交货日期顺序编制生产调度计划。

方法二按照约束条件调整生产订单的顺序，如尽量满足合同交货期、满足轧辊对钢坯重量的限制等，且生产订单不拆分。建立如式(1)～式(5)的传统批决策与调度模型，以简单的串行搜索算法进行求解。

方法三按照约束条件调整生产订单的顺序，如尽量满足合同交货期、满足轧辊对钢坯重量的限制等，且生产订单不拆分。建立如式(1)～式(5)的传统批决策与调度模型，以自适应遗传算法进行求解。

方法四以改进型的批决策与调度策略建立模型，即加入订单可拆分形式，并且以实际生产的特点扩充约束条件，如拆分合并约束条件。以自适应遗传算法进行求解。

采用以上四种方法分别对第一组20个合同、第二组50个合同进行生产计划编制的对比数据如表1和表2所示，其中第三种和第四种方法分别反复进行100次，取平均值。

Table1 Data comparison of 20 contracts’production planning for four methods表1 四种方法分别对20个合同的生产计划编制数据对比

Table2 Data comparison of 50 contracts’production planning for four methods表2 四种方法分别对50个合同的生产计划编制数据对比

由表1和表2中的数据可明显看出，以改进型的批决策与调度策略模型为基础的计划，无论是20个合同还是50个合同的生产总时间、需要的检修总时间，相较于简单的按交货时间顺序排序、不拆分订单的串行搜索排序所需要的时间都要短。特别是相较于普通批决策与调度模型得出的生产计划调度方案，当合同数量较多时，改进的模型体现出了较大优势。换辊次数的减少也对节约时间、降低能源消耗、减少劳力消耗、降低企业成本起到了很大作用。特别是新模型编制出的热轧生产计划调度方案，基本解决了延误合同约定交货期的问题，没有了合同违约金，企业的利润将有很大程度的提高。随着合同数量的增加，最大库存占用率越来越高，在50个合同的生产计划编制数据中，方法一的库存占用率已经超过了100%，已经无法满足生产需要。而新模型的应用可以大大减少库存占用率，对于企业在一定时期内合同数量的增加或者接大订单生产有着重要的意义。

虽然改进型的批决策与调度模型在求解过程中更加复杂，使得解的种类大大提升。图4所示为普通批决策与调度策略模型和改进后的模型的求解过程收敛图，可明显看出，改进型模型目标函数的收敛速度虽然相较于普通模型的收敛速度慢，但是改进型模型求得的解更优于普通模型的解，即节约了生产总时间。

Figure 4 Curve convergence of solution procedures图4 求解过程收敛对比图

4 结束语

本文以热轧型钢企业的项目为依托，研究设计了MES生产计划与调度系统的各功能模块。以批决策与调度和订单排序的基本理论为基础，改进了批决策与调度模型，并对实际钢铁企业的热轧生产调度计划的编制问题进行了求解。通过与普通模型求解计划的横向比较，以及不同数目、不同钢种的订单组合的纵向比较，验证了改进的新模型求得的解可节约生产时间、提高产能，如此编制出的生产计划调度方案可以大大降低热轧型钢企业的生产成本。

[1] Huang Xiao-ling, Chai Tian-you. Application of planning and sheduling cascade model of complex system processing to mineral processing MES system [J]. Acta Automatica Sinica, 2011,37(9):1130-1139.(in Chinese)

[2] Gao Zhi-xin, Li Tie-ke, Su Zhi-xiong. Application of memetic algorithm on slab sequencing[J]. Computer Engineering and Applications,2009,45 (19):192-194.(in Chinese)

[3] Chen Hao, Du Bin, Huang Ke-wei. PESAII algorithm for hot milling batch planning problem based on PCVRP[J].Control Engineering of China, 2012,18(S),86-88.(in Chinese)

[4] Xu Rui, Chen Hua-ping, Shao Hao, et al. Two kinds of ant colony algorithms to minimize the total completion time for batch scheduling problem [J]. Computer Integrated Manufacturing Systems, 2010,16(6):1255-1264.(in Chinese)

[5] Li Xue-bing. Development and application of assembly production management system with small batch and multi-items[J]. Modern Manufacturing Engineering, 2011(3):23-27.(in Chinese)

[6] Han Wen-min,Zeng Li-yi,Wei Yun-de,et al. Study on dynamic reconfiguration approach of manufacturing cell for make-to-order[J]. Process Automation Instrumentation, 2011, 32(3):29-35.(in Chinese)

[7] Gao Yang, Jiang Zi-bin. Using HGA to solve production planning in VE [J]. Control and Decision, 2007,22(8):931-934.(in Chinese)

[8] Cui Xue-li. Job shop schedule scheme based on hybrid genetic algorithm[J]. Computer Engineering and Design, 2011,32(7):2467-2471.(in Chinese)

[9] Pezzella F, Morganti G, Ciaschetti G.A genetic algorithm for the flexible job-shop scheduling problem [J]. Computers & Operations Research,2008,35(10):3202-3212.

[10] Srinivas M, Patnaik L M. Adaptive probabilities of crossover and mutation in genetic algorithms[J].IEEE Transactions on Systems, Man, and Cybernetics,1994,24(4):656-667.

附中文参考文献：

[1] 黄肖玲,柴天佑. 复杂生产过程计划调度级联模型在选矿MES中的应用研究[J]. 自动化学报, 2011,37(9):1130-1139.

[2] 高知新,李铁克,苏志雄.Memetic算法在板坯排序中的应用[J].计算机工程与应用,2009,45(19),192-194.

[3] 陈浩,杜斌,黄可为. PESAII算法求解基于PCVRP的热轧批量计划问题[J].控制工程,2012,18(S):86-88.

[4] 许瑞,陈华平,邵浩,等. 极小化总完工时间批调度问题的两种蚁群算法[J]. 计算机集成制造系统, 2010,16(6):1255-1264.

[5] 李学兵.小批量多品种装配生产管理系统的开发与应用[J]. 现代制造工程, 2011(3):23-27.

[6] 韩文民,曾里义,魏允德.面向订单生产的制造单元动态重构方法研究[J]. 自动化仪表, 2011, 32(3):29-35.

[7] 高阳,江资斌. 用混合遗传算法求解虚拟企业生产计划[J]. 控制与决策, 2007,22(8):931-934.

[8] 崔雪丽.基于混合遗传算法的车间生产计划调度[J].计算机工程与设计,2011,32(7):2467-2471.

HuaJi-wei,born in 1978,PhD,lecturer,CCF member(E200027582M),his research interests include computer software, and computer application.

李晓婷(1986-),女，河北石家庄人，硕士，研究方向为计算机控制与工程应用。E-mail:176307200@qq.com

LiXiao-ting,born in 1986,MS，her research interests include computer control and engineering application.

Studyofproductionplanningandschedulingsystembasedonbatchdecision-makingandschedulingmodel

HUA Ji-wei1,LI Xiao-ting2

(1.College of Computer and Information Engineering,Tianjin Normal University,Tianjin 300074；2.Hebei Press Publication Radio Film and Television Bureau,Supervision Center,Shijiazhuang 050031,China)

Due to the complexity of the hot rolled section steel production process, some problems such as delivery delay and overload inventory appear easily, which are induced by improper planning and scheduling. Aiming at these problems, the MES production planning and scheduling system is studied and designed. A mathematical model is formulated based on the improved batch decision-making and scheduling strategy. And the production scheduling plan is solved with self-adaptive genetic algorithm. Based on these theories, a production planning and scheduling system for a hot-rolled enterprise is designed and implemented. Through the real hot rolled steel’s orders data, raw materials data, equipment data and so on, the planning methods of using new batch decision-making and scheduling strategy model and old ones are simulated and compared. It is improved that the solution of batch decision-making and scheduling model is able to save production time, reduce the times of equipment scheduling. Using this plan to direct production activities can reduce the times of delay in delivery, reduce inventory occupancy rate and improve enterprise profit margin.

production planning and scheduling;hot rolling section steel;batch decision-making and batch scheduling;genetic algorithm

2012-07-21;

：2012-11-23

河北省基础研究重点项目(09963536D);天津市高等学校科技发展基金计划项目(20120814);天津师范大学博士基金资助项目(52XB1001，52X09013)

1007-130X(2014)02-0347-07

TP391

：A

10.3969/j.issn.1007-130X.2014.02.025

花季伟(1978-),男,天津人，博士，讲师，CCF会员(E200027582M)，研究方向为计算机软件及计算机应用。E-mail:huajiwei@yeah.net

通信地址：300074 天津市天津师范大学计算机与信息工程学院Address:College of Computer and Information Engineering,Tianjin Normal University,Tianjin 300074,P.R.China