基于离散事件动态系统的染缸资源配置优化方法研究

余 婷，何经旺，林 励，王子玥玥

（福建信息职业技术学院，福建 福州 350003）

目前，国内的印染企业仍对生产订单进行人工染缸资源配置，企业自动化程度与生产效率较低。因此，对订单进行合理的染缸资源配置，提高染机资源利用率，对印染企业具有重要意义。李可彪等[1]根据企业生产计划流程建立了以投入生产染缸空闲量最少为目标、以有限生产资源为约束的染缸生产排缸模型。莫丰勇[2]则针对企业浸染生产过程中的加工设备多和调度复杂等特性，建立了一种用于浸染生产调度的数学模型，并用遗传算法求解染缸配置。本研究基于福建晋江某纺织企业的染缸资源配置过程，用离散事件动态系统的方法对订单排缸过程建立模型，再用动态规划法寻找染缸最优配置策略，使订单能在较短时间内顺利加工完成并提高利用率。

1 染缸资源配置的离散事件动态系统模型

1.1 离散事件动态系统

离散事件动态系统（Discrete Event Dynamic System，DEDS）兴起于20世纪80年代，由一些有复杂交互作用的事件驱动，系统状态仅在一些离散时刻点随着事件的发生而变化。形式语言/自动机是DEDS的基本建模工具[3]。一个确定的有限状态自动机G为一个五元组[4]：G=(Q,∑,δ,q0,Qm)。其中，Q为有限状态集合；∑为事件集（分可控事件集∑c和不可控事件集∑uc，且∑uc=∑/ ∑c）；δ为状态转移函数，即δ:Q× ∑→Q，描述系统由一个状态经给定条件转移至新状态的过程；q0∈Q为初始状态；Qm∈Q为标识状态。若定义δ(q0,ε)=q0，且δ(q0,sσ)=δ[δ(q0,s),σ]，∀σ∈∑，s∈∑*，则状态转移函数也可以扩展定义至符号串集合∑*，即δ:Q× ∑→Q。对于任一初始状态q0∈Q，自动机G的生成语言为L(G)定义为使状态转移函数δ(w,q0)有定义的输入符号串w∈∑*的一个集，用式子表示为L(G)={s∈∑*|δ(q0,s)!}。设有一个映射f:L(G)→Γ，表示当自动机G产生事件串s时的控制输入为f(s)，下一个发生的事件需发生在f(s)∩{σ:δ(sσ,q0)!}中，则称f为监控器，记f控制下的系统为f/G。在此，假设字符串s的长度为|s|，Lk(G)={s∈L(G)||s|=k}表示由自动机G生成的长度为k的字符串集合。当字符串长度|s|=k时，串s发生后，在监控器fk的作用下，所有可能的控制输入fk(s)可表示为fk:Lk(G)→Γ，其中，s∈Lk(G)，Γ为控制输入集。故控制器f为一系列决策序列f=(f0,f1,f2,…)。

1.2 染缸资源配置的离散事件动态系统建模

资源配置系统是一类典型的离散事件动态系统。针对染缸资源配置系统，规定配置规则：任一订单均可通过某些染缸进行有限次的满负荷加工及一次不满负荷加工完成；若订单质量小于染缸容量，则将订单直接分配在合适的染缸进行生产；若订单质量大于染缸容量，则需对订单进行适当拆分，将其分配到若干染缸中生产。

本研究考虑对l种缸容的染缸资源配置系统建立自动机模型，使订单的各种生产方式通过自动机状态转换图表示出来，模型G:(Q,∑,δ,q0,Qm)。其中，Q={l种染缸工作状态的集合}，0表示染缸处于空闲状态，1表示染缸处于满负荷工作状态，2表示染缸处于不满负荷工作状态；∑={不同缸容染缸工作事件的集合}，σi(i=1,2,…,l)表示第i种缸容的染缸满负荷工作，βi、βj(i=1,…,l,j=1,…,l,i≠j)分别表示使第i种、第j种缸容的染缸不满负荷工作，r表示染缸工作结束返回空闲状态；δ:Q× ∑→Q为各种染缸工作状态的转移函数；表示l种染缸资源的初始状态均处于空闲状态；Qm为订单顺利加工完成后染缸的工作状态。将染缸的工作视为一个事件，在自动机模型中，订单的任何一种加工方式均可用一个事件串表示，这些事件串的集合可用正则表达式表示：R=(σlr)*…(σlr)*(βlr+…+βlr)，其中，∑c={σl,…,σl,βl,…,βl}，∑uc={r}。

2 订单的最优染缸资源配置方式求解

假定各染缸满负荷工作时利用率为100%，设有一组订单，每个订单的染缸分配过程按事件串长度分为n阶段，定义以下5种关于染缸资源利用率的控制函数：

（1）在加工第p个订单Np时，从第k阶段到最后阶段（第n阶段）的染缸平均资源有效利用率函数为vk=(sk,uk)表示在第k阶段，选取决策uk的染缸资源有效利用率；uk为在第k阶段，当状态处于sk时，对剩余订单量分配染缸资源的决策函数。待各阶段决策确定后，整个订单染缸配置过程的决策序列就构成一个策略，用f={u1(s1),u2(s2),…,un(sn)}表示。

（3）对于订单组中第p个订单Np，当选取最优染缸配置方式后，染缸资源的实际利用率函数：Wp=Np/Mp，Np为第p个订单的质量，Mp为所选各染缸的容量总和。

（4）对订单组进行染缸资源配置后，整个订单组加工周期符号表示对式子向上取整，P1080、P540、P360、P180、P50分别表示在染缸资源配置结果中缸容分别为1 080、540、360、180、50 kg的染缸使用次数。

在生产中，为了提高生产质量，需将订单尽量分配在较大缸容染缸里加工一次，避免在较小缸容染缸里加工多次而出现色差问题，在此引入利用率折扣率ρ，用来降低订单在较小缸容资源的使用频率和效率。同时，为了将所有染缸投入生产，降低染缸闲置率，引入等待加工利用率折扣率g，用来降低订单因排队等待加工的染缸资源有效利用率，使订单优先分配到运作次数较少的染缸加工。ρ与g的取值范围都为（0，1）。本研究选取一组染缸容量为1 080、540、360、180、50 kg，相应机台数矩阵X=[x1,x2,x3,x4,x5]，x1、x2、x3、x4、x5分别表示缸容为1 080、540、360、180、50 kg的现有机台数。在此，定义以下两个有效染缸资源利用率函数：

（1）在加工第p个订单Np时，各染缸不满负荷工作时染缸资源的有效利用率函数：

（2）在加工第p个订单Np时，各染缸满负荷工作时染缸资源的有效利用率函数为：

其中，λ1、λ2、λ3、λ4、λ5表示剩余订单量在缸容为1 080、540、360、180、50 kg的染缸中不满负荷工作时的染缸利用率。H矩阵为加工到各阶段各类缸容染缸使用次数累计矩阵。将该算法经Matlab编译并对大量订单进行染缸资源配置，结果显示，对于ρ和g的大小，若侧重于订单组质量问题，应将订单尽量分配到大染缸中加工，减少加工次数，较好的系数取值范围为0.80≤ρ≤0.85，0.90＜g≤1.00；若侧重于单组加工时间问题，应尽快加工订单，缩短订单排队等待加工时间，较好的系数取值范围为0.80≤g≤0.85，0.90＜ρ≤1.00。

在染缸资源配置自动机模型中，每个订单的每种加工方式都可以用一个事件串表示。将每个染缸工作一次视为一个事件，对订单的染缸配置过程按事件串长度划分阶段，在每个阶段设定染缸资源利用率为决策函数，并建立各个阶段之间染缸资源利用率的递推关系，最后以所用染缸的有效平均资源利用率最大为目标函数寻找订单最优排缸策略。现有一订单组质量分别为860、350、670、1 150、1 200、2 150 kg，将此订单组分别用本研究所提算法与计划员进行染缸资源配置，结果如表1所示。

表1 本研究所提算法的排缸结果

分析表1可知，在基于折扣系数ρ和g的订单组染缸资源配置结果中，整个订单组的加工周期：

人工加工周期：

由以上计算分析可知，在基于系数ρ和g的订单染缸配置结果中，订单组为2个加工周期，与人工配置结果相比缩短了1个加工周期，且染缸资源利用率明显提高。

3 结语

本研究将资源配置系统的自动机模型及动态规划最优染缸配置方式应用于实际订单的染缸资源配置中，配置结果与印染企业中的人工配置结果相比，各染缸闲置率较低，订单组加工周期缩短，染缸利用率大幅提高，这对年产值数亿元的印染企业来说意义深远。折扣系数的取值范围是结合实验测试及人工经验选择的，有待进一步测定。