基于Petri網(wǎng)行為輪廓的超市自助結(jié)賬系統(tǒng)優(yōu)化分析

魏瑤

摘 要：本研究對(duì)超市自助結(jié)賬系統(tǒng)進(jìn)行建模并對(duì)模型進(jìn)行優(yōu)化，以達(dá)到使模型更具有實(shí)用性的目的，首先對(duì)自助結(jié)賬系統(tǒng)進(jìn)行建模，在保證行為合理的基礎(chǔ)上，通過(guò)增加相應(yīng)的結(jié)構(gòu)變遷，再利用行為輪廓的相關(guān)理論和性質(zhì)，對(duì)原自助結(jié)賬系統(tǒng)模型進(jìn)行優(yōu)化，以提高其實(shí)用性，縮短結(jié)賬時(shí)間，并通過(guò)HIPS仿真軟件進(jìn)行模擬運(yùn)行證明了優(yōu)化模型的可行性。

關(guān)鍵詞：Petri網(wǎng);行為輪廓;自助結(jié)賬;優(yōu)化;HIPS

中圖分類號(hào)：TP391.9? 文獻(xiàn)標(biāo)識(shí)碼：A? 文章編號(hào)：1673-260X（2021）02-0010-03

0 引言

新型冠狀病毒的爆發(fā)已經(jīng)給人們的日常生活方式帶來(lái)了很大的影響，隨著疫情下人們對(duì)無(wú)接觸支付模式的深入了解，無(wú)接觸的超市自助結(jié)賬模式也得到了廣大消費(fèi)者的接受，自助收銀機(jī)成為人們?cè)诔匈?gòu)物付款時(shí)的新選擇。為了提高系統(tǒng)的工作效率，現(xiàn)對(duì)自助結(jié)賬系統(tǒng)進(jìn)行建模優(yōu)化，利用Petri網(wǎng)的相關(guān)性質(zhì)[1]和行為輪廓的相關(guān)知識(shí)[2]可以解決很多問(wèn)題。

如何實(shí)現(xiàn)業(yè)務(wù)流程的優(yōu)化是當(dāng)今熱門(mén)研究課題，目前國(guó)內(nèi)外許多學(xué)者在該方面做了大量研究。邵叱風(fēng)提出了一種利用Java編程實(shí)現(xiàn)算數(shù)計(jì)算Petri網(wǎng)動(dòng)態(tài)模型的模擬，驗(yàn)證了Petri網(wǎng)的模擬能力[3]，同時(shí)提出一種日志挖掘方法，利用日志除標(biāo)簽外的屬性輔助發(fā)現(xiàn)過(guò)程模型[4]，另外提出了一種基于過(guò)程挖掘的結(jié)構(gòu)優(yōu)化方法，通過(guò)過(guò)程挖掘得到模型，再改造關(guān)聯(lián)結(jié)構(gòu)提高流程運(yùn)行效率[5];應(yīng)麗等人利用行為輪廓增加相關(guān)的控制結(jié)構(gòu)對(duì)模型進(jìn)行優(yōu)化，并通過(guò)分析說(shuō)明了流程模型優(yōu)化的有效性[6]。KHAN G等人為了解決服務(wù)組成和調(diào)度活動(dòng)面臨的性能和復(fù)雜性問(wèn)題，在Petri網(wǎng)的基礎(chǔ)上，利用模型和可達(dá)圖的概念，對(duì)安全性、有界性和公平性等進(jìn)行了形式化分析[7]。

本文以基于Petri網(wǎng)行為輪廓的超市自助結(jié)賬系統(tǒng)優(yōu)化為例，幫助顧客在超市購(gòu)物時(shí)可以用更短的時(shí)間完成支付。本文結(jié)構(gòu)如下，第一部分介紹Petri網(wǎng)的基本概念，第二部分對(duì)基于Petri網(wǎng)的自助結(jié)賬系統(tǒng)模型進(jìn)行分析，并給出了優(yōu)化后的模型，第三部分將優(yōu)化后的模型通過(guò)HIPS[6]仿真軟件進(jìn)行模擬運(yùn)行，對(duì)優(yōu)化后的模型的結(jié)構(gòu)和行為進(jìn)行分析。第四部分總結(jié)了本篇文章。

1 相關(guān)定義

定義1[2]（流程模型Petri網(wǎng)） 一個(gè)流程模型Petri網(wǎng)PM=（P，T，F(xiàn)，C，s，e）是一個(gè)六元組，滿足下列條件：

（1）P是有限庫(kù)所集，T是有限活動(dòng)變遷集;

（2）P≠？覫，T≠？覫且P∩T≠？覫;

（3）F？哿（P×T）∪（T×P）表示PN的流關(guān)系且（P∪T）是強(qiáng)連通圖;

（4）dom（F）∪cod（F）=P∪T，其中

dom（F）{x∈P∪T|？堝y∈P∪T，（x，y∈）}

cod（F）{x∈P∪T|？堝y∈P∪T，（y，x∈）};

（5）C={and，xor，or}是流程網(wǎng)的結(jié)構(gòu)類型;

（6）M0是網(wǎng)的初始標(biāo)識(shí)，Mi是網(wǎng)的終止標(biāo)識(shí)，且Mi是死標(biāo)識(shí);

（7）s∈T是活動(dòng)開(kāi)始的變遷，e∈T是活動(dòng)終止的變遷.

則稱該網(wǎng)為流程模型Petri網(wǎng)。在此定義上，我們定義了網(wǎng)的前集和網(wǎng)的后集。

定義2[1]（變遷發(fā)生規(guī)則） 一個(gè)四元組PN=（P，T;F，M0）稱為Petri網(wǎng)，并具有下面的變遷發(fā)生規(guī)則：

變遷t∈T具有發(fā)生權(quán)，當(dāng)且僅當(dāng)對(duì)？坌p∈t：M（p）≥1，記作M[t>;

在標(biāo)識(shí)M下能使得變遷t經(jīng)發(fā)生后，得到一個(gè)新的標(biāo)識(shí)M′，記作M[t>M′，則有

M′（P）=M（P）+1，若p∈t-′tM（P）-1，若p∈′t-tM（P），其他

定義3[1]（可達(dá)性） 已知Petri網(wǎng)PN=（P，T;F，C），如果存在t∈T，使[t>M′，則稱M′為從M直接可達(dá)的。如果存在變遷序列t1，t2，…，tk和標(biāo)識(shí)序列M1，M2，…，Mk使得M[t1>M1[t2>M2…Mk-1[tk>Mk，則稱Mk為從M可達(dá)的。從M可達(dá)的一切標(biāo)識(shí)的集合，記為R（M）。

定義4[2]（行為輪廓） 設(shè)有網(wǎng)PN=（P，T，F(xiàn)，C），初始標(biāo)識(shí)為M0，對(duì)任意給定的變遷滿足下列關(guān)系：

（1）若t1？酆t2且t2，則稱t1和t2為嚴(yán)格序關(guān)系，記作t1→t2;

（2）若且t2？酆t1，則稱t1和t2為嚴(yán)格逆序關(guān)系，記作t1→-1t2;

（3）若且，則稱t1和t2為排他序關(guān)系，記作t1+t2;

（4）若t1？酆t2且t2？酆t1，則稱t1和t2為交叉序關(guān)系，記作t1‖t2.

2 超市自助結(jié)賬系統(tǒng)的建模優(yōu)化分析

2.1 問(wèn)題描述

隨著疫情下無(wú)接觸支付模式的發(fā)展，以及緩解傳統(tǒng)人工結(jié)賬方式存在的在高峰期排隊(duì)時(shí)間久的問(wèn)題，越來(lái)越多的超市等大型零售場(chǎng)所開(kāi)始推行消費(fèi)者自助結(jié)賬系統(tǒng)，由顧客自行掃描所購(gòu)商品條碼，由超市系統(tǒng)核對(duì)信息并計(jì)算總金額，顧客掃碼支付。如果按照單次商品分別查找，審核和計(jì)算金額，會(huì)浪費(fèi)很多時(shí)間。現(xiàn)通過(guò)Petri網(wǎng)對(duì)自助結(jié)賬系統(tǒng)進(jìn)行建模優(yōu)化，可以解決這一問(wèn)題，提高系統(tǒng)的工作效率。

2.2 模型提出

圖1為單件商品的超市自助結(jié)賬系統(tǒng)，由圖可知：從顧客挑選商品開(kāi)始，t1，t2發(fā)生，然后由顧客掃描商品條碼，在超市系統(tǒng)提供的商品信息庫(kù)中識(shí)別商品，引發(fā)t3發(fā)生，t1和t3，t2和t3滿足嚴(yán)格序關(guān)系，然后t4，t5，t6，t7發(fā)生，由超市系統(tǒng)審核商品的重量與商品信息庫(kù)中重量是否一致，避免發(fā)生顧客掃描低價(jià)商品后更換高價(jià)商品的情況，并產(chǎn)生一個(gè)排他關(guān)系，記作t8+t9，若t9發(fā)生，則系統(tǒng)結(jié)束運(yùn)行，結(jié)賬失敗;若t8發(fā)生，則t10，t11，t12，t13繼續(xù)發(fā)生，系統(tǒng)核算金額，進(jìn)入付款界面，產(chǎn)生兩種付款模式t14， t15，它們是一個(gè)排他關(guān)系，記作t14+t15;接下來(lái)t16發(fā)生，也產(chǎn)生兩種情況，若超時(shí)未付款，則t18，t19發(fā)生，交易失敗;若系統(tǒng)收到付款，則t17，t21，t22發(fā)生，交易成功。該模型表示單件商品的結(jié)賬流程，若購(gòu)買(mǎi)商品數(shù)量較多，則會(huì)消耗較多時(shí)間。因此，考慮在系統(tǒng)中加入相應(yīng)的結(jié)構(gòu)變遷，以實(shí)現(xiàn)循環(huán)，提高效率。

2.3 模型優(yōu)化

針對(duì)圖1的模型進(jìn)行優(yōu)化時(shí)，考慮加入合適的結(jié)構(gòu)變遷，以形成循環(huán)，所建優(yōu)化模型如圖2所示，在原模型基礎(chǔ)上，增加了變遷t24，使得系統(tǒng)可以在審核完第一件商品后，繼續(xù)循環(huán)審核第二件，最后將金額累計(jì)，可以節(jié)約時(shí)間，提高系統(tǒng)工作效率。

3 仿真軟件模擬運(yùn)行

我們通過(guò)HIPS[6]仿真軟件進(jìn)行模擬運(yùn)行，對(duì)優(yōu)化后的模型的結(jié)構(gòu)和行為進(jìn)行分析，如圖3和圖4所示。

使用CPNtools對(duì)優(yōu)化前后后的模型執(zhí)行時(shí)間進(jìn)行分析，默認(rèn)每個(gè)變遷執(zhí)行耗時(shí)為1，商品數(shù)量為1-10。仿真實(shí)驗(yàn)結(jié)果表明，優(yōu)化后的自助結(jié)賬系統(tǒng)的Petri網(wǎng)模型是可行的（如圖5所示），相較于優(yōu)化前結(jié)賬耗時(shí)明顯降低（如圖6所示）。

仿真實(shí)驗(yàn)表明，優(yōu)化后的自助結(jié)賬系統(tǒng)的Petri網(wǎng)模型是可行的，相較于優(yōu)化前結(jié)賬耗時(shí)明顯降低。

4 結(jié)語(yǔ)

本文構(gòu)建了基于Petri網(wǎng)構(gòu)建的超市自助結(jié)賬系統(tǒng)流程模型，運(yùn)用Petri網(wǎng)的可達(dá)性并分析其行為輪廓，根據(jù)Petri網(wǎng)流程模型運(yùn)行規(guī)則，通過(guò)添加相關(guān)的控制結(jié)構(gòu)，得到優(yōu)化的目標(biāo)模型。優(yōu)化后的模型從一定程度上縮短了時(shí)間，提高了系統(tǒng)的工作效率。但是不同超市的系統(tǒng)會(huì)有所不同，所以本文在一定程度上具有局限性，今后可以結(jié)合更多的超市付款流程，對(duì)流程進(jìn)行進(jìn)一步的優(yōu)化和改進(jìn)，提高模型的適用性。

——————————

參考文獻(xiàn)：

〔1〕吳哲輝.Petri網(wǎng)導(dǎo)論[M].北京：機(jī)械工業(yè)出版社，2006.6-22.

〔2〕方賢文.Petri網(wǎng)行為輪廓理論及其應(yīng)用[M].上海：上海交通大學(xué)出版社，2017.39-40.

〔3〕邵叱風(fēng).基于流程挖掘的并行優(yōu)化算法[J].赤峰學(xué)院學(xué)報(bào)（自然科學(xué)版），2019，35（10）：66-70.

〔4〕應(yīng)麗，王麗麗，劉祥偉.基于Petri網(wǎng)的門(mén)診就醫(yī)流程模型優(yōu)化分析[J].延邊大學(xué)學(xué)報(bào)（自然科學(xué)版），2018，44（01）：79-82.

〔5〕KHAN G， SARKAR A， SENGUPTA S. Behavioral Analysis of Service Composition Patterns in ECBS Using Petri-Net-Based Approach[M]//Advanced Computing and Systems for Security. Springer， Singapore， 2020： 53-66.

〔6〕HARIE Y， MITSUI Y， FUJIMORI K， et al. HiPS： Hierarchical Petri Net design， simulation， verification and model checking tool[C]//2017 IEEE 6th Global Conference on Consumer Electronics （GCCE）. IEEE， 2017： 1-5.