基于離散事件動(dòng)態(tài)系統(tǒng)的染缸資源配置優(yōu)化方法研究

余 婷，何經(jīng)旺，林 勵(lì)，王子玥玥

（福建信息職業(yè)技術(shù)學(xué)院，福建 福州 350003）

目前，國內(nèi)的印染企業(yè)仍對(duì)生產(chǎn)訂單進(jìn)行人工染缸資源配置，企業(yè)自動(dòng)化程度與生產(chǎn)效率較低。因此，對(duì)訂單進(jìn)行合理的染缸資源配置，提高染機(jī)資源利用率，對(duì)印染企業(yè)具有重要意義。李可彪等[1]根據(jù)企業(yè)生產(chǎn)計(jì)劃流程建立了以投入生產(chǎn)染缸空閑量最少為目標(biāo)、以有限生產(chǎn)資源為約束的染缸生產(chǎn)排缸模型。莫豐勇[2]則針對(duì)企業(yè)浸染生產(chǎn)過程中的加工設(shè)備多和調(diào)度復(fù)雜等特性，建立了一種用于浸染生產(chǎn)調(diào)度的數(shù)學(xué)模型，并用遺傳算法求解染缸配置。本研究基于福建晉江某紡織企業(yè)的染缸資源配置過程，用離散事件動(dòng)態(tài)系統(tǒng)的方法對(duì)訂單排缸過程建立模型，再用動(dòng)態(tài)規(guī)劃法尋找染缸最優(yōu)配置策略，使訂單能在較短時(shí)間內(nèi)順利加工完成并提高利用率。

1 染缸資源配置的離散事件動(dòng)態(tài)系統(tǒng)模型

1.1 離散事件動(dòng)態(tài)系統(tǒng)

離散事件動(dòng)態(tài)系統(tǒng)（Discrete Event Dynamic System，DEDS）興起于20世紀(jì)80年代，由一些有復(fù)雜交互作用的事件驅(qū)動(dòng)，系統(tǒng)狀態(tài)僅在一些離散時(shí)刻點(diǎn)隨著事件的發(fā)生而變化。形式語言/自動(dòng)機(jī)是DEDS的基本建模工具[3]。一個(gè)確定的有限狀態(tài)自動(dòng)機(jī)G為一個(gè)五元組[4]：G=(Q,∑,δ,q0,Qm)。其中，Q為有限狀態(tài)集合；∑為事件集（分可控事件集∑c和不可控事件集∑uc，且∑uc=∑/ ∑c）；δ為狀態(tài)轉(zhuǎn)移函數(shù)，即δ:Q× ∑→Q，描述系統(tǒng)由一個(gè)狀態(tài)經(jīng)給定條件轉(zhuǎn)移至新狀態(tài)的過程；q0∈Q為初始狀態(tài)；Qm∈Q為標(biāo)識(shí)狀態(tài)。若定義δ(q0,ε)=q0，且δ(q0,sσ)=δ[δ(q0,s),σ]，?σ∈∑，s∈∑*，則狀態(tài)轉(zhuǎn)移函數(shù)也可以擴(kuò)展定義至符號(hào)串集合∑*，即δ:Q× ∑→Q。對(duì)于任一初始狀態(tài)q0∈Q，自動(dòng)機(jī)G的生成語言為L(G)定義為使?fàn)顟B(tài)轉(zhuǎn)移函數(shù)δ(w,q0)有定義的輸入符號(hào)串w∈∑*的一個(gè)集，用式子表示為L(G)={s∈∑*|δ(q0,s)!}。設(shè)有一個(gè)映射f:L(G)→Γ，表示當(dāng)自動(dòng)機(jī)G產(chǎn)生事件串s時(shí)的控制輸入為f(s)，下一個(gè)發(fā)生的事件需發(fā)生在f(s)∩{σ:δ(sσ,q0)!}中，則稱f為監(jiān)控器，記f控制下的系統(tǒng)為f/G。在此，假設(shè)字符串s的長度為|s|，Lk(G)={s∈L(G)||s|=k}表示由自動(dòng)機(jī)G生成的長度為k的字符串集合。當(dāng)字符串長度|s|=k時(shí)，串s發(fā)生后，在監(jiān)控器fk的作用下，所有可能的控制輸入fk(s)可表示為fk:Lk(G)→Γ，其中，s∈Lk(G)，Γ為控制輸入集。故控制器f為一系列決策序列f=(f0,f1,f2,…)。

1.2 染缸資源配置的離散事件動(dòng)態(tài)系統(tǒng)建模

資源配置系統(tǒng)是一類典型的離散事件動(dòng)態(tài)系統(tǒng)。針對(duì)染缸資源配置系統(tǒng)，規(guī)定配置規(guī)則：任一訂單均可通過某些染缸進(jìn)行有限次的滿負(fù)荷加工及一次不滿負(fù)荷加工完成；若訂單質(zhì)量小于染缸容量，則將訂單直接分配在合適的染缸進(jìn)行生產(chǎn)；若訂單質(zhì)量大于染缸容量，則需對(duì)訂單進(jìn)行適當(dāng)拆分，將其分配到若干染缸中生產(chǎn)。

本研究考慮對(duì)l種缸容的染缸資源配置系統(tǒng)建立自動(dòng)機(jī)模型，使訂單的各種生產(chǎn)方式通過自動(dòng)機(jī)狀態(tài)轉(zhuǎn)換圖表示出來，模型G:(Q,∑,δ,q0,Qm)。其中，Q={l種染缸工作狀態(tài)的集合}，0表示染缸處于空閑狀態(tài)，1表示染缸處于滿負(fù)荷工作狀態(tài)，2表示染缸處于不滿負(fù)荷工作狀態(tài)；∑={不同缸容染缸工作事件的集合}，σi(i=1,2,…,l)表示第i種缸容的染缸滿負(fù)荷工作，βi、βj(i=1,…,l,j=1,…,l,i≠j)分別表示使第i種、第j種缸容的染缸不滿負(fù)荷工作，r表示染缸工作結(jié)束返回空閑狀態(tài)；δ:Q× ∑→Q為各種染缸工作狀態(tài)的轉(zhuǎn)移函數(shù)；表示l種染缸資源的初始狀態(tài)均處于空閑狀態(tài)；Qm為訂單順利加工完成后染缸的工作狀態(tài)。將染缸的工作視為一個(gè)事件，在自動(dòng)機(jī)模型中，訂單的任何一種加工方式均可用一個(gè)事件串表示，這些事件串的集合可用正則表達(dá)式表示：R=(σlr)*…(σlr)*(βlr+…+βlr)，其中，∑c={σl,…,σl,βl,…,βl}，∑uc={r}。

2 訂單的最優(yōu)染缸資源配置方式求解

假定各染缸滿負(fù)荷工作時(shí)利用率為100%，設(shè)有一組訂單，每個(gè)訂單的染缸分配過程按事件串長度分為n階段，定義以下5種關(guān)于染缸資源利用率的控制函數(shù)：

（1）在加工第p個(gè)訂單Np時(shí)，從第k階段到最后階段（第n階段）的染缸平均資源有效利用率函數(shù)為vk=(sk,uk)表示在第k階段，選取決策uk的染缸資源有效利用率；uk為在第k階段，當(dāng)狀態(tài)處于sk時(shí)，對(duì)剩余訂單量分配染缸資源的決策函數(shù)。待各階段決策確定后，整個(gè)訂單染缸配置過程的決策序列就構(gòu)成一個(gè)策略，用f={u1(s1),u2(s2),…,un(sn)}表示。

（3）對(duì)于訂單組中第p個(gè)訂單Np，當(dāng)選取最優(yōu)染缸配置方式后，染缸資源的實(shí)際利用率函數(shù)：Wp=Np/Mp，Np為第p個(gè)訂單的質(zhì)量，Mp為所選各染缸的容量總和。

（4）對(duì)訂單組進(jìn)行染缸資源配置后，整個(gè)訂單組加工周期符號(hào)表示對(duì)式子向上取整，P1080、P540、P360、P180、P50分別表示在染缸資源配置結(jié)果中缸容分別為1 080、540、360、180、50 kg的染缸使用次數(shù)。

在生產(chǎn)中，為了提高生產(chǎn)質(zhì)量，需將訂單盡量分配在較大缸容染缸里加工一次，避免在較小缸容染缸里加工多次而出現(xiàn)色差問題，在此引入利用率折扣率ρ，用來降低訂單在較小缸容資源的使用頻率和效率。同時(shí)，為了將所有染缸投入生產(chǎn)，降低染缸閑置率，引入等待加工利用率折扣率g，用來降低訂單因排隊(duì)等待加工的染缸資源有效利用率，使訂單優(yōu)先分配到運(yùn)作次數(shù)較少的染缸加工。ρ與g的取值范圍都為（0，1）。本研究選取一組染缸容量為1 080、540、360、180、50 kg，相應(yīng)機(jī)臺(tái)數(shù)矩陣X=[x1,x2,x3,x4,x5]，x1、x2、x3、x4、x5分別表示缸容為1 080、540、360、180、50 kg的現(xiàn)有機(jī)臺(tái)數(shù)。在此，定義以下兩個(gè)有效染缸資源利用率函數(shù)：

（1）在加工第p個(gè)訂單Np時(shí)，各染缸不滿負(fù)荷工作時(shí)染缸資源的有效利用率函數(shù)：

（2）在加工第p個(gè)訂單Np時(shí)，各染缸滿負(fù)荷工作時(shí)染缸資源的有效利用率函數(shù)為：

其中，λ1、λ2、λ3、λ4、λ5表示剩余訂單量在缸容為1 080、540、360、180、50 kg的染缸中不滿負(fù)荷工作時(shí)的染缸利用率。H矩陣為加工到各階段各類缸容染缸使用次數(shù)累計(jì)矩陣。將該算法經(jīng)Matlab編譯并對(duì)大量訂單進(jìn)行染缸資源配置，結(jié)果顯示，對(duì)于ρ和g的大小，若側(cè)重于訂單組質(zhì)量問題，應(yīng)將訂單盡量分配到大染缸中加工，減少加工次數(shù)，較好的系數(shù)取值范圍為0.80≤ρ≤0.85，0.90＜g≤1.00；若側(cè)重于單組加工時(shí)間問題，應(yīng)盡快加工訂單，縮短訂單排隊(duì)等待加工時(shí)間，較好的系數(shù)取值范圍為0.80≤g≤0.85，0.90＜ρ≤1.00。

在染缸資源配置自動(dòng)機(jī)模型中，每個(gè)訂單的每種加工方式都可以用一個(gè)事件串表示。將每個(gè)染缸工作一次視為一個(gè)事件，對(duì)訂單的染缸配置過程按事件串長度劃分階段，在每個(gè)階段設(shè)定染缸資源利用率為決策函數(shù)，并建立各個(gè)階段之間染缸資源利用率的遞推關(guān)系，最后以所用染缸的有效平均資源利用率最大為目標(biāo)函數(shù)尋找訂單最優(yōu)排缸策略。現(xiàn)有一訂單組質(zhì)量分別為860、350、670、1 150、1 200、2 150 kg，將此訂單組分別用本研究所提算法與計(jì)劃員進(jìn)行染缸資源配置，結(jié)果如表1所示。

表1 本研究所提算法的排缸結(jié)果

分析表1可知，在基于折扣系數(shù)ρ和g的訂單組染缸資源配置結(jié)果中，整個(gè)訂單組的加工周期：

人工加工周期：

由以上計(jì)算分析可知，在基于系數(shù)ρ和g的訂單染缸配置結(jié)果中，訂單組為2個(gè)加工周期，與人工配置結(jié)果相比縮短了1個(gè)加工周期，且染缸資源利用率明顯提高。

3 結(jié)語

本研究將資源配置系統(tǒng)的自動(dòng)機(jī)模型及動(dòng)態(tài)規(guī)劃最優(yōu)染缸配置方式應(yīng)用于實(shí)際訂單的染缸資源配置中，配置結(jié)果與印染企業(yè)中的人工配置結(jié)果相比，各染缸閑置率較低，訂單組加工周期縮短，染缸利用率大幅提高，這對(duì)年產(chǎn)值數(shù)億元的印染企業(yè)來說意義深遠(yuǎn)。折扣系數(shù)的取值范圍是結(jié)合實(shí)驗(yàn)測試及人工經(jīng)驗(yàn)選擇的，有待進(jìn)一步測定。