染缸資源的離散事件動(dòng)態(tài)系統(tǒng)建模及優(yōu)化

余婷，王飛，汲洋弘康

（華僑大學(xué)信息科學(xué)與工程學(xué)院，福建廈門361021）

染缸資源的離散事件動(dòng)態(tài)系統(tǒng)建模及優(yōu)化

余婷，王飛，汲洋弘康

（華僑大學(xué)信息科學(xué)與工程學(xué)院，福建廈門361021）

根據(jù)印染企業(yè)訂單排缸生產(chǎn)計(jì)劃的實(shí)際情況，建立染缸資源配置系統(tǒng)的自動(dòng)機(jī)模型，使訂單的各種染缸配置方式映射到自動(dòng)機(jī)模型中；然后，根據(jù)模型行為演化過(guò)程，對(duì)訂單的染缸資源配置過(guò)程劃分階段，在各個(gè)階段設(shè)定性能指標(biāo)函數(shù)，并建立各階段間性能指標(biāo)函數(shù)間的遞推關(guān)系式；最后，用動(dòng)態(tài)規(guī)劃法對(duì)染缸的配置過(guò)程尋找最優(yōu)排缸策略，得到染缸資源利用率最大的配置方式.實(shí)例結(jié)果表明：與現(xiàn)有的計(jì)算機(jī)調(diào)度系統(tǒng)相比，所建立的模型和決策方法能有效地提高染缸資源的利用率.

染缸；資源配置；離散事件；動(dòng)態(tài)系統(tǒng)；自動(dòng)機(jī)；動(dòng)態(tài)規(guī)劃

對(duì)于資源配置系統(tǒng)的一系列研究成果，很大程度上依賴于離散事件動(dòng)態(tài)系統(tǒng)的迅速發(fā)展［1］.目前，對(duì)于資源配置系統(tǒng)的研究大致可分為系統(tǒng)的死鎖和優(yōu)化兩個(gè)主要問(wèn)題.基于模型的死鎖避免，在多進(jìn)程并發(fā)系統(tǒng)中的應(yīng)用得到了較好的發(fā)展.在柔性制造系統(tǒng)中，自動(dòng)機(jī)和Petri網(wǎng)是研究死鎖問(wèn)題的兩大數(shù)學(xué)工具［2］.在自動(dòng)機(jī)中，Lawley等［2］和Reveliotis等［3］提出了基于多項(xiàng)式復(fù)雜性的最優(yōu)無(wú)阻塞監(jiān)控策略來(lái)預(yù)防死鎖避免問(wèn)題.在Petri網(wǎng)中，李志武等［4］和Tricas等［5］根據(jù)Siphon理論來(lái)設(shè)計(jì)控制監(jiān)控器，避免柔性制造系統(tǒng)中的死鎖問(wèn)題.郭濤等［6］和Sampath等［7］提出了在資源配置系統(tǒng)中的控制規(guī)范改變時(shí)，用數(shù)學(xué)規(guī)劃的方法在Petri網(wǎng)模型中設(shè)計(jì)資源重構(gòu)控制器，以實(shí)現(xiàn)最優(yōu)資源配置問(wèn)題；Tezcan等［8］提出了用魯棒控制策略來(lái)優(yōu)化多服務(wù)器并行服務(wù)系統(tǒng)中的服務(wù)器分配問(wèn)題.本文基于福建晉江某印染紡織企業(yè)的訂單排缸過(guò)程，用離散事件動(dòng)態(tài)系統(tǒng)對(duì)訂單的染缸資源配置過(guò)程建立模型.

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

離散事件動(dòng)態(tài)系統(tǒng)是指由異步、突發(fā)的事件按照一定的運(yùn)行規(guī)則相互作用，導(dǎo)致系統(tǒng)狀態(tài)演化的一類動(dòng)態(tài)系統(tǒng)，實(shí)際上是一個(gè)用于生產(chǎn)產(chǎn)品或提供服務(wù)的人造系統(tǒng)，以此來(lái)滿足人類設(shè)定的一些需求［9］.資源配置系統(tǒng)是一類典型的離散事件動(dòng)態(tài)系統(tǒng)，通常由一系列的異步、并發(fā)或有序的過(guò)程一起構(gòu)成［6］.它的每個(gè)配置過(guò)程可能需要多種資源并且服從人為設(shè)定的一些復(fù)雜規(guī)則，而這些規(guī)則無(wú)法用傳統(tǒng)的差微分方程來(lái)描述.用離散事件系統(tǒng)能夠更好地對(duì)染缸資源配置系統(tǒng)建立模型及分析其行為性能［10］.

離散事件動(dòng)態(tài)系統(tǒng)的行為一般以自動(dòng)機(jī)G的生成語(yǔ)言L（G）＝｛s∈Σ＊｜δ（x0，s）?。硎?假設(shè)字符串s長(zhǎng)度為｜s｜，Lk（G）＝｛s∈L（G）｜｜s｜＝k｝表示由自動(dòng)機(jī)G生成的長(zhǎng)度為k的字符串集合.當(dāng)字符串長(zhǎng)度｜s｜＝k時(shí)，則串s發(fā)生后，在控制器fk作用下，所有可能的控制輸入fk（s）可表示為fk∶L（k）（G）→Γ.其中：s∈L（k）（G）；Γ為控制輸入集.因此，控制器f即為一系列決策序列f＝（f0，f1，f2，…）.

2 染缸資源配置系統(tǒng)數(shù)學(xué)模型的建立

圖1 染缸資源配置的自動(dòng)機(jī)模型Fig.1 Automata model for the resource allocation of dye vats

染缸資源配置系統(tǒng)是一種常見(jiàn)的離散事件動(dòng)態(tài)系統(tǒng).在此，將利用自動(dòng)機(jī)對(duì)染缸資源配置系統(tǒng)建立數(shù)學(xué)模型.在模型中，訂單的各種生產(chǎn)方式可以用自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換圖表示出來(lái).文中，將考慮對(duì)l種缸容的染缸資源配置系統(tǒng)建立自動(dòng)機(jī)模型，如圖1所示.模型G可表示為

在染缸資源配置系統(tǒng)的自動(dòng)機(jī)模型中，先需定義訂單的排缸規(guī)則：當(dāng)訂單的質(zhì)量不能用單一染缸完成加工時(shí)，這時(shí)就需要對(duì)訂單做拆分.即一部分可以用某些染缸滿負(fù)荷工作有限次，另外一部分用某一種染缸不滿負(fù)荷工作一次，以此來(lái)順利完成訂單的加工.因此，對(duì)任何一個(gè)訂單，它都可以通過(guò)種染缸進(jìn)行有限次的滿負(fù)荷工作和某種染缸進(jìn)行一次的不滿負(fù)荷工作來(lái)完成.在自動(dòng)機(jī)模型中，訂單的任何一種染缸配置方式都可以用一個(gè)事件串表示，且這些事件串集合可用正則表達(dá)式表示為

3 訂單的最優(yōu)染缸資源配置

假定所有染缸工作事件發(fā)生后的染缸資源利用率均為正，染缸滿負(fù)荷工作時(shí)的資源利用率為100%.在此，設(shè)一個(gè)訂單的染缸分配過(guò)程按事件串長(zhǎng)度分為n階段，定義如下4種關(guān)于染缸資源利用率的控制函數(shù).

1）訂單加工過(guò)程中，從第k階段到最后階段（第n階段）的染缸平均資源利用率函數(shù) .其表達(dá)式為

其中：vj（sj，uj）表示在第j階段，選取決策uj的染缸資源利用率；uk為在第k階段時(shí)，當(dāng)狀態(tài)處于sk時(shí)，對(duì)剩余訂單量分配染缸資源的決策函數(shù).待各階段決策確定后，整個(gè)訂單染缸配置過(guò)程的決策序列就構(gòu)成一個(gè)策略，用f＝｛u1（s1），u2（s2），…，un（sn）｝表示.

2）最優(yōu)化函數(shù)，表示訂單順利加工完成后的染缸資源利用率最大.其表達(dá)式為

在實(shí)際生產(chǎn)當(dāng)中，為使訂單能夠盡量分配在較大缸容的染缸里加工一次，避免在較小缸容的染缸里加工多次而導(dǎo)致布出現(xiàn)的色差問(wèn)題，提高布的質(zhì)量.因此在這里引入利用率折扣率ρ，來(lái)減小訂單在較小缸容資源的使用頻率和效率，折扣率的取值范圍為ρ∈（0，1）.

3）染缸滿負(fù)荷工作時(shí)的染缸資源利用率函數(shù)，其表達(dá)式為

4）染缸不滿負(fù)荷工作時(shí)的染缸資源利用率函數(shù)，其表達(dá)式為

企業(yè)生命周期理論認(rèn)為，處于不同生命周期階段的企業(yè)有著不同的競(jìng)爭(zhēng)狀況和財(cái)務(wù)特征。對(duì)于初創(chuàng)期企業(yè)，外部投資者的關(guān)注重點(diǎn)是企業(yè)產(chǎn)品或技術(shù)的核心競(jìng)爭(zhēng)力以及未來(lái)的發(fā)展空間，而此階段的企業(yè)碳信息披露情況不會(huì)成為外部投資者關(guān)注的重點(diǎn)。據(jù)此，提出假設(shè)2。

其中：λ1，λ2，λ3，λ4分別表示剩余訂單量在缸容為540，360，180，50kg的染缸中不滿負(fù)荷工作時(shí)的染缸利用率.

在染缸資源配置的自動(dòng)機(jī)模型中，任何一個(gè)訂單的任何一種加工方式都可以用一個(gè)事件串表示.每個(gè)染缸工作一次視為一個(gè)事件.對(duì)訂單的染缸配置過(guò)程按事件串長(zhǎng)度劃分階段，在每個(gè)階段設(shè)定染缸資源的利用率為決策函數(shù)，并構(gòu)造各個(gè)階段之間染缸資源利用率的遞推關(guān)系.最后，以所用染缸的最大平均資源利用率為目標(biāo)函數(shù)尋找訂單的最優(yōu)排缸策略.

4 實(shí)例分析

圖2 訂單質(zhì)量為810kg的染缸自動(dòng)機(jī)模型圖Fig.2 Automata model of dye vats for the order weight of 810kg

現(xiàn)有一組訂單，其質(zhì)量分別為810，80，860，410，670，800，685，785，530，655，1 150，2 350，1 450，530，390kg，缸容為50，180，360，540kg的染缸各一臺(tái)，折扣率為ρ＝0.95，求此組訂單的最優(yōu)染缸資源配置方式，使得染缸資源的利用率最大.以訂單質(zhì)量為810kg的染缸資源配置為例，其自動(dòng)機(jī)模型如圖2所示.

按照動(dòng)態(tài)規(guī)劃的方法，從最后一個(gè)階段開(kāi)始計(jì)算，計(jì)算過(guò)程從略.

1）當(dāng)k＝n時(shí)，經(jīng)計(jì)算有

2）當(dāng)k＝n－1時(shí)，經(jīng)計(jì)算有

4）當(dāng)k＝n－3時(shí)，經(jīng)計(jì)算有

以訂單順利加工完成為終止階段.由以上各種配置方式中，可知整個(gè)配置過(guò)程中最長(zhǎng)階段為4個(gè)階段，故n＝4.

取訂單的染缸資源利用率為最大，其配置方式為

據(jù)此可知訂單質(zhì)量為810kg的染缸資源最佳配置策略：一個(gè)缸容為360kg的染缸滿負(fù)荷工作一次和一個(gè)缸容為540kg的染缸不滿負(fù)荷工作一次.用自動(dòng)機(jī)的生成語(yǔ)言可表示為

其中：f為染缸資源最優(yōu)配置策略.

表1 不同缸容下兩種系統(tǒng)的排缸結(jié)果Tab.1 Result of the two arranging ways of the dye vat for orders

由表1可知：所研究的動(dòng)態(tài)規(guī)劃尋找訂單的最優(yōu)排缸策略具有一定的有效性.

5 結(jié)束語(yǔ)

文中將資源配置系統(tǒng)的自動(dòng)機(jī)模型及動(dòng)態(tài)規(guī)劃尋最優(yōu)染缸配置方式應(yīng)用到實(shí)際訂單的排缸過(guò)程中，其排缸結(jié)果與目前印染企業(yè)中普遍采用的計(jì)算機(jī)調(diào)度系統(tǒng)的排缸結(jié)果相比，染缸資源利用率有了一定的提高.然而，染缸的資源是有限的，當(dāng)訂單的數(shù)量多時(shí)，會(huì)使一些訂單集中在某些缸容的染缸排隊(duì)等待加工，而其他缸容的染缸卻是處于空閑狀態(tài) .因此，如何使所有染缸同時(shí)工作，減少訂單的排隊(duì)等待時(shí)間有待于進(jìn)一步的研究.

［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，F(xiàn)ERREIRA 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］ 徐國(guó)華，胡奇英.離散事件動(dòng)態(tài)系統(tǒng)的監(jiān)控方法［M］.鄭州：河南科學(xué)技術(shù)出版社，1996：1－10.

［11］ 鄭大忠，趙千川.離散事件動(dòng)態(tài)系統(tǒng)［M］.北京：清華大學(xué)出版社，2001：282－340.

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

YU Ting，WANG Fei，JI Yang－h(huán)ong－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

（責(zé)任編輯：黃曉楠 英文審校：吳逢鐵）

1000－5013（2014）01－0031－05

10.11830／ISSN.1000－5013.2014.01.0031

2013－06－04

王飛（1977－），男，副教授，主要從事離散事件動(dòng)態(tài)系統(tǒng)控制、資源優(yōu)化配置的研究.E－mail：feiw545＠163.com.

國(guó)家自然科學(xué)基金資助項(xiàng)目（61203040）；福建省自然科學(xué)基金資助項(xiàng)目（2011J01532）