染缸資源的離散事件動態系統建模及優化

余婷，王飛，汲洋弘康

（華僑大學信息科學與工程學院，福建廈門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）