染缸资源的离散事件动态系统建模及优化

余婷，王飞，汲洋弘康

（华侨大学信息科学与工程学院，福建厦门361021）

染缸资源的离散事件动态系统建模及优化

余婷，王飞，汲洋弘康

（华侨大学信息科学与工程学院，福建厦门361021）

根据印染企业订单排缸生产计划的实际情况，建立染缸资源配置系统的自动机模型，使订单的各种染缸配置方式映射到自动机模型中；然后，根据模型行为演化过程，对订单的染缸资源配置过程划分阶段，在各个阶段设定性能指标函数，并建立各阶段间性能指标函数间的递推关系式；最后，用动态规划法对染缸的配置过程寻找最优排缸策略，得到染缸资源利用率最大的配置方式.实例结果表明：与现有的计算机调度系统相比，所建立的模型和决策方法能有效地提高染缸资源的利用率.

染缸；资源配置；离散事件；动态系统；自动机；动态规划

对于资源配置系统的一系列研究成果，很大程度上依赖于离散事件动态系统的迅速发展［1］.目前，对于资源配置系统的研究大致可分为系统的死锁和优化两个主要问题.基于模型的死锁避免，在多进程并发系统中的应用得到了较好的发展.在柔性制造系统中，自动机和Petri网是研究死锁问题的两大数学工具［2］.在自动机中，Lawley等［2］和Reveliotis等［3］提出了基于多项式复杂性的最优无阻塞监控策略来预防死锁避免问题.在Petri网中，李志武等［4］和Tricas等［5］根据Siphon理论来设计控制监控器，避免柔性制造系统中的死锁问题.郭涛等［6］和Sampath等［7］提出了在资源配置系统中的控制规范改变时，用数学规划的方法在Petri网模型中设计资源重构控制器，以实现最优资源配置问题；Tezcan等［8］提出了用鲁棒控制策略来优化多服务器并行服务系统中的服务器分配问题.本文基于福建晋江某印染纺织企业的订单排缸过程，用离散事件动态系统对订单的染缸资源配置过程建立模型.

1 离散事件动态系统

离散事件动态系统是指由异步、突发的事件按照一定的运行规则相互作用，导致系统状态演化的一类动态系统，实际上是一个用于生产产品或提供服务的人造系统，以此来满足人类设定的一些需求［9］.资源配置系统是一类典型的离散事件动态系统，通常由一系列的异步、并发或有序的过程一起构成［6］.它的每个配置过程可能需要多种资源并且服从人为设定的一些复杂规则，而这些规则无法用传统的差微分方程来描述.用离散事件系统能够更好地对染缸资源配置系统建立模型及分析其行为性能［10］.

离散事件动态系统的行为一般以自动机G的生成语言L（G）＝｛s∈Σ＊｜δ（x0，s）！｝表示.假设字符串s长度为｜s｜，Lk（G）＝｛s∈L（G）｜｜s｜＝k｝表示由自动机G生成的长度为k的字符串集合.当字符串长度｜s｜＝k时，则串s发生后，在控制器fk作用下，所有可能的控制输入fk（s）可表示为fk∶L（k）（G）→Γ.其中：s∈L（k）（G）；Γ为控制输入集.因此，控制器f即为一系列决策序列f＝（f0，f1，f2，…）.

2 染缸资源配置系统数学模型的建立

图1 染缸资源配置的自动机模型Fig.1 Automata model for the resource allocation of dye vats

染缸资源配置系统是一种常见的离散事件动态系统.在此，将利用自动机对染缸资源配置系统建立数学模型.在模型中，订单的各种生产方式可以用自动机的状态转换图表示出来.文中，将考虑对l种缸容的染缸资源配置系统建立自动机模型，如图1所示.模型G可表示为

在染缸资源配置系统的自动机模型中，先需定义订单的排缸规则：当订单的质量不能用单一染缸完成加工时，这时就需要对订单做拆分.即一部分可以用某些染缸满负荷工作有限次，另外一部分用某一种染缸不满负荷工作一次，以此来顺利完成订单的加工.因此，对任何一个订单，它都可以通过种染缸进行有限次的满负荷工作和某种染缸进行一次的不满负荷工作来完成.在自动机模型中，订单的任何一种染缸配置方式都可以用一个事件串表示，且这些事件串集合可用正则表达式表示为

3 订单的最优染缸资源配置

假定所有染缸工作事件发生后的染缸资源利用率均为正，染缸满负荷工作时的资源利用率为100%.在此，设一个订单的染缸分配过程按事件串长度分为n阶段，定义如下4种关于染缸资源利用率的控制函数.

1）订单加工过程中，从第k阶段到最后阶段（第n阶段）的染缸平均资源利用率函数 .其表达式为

其中：vj（sj，uj）表示在第j阶段，选取决策uj的染缸资源利用率；uk为在第k阶段时，当状态处于sk时，对剩余订单量分配染缸资源的决策函数.待各阶段决策确定后，整个订单染缸配置过程的决策序列就构成一个策略，用f＝｛u1（s1），u2（s2），…，un（sn）｝表示.

2）最优化函数，表示订单顺利加工完成后的染缸资源利用率最大.其表达式为

在实际生产当中，为使订单能够尽量分配在较大缸容的染缸里加工一次，避免在较小缸容的染缸里加工多次而导致布出现的色差问题，提高布的质量.因此在这里引入利用率折扣率ρ，来减小订单在较小缸容资源的使用频率和效率，折扣率的取值范围为ρ∈（0，1）.

3）染缸满负荷工作时的染缸资源利用率函数，其表达式为

4）染缸不满负荷工作时的染缸资源利用率函数，其表达式为

企业生命周期理论认为，处于不同生命周期阶段的企业有着不同的竞争状况和财务特征。对于初创期企业，外部投资者的关注重点是企业产品或技术的核心竞争力以及未来的发展空间，而此阶段的企业碳信息披露情况不会成为外部投资者关注的重点。据此，提出假设2。

其中：λ1，λ2，λ3，λ4分别表示剩余订单量在缸容为540，360，180，50kg的染缸中不满负荷工作时的染缸利用率.

在染缸资源配置的自动机模型中，任何一个订单的任何一种加工方式都可以用一个事件串表示.每个染缸工作一次视为一个事件.对订单的染缸配置过程按事件串长度划分阶段，在每个阶段设定染缸资源的利用率为决策函数，并构造各个阶段之间染缸资源利用率的递推关系.最后，以所用染缸的最大平均资源利用率为目标函数寻找订单的最优排缸策略.

4 实例分析

图2 订单质量为810kg的染缸自动机模型图Fig.2 Automata model of dye vats for the order weight of 810kg

现有一组订单，其质量分别为810，80，860，410，670，800，685，785，530，655，1 150，2 350，1 450，530，390kg，缸容为50，180，360，540kg的染缸各一台，折扣率为ρ＝0.95，求此组订单的最优染缸资源配置方式，使得染缸资源的利用率最大.以订单质量为810kg的染缸资源配置为例，其自动机模型如图2所示.

按照动态规划的方法，从最后一个阶段开始计算，计算过程从略.

1）当k＝n时，经计算有

2）当k＝n－1时，经计算有

4）当k＝n－3时，经计算有

以订单顺利加工完成为终止阶段.由以上各种配置方式中，可知整个配置过程中最长阶段为4个阶段，故n＝4.

取订单的染缸资源利用率为最大，其配置方式为

据此可知订单质量为810kg的染缸资源最佳配置策略：一个缸容为360kg的染缸满负荷工作一次和一个缸容为540kg的染缸不满负荷工作一次.用自动机的生成语言可表示为

其中：f为染缸资源最优配置策略.

表1 不同缸容下两种系统的排缸结果Tab.1 Result of the two arranging ways of the dye vat for orders

由表1可知：所研究的动态规划寻找订单的最优排缸策略具有一定的有效性.

5 结束语

文中将资源配置系统的自动机模型及动态规划寻最优染缸配置方式应用到实际订单的排缸过程中，其排缸结果与目前印染企业中普遍采用的计算机调度系统的排缸结果相比，染缸资源利用率有了一定的提高.然而，染缸的资源是有限的，当订单的数量多时，会使一些订单集中在某些缸容的染缸排队等待加工，而其他缸容的染缸却是处于空闲状态 .因此，如何使所有染缸同时工作，减少订单的排队等待时间有待于进一步的研究.

［1］ REVELIOTIS S A.Real－time management of resource allocation systems［M］.Boston：Springer Science，2005：2－35.

［2］ FANTI M P，ZHOU M C.Deadlock control methods in automated manufacturing systems［J］.IEEE Trans Syst Man Cybern A：Syst Humans，2004，34（1）：5－22.

［3］ LAWLEY M A，REVELIOTIS S A.Deadlock avoidance for sequential resource allocation systems：Hard and easy cases［J］.Int J Flexible Manuf Syst，2001，13（1）：384－404.

［4］ REVELIOTIS S A，LAWLEY M A，FERREIRA P M.Polynomial complexity deadlock avoidance policies for sequential resource allocation systems［J］.IEEE Trans Automat Control，1997，42（10）：1344－1357.

［5］ LI Shao－yong，LI Zhi－wu，HU He－suan.Siphon extraction for deadlock control in flexible manufacturing systems by using Petri nets［J］.Int J Comput Integr Manuf，2011，24（8）：710－725.

［6］ TRICAS F，EZPELETA J.Some results on siphon computation for deadlock prevention in resource allocation systems modeled with Petri nets［C］∥Proceedings of 2003IEEE Conference on Emerging Technologies and Factory Automation.Lisbon Portugal：IEEE，2003：322－329.

［7］ GUO Tao，LI Jun，DAI Xiao－zhong，et al.Supervisory control reconfiguration and optimization of resource allocation systems with a Petri Net and mathematical programming approach［C］∥Proceedings of 9th IEEE International Conference on Networking，Sensing and Control.Beijing：IEEE，2012：52－57.

［8］ SAMPATH R，DARABI H.Control reconfiguration of discrete event systems with dynamic control specifications［J］.IEEE Transactions on Automation Science and Engineering，2007，5（1）：84－100.

［9］ DAI J G，TEZCAN T.Optimal control of parallel server systems with many servers in heavy traffic［J］.Queueing Syst，2008，59（2）：95－134.

［10］ 徐国华，胡奇英.离散事件动态系统的监控方法［M］.郑州：河南科学技术出版社，1996：1－10.

［11］ 郑大忠，赵千川.离散事件动态系统［M］.北京：清华大学出版社，2001：282－340.

Model Building and Optimization of Discrete Event Dynamic System for Dye Vats

YU Ting，WANG Fei，JI Yang－hong－kang
（College of Information Science and Engineering，Huaqiao University，Xiamen 361021，China）

According to the flow of the vat arranging for orders in the actual production，the automata model for the resource allocation of dye vats was established.By this way，all the dye vats arranging ways for an order can be mapped into the automata model.Then according to the evolution process of the model behavior，the resource allocation of the dye vats were divided into several stages firstly.Secondly，the performance index function was defined at each stage.Thirdly，the recursive relation of performance index function was set up between each stage.Lastly，the dynamic programming method was adopted to get the optimal way of the allocation of the dye vats，aiming at improving the utilization of the dye vat to the maximum.Compared to the existing computer dispatch system，the result of the instance shows that the model and the decision method provided in this paper can effectively improve the utilization of the dye vats.

dye vats；resource allcation；discrete event；dynamic system；automata；dynamic programming

TP 271.8

A

（责任编辑：黄晓楠 英文审校：吴逢铁）

1000－5013（2014）01－0031－05

10.11830／ISSN.1000－5013.2014.01.0031

2013－06－04

王飞（1977－），男，副教授，主要从事离散事件动态系统控制、资源优化配置的研究.E－mail：feiw545＠163.com.

国家自然科学基金资助项目（61203040）；福建省自然科学基金资助项目（2011J01532）