王江武，胡晓兵，武韶敏

（四川大学 制造科学与工程学院，成都 610065）

设计与应用

基于约束理论的FMS调度算法研究

王江武，胡晓兵，武韶敏

（四川大学 制造科学与工程学院，成都 610065）

针对FMS计划排产问题，以消除排产制约因素，优化排产，达到产能平衡为目标，建立相关数学模型，研究、设计了基于约束理论的调度算法。通过分析约束理论中的“鼓-缓冲-绳”(DBR)系统思想以及FMS的排产要求，找到系统排产的瓶颈资源，对生产计划进行重新排序，最终达到系统优化排产。并在实际调度问题中，验证了该算法的可行性和有效性。

柔性制造系统；计划排产；约束理论

0　引言

随着技术创新和信息扩散的加快，人们的需求日趋多样化和个性化，因而，采取面向订单设计的订货生产已经成为生产方式的主流。但是面对订货型生产管理，往往会存在以下问题：产品的订单具有随机性和突发性，生产预计困难；生产资源不能及时到位，生产连续性差；设备故障等突发因素难以预计导致排产计划不准等，而这些问题也成为了制约企业生产效率的因素，也是设计排产算法时应该考虑的问题。

常见的算法包括基于Petri网，基于规则，遗传算法，禁忌搜索法或者基于仿真等，以提高柔性制造系统计划排程和生产调度的性能，如郝东、蒋昌俊、林琳，等[1]在Petri网对柔性制造系统建模的基础上，使用遗传算法研究调度问题并得到近似最优解，虽然其适合多品种、小批量的生产调度问题，但遗传算法的结果具有一定随机性，其复现性差，且优化目标单一。Priore P，Pino R，Parre☒o J，et al.[2]研究了人工神经网络技术在调度中的应用，建立学习机制，通过形成“调度知识”丰富调度规则。

然而以上算法由于复杂程度高，难以通过计算机编程实现，大多是理论上的研究，实用性不强，不适于FMS调度应用。本文从约束理论这套简单明了且便于接受的实施法则入手，提出了一种基于约束理论的生产排产模型，分析了其算法流程，并在实际调度问题中进行验证，结果表明所建立的模型和算法切实可行。

1　约束理论

约束理论（TOC）是在以色列学者戈德拉特博士（Dr.EliyahuM.Goldratt）的优化生产技术（Optimized Production Technology，OPT）理论基础上发展而来的，其核心就在于找到制约系统目标实现的因素，通过对制约因素进行消除以改善系统性能，其主要适用于离散型机群布置的多品种订货型生产模式。

约束理论在排产过程中的主要工作就是找到瓶颈工序，消除瓶颈工序，其最终的目的是为了达到物流的平衡，以缩短生产周期，减少在制品，以达到计划的短期最优化。通过DBR系统，即“鼓-缓冲器-绳”系统可以很好地控制物流平衡，落实优化生产技术。

图1　DBR系统

2　排产模型及算法流程

2.1排产模型

假设企业有L个客户，l为客户编号，l=1,2，…，L，M类设备，设备编号记为m，m=1，2，…，M，可加工N种零件，零件编号为n，n=1，2，…，N，在从T1到T2时间内接到一批订单A。

按零件n汇总出该产品在计划期的生产量qn（n=1，2，…，N）。根据这个生产量可按资源m汇总出在计划期内该资源的负荷（消耗工时）为：

其中，wnm表示资源的消耗系数，即零件n在资源m上加工的单位加工工时。

记H1为瓶颈资源集，H2为非瓶颈资源集，将G∩H1≠Φ的生产计划，即占用瓶颈资源的生产计划定义为

F1为占用瓶颈资源的生产计划数量。类似的，将G∩H1=Φ的生产计划定义为不占用瓶颈资源的生产计划

S11表示D1中的延时计划，S12表示 D1中的新计划，同理可得S21表示D2中的延时计划，S22表示D2中的新计划。

综合优先系数的值R为客户重要性权值Vl，计划紧迫性权值Up和计划效益权值Cp三者的乘积。即第一类计划综合优先系数为R1p，R1p=V1pL1pC1p, p=1，2，…，F1；第二类计划综合优先系数为R2p，R2p=V2pL2pC2p，p=F1+1，F1+2，…，P。

2.2算法流程

首先，找到生产负荷高于可用产能的工作中心，即瓶颈资源；其次按算法规则顺序选择瓶颈资源；消除选择资源的瓶颈，可选择向前移动计划也可以选择向后推迟计划，或者寻找计划的替代资源；根据资源瓶颈的变动，调整其前、后的工序计划；根据以上变动相应调整其他受干扰的资源。至此一个循环结束，一个加工中心资源得到平衡，再选取新的资源，从头开始，经过反复几次计算，最终达到整个系统优化排产。

3　算法验证

在2016年1月1日到2016年1月15日期间有6笔订单，面向4个客户，共生产4种零件。生产订单信息如表1所示。

表1　订单基本信息

【】【】

已知FMS-80生产线由3台加工中心组成，其设备日最大负荷量均为24小时。单位产品加工的资源需求信息如表2所示。

表2　资源需求信息

以产品的交货日期作为瓶颈资源分段查询标准，计算每个时间段内的设备需求负荷Tm，分段查询是否存在瓶颈约束，从而得到以下数据：

表3　分段设备负荷

由表中数据可以看出在整个计划时间段内不存在瓶颈资源约束，但在分段日期内，设备M1上存在局部瓶颈约束，按照订单状态对所需排产订单进行分类，分别计算相应的综合优先系数，并根据综合优先系数对占用瓶颈资源的计划进行排序，按次序进行排产，得到最终的排产结果：

表4　排产结果

由于P3计划的优先级高于P2计划，故将P2计划部分延期到1月8号后执行，此时系统在各个时间段内设备需求时间均小于设备最大负荷，均不存在瓶颈制约，可正常进行生产，排产结果合理。

4　结论

FMS面向的是多品种，中小批量的生产，能够快速响应市场需求的变化。FMS应用支撑系统作为整个工厂级管理框架中承上启下的中间层，其采用的排产算法既要考虑订单具有随机性和突发性，又要兼顾系统资源的平衡性。本文在研究了FMS实际调度问题的基础上，提出了基于约束理论的排产算法，并在实际的调度问题中得到了有效的验证。

[1] 郝东,蒋昌俊,林琳.基于Petri网与GA算法的FMS调度优化[J].计算机学报,2005,02：201-208.

[2] Priore P, Pino R, Parre☒o J,et al. Real-time Scheduling of Flexible Manufacturing Systems using Support Vector Machines and Neural Networks[J].Proceedings of the 2013 International Conference on Artificial Intelligence, ICAI 2013; 2013, 651-656;

[3] 李浩,沈祖志,邓明荣.订货型企业基于约束理论的订单排产优化研究[J]. 中国机械工程,2004,10：21-25.

[4] Chan F T S,Wong T C,Chan L Y. Flexible job-shop scheduling problem under resource constraints[J].International Journal of Production Research, 2006,44(11)：2071-2089.

Research into FMS scheduling algorithm based on the theory of constraints

WANG Jiang-wu, HU Xiao-bing, WU Shao-min

TH186

A

1009-0134(2016)07-0063-03

2016-02-28

国家科技重大专项（2012ZX04011-031）；四川省科技支撑计划项目（2014GZ20117）

王江武（1991 -），男，甘肃武威人，硕士，研究方向为数字化制造。