協(xié)同虛擬樣機(jī)的工作流時(shí)間管理研究＊

田豐春

（南京曉莊學(xué)院數(shù)學(xué)與信息技術(shù)學(xué)院，江蘇 南京 211171）

1 引言

協(xié)同虛擬樣機(jī)技術(shù)是在分布式的環(huán)境下，多領(lǐng)域?qū)＜覅f(xié)同建立和應(yīng)用虛擬樣機(jī)的方法和技術(shù)。它是一種基于一體化產(chǎn)品和過程開發(fā)IPPD（Integrated Product and Process Development）思想的新的設(shè)計(jì)／開發(fā)范例，其核心是IPT（Integrated Product Team）的實(shí)施，能夠?qū)崿F(xiàn)分布在不同地點(diǎn)、不同部門的IPPD 小組成員圍繞逼真的虛擬樣機(jī)，從不同角度、不同需求出發(fā)，對(duì)虛擬樣機(jī)進(jìn)行測試、仿真和評(píng)價(jià)，從而改進(jìn)和完善其設(shè)計(jì)、縮短產(chǎn)品的開發(fā)時(shí)間［1］。為了提高虛擬樣機(jī)設(shè)計(jì)效率，支持協(xié)同設(shè)計(jì)的工作流管理成為了協(xié)同虛擬樣機(jī)支撐平臺(tái)的重要組成部分。

工作流是一類能夠完全或者自動(dòng)執(zhí)行的經(jīng)營過程，根據(jù)一系列過程規(guī)則、文檔、信息或任務(wù)在不同的執(zhí)行者之間進(jìn)行傳遞與執(zhí)行。利用工作流技術(shù)可以描述和控制一個(gè)分布異地的多個(gè)集成化產(chǎn)品開發(fā)團(tuán)隊(duì)的動(dòng)態(tài)協(xié)同設(shè)計(jì)過程，實(shí)現(xiàn)對(duì)虛擬樣機(jī)協(xié)同設(shè)計(jì)過程全生命周期的管理，從而提高協(xié)同虛擬樣機(jī)的工作效率。

本文根據(jù)協(xié)同虛擬樣機(jī)對(duì)管理功能的需求，介紹了協(xié)同虛擬樣機(jī)中的工作流管理的各組成部分，并重點(diǎn)對(duì)工作流時(shí)間管理進(jìn)行了研究。

2 協(xié)同虛擬樣機(jī)中的工作流管理

協(xié)同虛擬樣機(jī)工程涉及多學(xué)科設(shè)計(jì)的集成技術(shù)，由各種應(yīng)用、底層支撐技術(shù)和標(biāo)準(zhǔn)組成，支持虛擬樣機(jī)的協(xié)同設(shè)計(jì)、建模和仿真。協(xié)同虛擬樣機(jī)系統(tǒng)主要由協(xié)同設(shè)計(jì)支撐平臺(tái)、模型庫（構(gòu)成產(chǎn)品、環(huán)境的各類模型）、虛擬樣機(jī)VP（Virtual Prototype）引擎和VR（Virtual Reality）／可視化環(huán)境四大部分組成。協(xié)同設(shè)計(jì)支撐平臺(tái)提供一個(gè)協(xié)同設(shè)計(jì)環(huán)境，它包括集成平臺(tái)／框架以及團(tuán)隊(duì)／組織管理、工作流管理、虛擬產(chǎn)品管理、項(xiàng)目管理等工具［2］。

工作流屬于計(jì)算機(jī)支持的協(xié)同工作的一部分，工作流管理平臺(tái)是協(xié)同虛擬樣機(jī)支撐平臺(tái)的重要組成部分，主要包括工作流定義、工作流引擎、工作流監(jiān)控和客戶端工具等組成部分，用以完成對(duì)工程項(xiàng)目任務(wù)過程的描述與運(yùn)行管理功能。

工作流管理系統(tǒng)用于定義、創(chuàng)建和管理工作流的執(zhí)行。它通過建模工具創(chuàng)建流程，流程的創(chuàng)建首先需要對(duì)項(xiàng)目進(jìn)行分解，這包括面向參與協(xié)同開發(fā)過程的某一協(xié)作群體的粗粒度劃分和面向具體開發(fā)人員的細(xì)粒度劃分。依據(jù)項(xiàng)目具體工作內(nèi)容和人員要求，將項(xiàng)目分解為不同的任務(wù)和活動(dòng)組合，組合中含有依賴、包含等各種邏輯關(guān)系。模型結(jié)構(gòu)化分析工具對(duì)創(chuàng)建的流程進(jìn)行解析和語法檢查，然后將解析后的數(shù)據(jù)存入流程數(shù)據(jù)庫。工作流引擎對(duì)流程的運(yùn)轉(zhuǎn)進(jìn)行控制，處理各種工作流數(shù)據(jù)和信息，調(diào)用外部應(yīng)用程序管理員通過監(jiān)控工具對(duì)工作流運(yùn)行過程進(jìn)行監(jiān)視和管理。用戶通過消息管理接收消息并通過工作流客戶端獲得自己的任務(wù)，同時(shí)依靠信息交互工具實(shí)現(xiàn)用戶間的協(xié)同設(shè)計(jì)開發(fā)。

3 協(xié)同虛擬樣機(jī)中的工作流時(shí)間管理

工作流時(shí)間管理是協(xié)同虛擬樣機(jī)工作流管理的關(guān)鍵部分。在工作流中，活動(dòng)結(jié)束的最遲期限稱為截止期限，若活動(dòng)實(shí)例的結(jié)束時(shí)間超過了這個(gè)最遲期限，則稱該活動(dòng)違反了此截止期限的時(shí)間約束［3］。違反工作流的截止期限會(huì)產(chǎn)生額外的負(fù)擔(dān)，增加業(yè)務(wù)成本并且浪費(fèi)系統(tǒng)的資源，并導(dǎo)致嚴(yán)重的性能損失。工作流時(shí)間管理主要研究工作流執(zhí)行的時(shí)間維計(jì)劃，估計(jì)不同的活動(dòng)執(zhí)行延遲、避免活動(dòng)／過程違反時(shí)間約束以及時(shí)間違反的異常處理，以提高過程管理的效率。

3.1 時(shí)間約束驗(yàn)證

實(shí)現(xiàn)工作流的可靠執(zhí)行、成功實(shí)施工作流管理需要對(duì)工作流模型進(jìn)行合理性驗(yàn)證與分析。常見的驗(yàn)證方法有靜態(tài)驗(yàn)證和動(dòng)態(tài)驗(yàn)證。靜態(tài)驗(yàn)證是一種事前的驗(yàn)證方法，基于所建立的工作流模型結(jié)構(gòu)，檢查過程模型與時(shí)間約束的可能沖突，修改或松弛不一致的時(shí)間約束，為工作流設(shè)計(jì)者合理設(shè)定時(shí)間約束與有效建模提供幫助。動(dòng)態(tài)驗(yàn)證是在實(shí)例執(zhí)行過程中，基于實(shí)例的當(dāng)前狀態(tài)、絕對(duì)時(shí)間與關(guān)鍵路徑，通過計(jì)算關(guān)鍵路徑的執(zhí)行延遲估算尚未調(diào)度活動(dòng)的預(yù)期執(zhí)行時(shí)間，判斷時(shí)序一致性。隨著實(shí)例執(zhí)行進(jìn)程的推進(jìn)，即便一致的期限約束也無法保證它在將來的工作流執(zhí)行中仍然滿足。為此，需要對(duì)時(shí)間約束進(jìn)行動(dòng)態(tài)或多次驗(yàn)證。

動(dòng)態(tài)的業(yè)務(wù)流程或不確定的活動(dòng)執(zhí)行時(shí)間常常破壞工作流執(zhí)行的截止期限。因此，在運(yùn)行時(shí)動(dòng)態(tài)驗(yàn)證工作流的一致性十分必要。我們可以在實(shí)例運(yùn)行過程中進(jìn)行時(shí)間監(jiān)控與仿真，監(jiān)控前序活動(dòng)的結(jié)束時(shí)間，重新計(jì)算后續(xù)活動(dòng)的完成時(shí)間，盡早預(yù)測可能的時(shí)間違反，以避免時(shí)間錯(cuò)誤和費(fèi)用增加。

3.2 關(guān)鍵路徑法

本文主要通過確定工作流關(guān)鍵路徑的方法來預(yù)測可能的時(shí)間違反。所謂工作流關(guān)鍵路徑指的是從工作流的開始節(jié)點(diǎn)到結(jié)束節(jié)點(diǎn)形成的節(jié)點(diǎn)序列中，各節(jié)點(diǎn)平均執(zhí)行時(shí)間之和最大的序列。關(guān)鍵路徑上的活動(dòng)稱為關(guān)鍵活動(dòng)［3］。如果關(guān)鍵活動(dòng)的完工時(shí)間推遲，出現(xiàn)時(shí)間違反，將導(dǎo)致成本增加。為此，需要對(duì)關(guān)鍵路徑上的活動(dòng)加強(qiáng)管理，通過優(yōu)先安排關(guān)鍵活動(dòng)所需要的資源或者為關(guān)鍵活動(dòng)分配額外資源等措施，盡量壓縮關(guān)鍵活動(dòng)的執(zhí)行時(shí)間。

工作流執(zhí)行過程由任務(wù)和條件構(gòu)成，路由決定了哪些任務(wù)需要被執(zhí)行，以什么次序執(zhí)行。圖1所示是一個(gè)包含順序結(jié)構(gòu)、AND 控制結(jié)構(gòu)、OR 控制結(jié)構(gòu)和LOOP控制結(jié)構(gòu)的網(wǎng)絡(luò)圖例子［4］。在這里我們假設(shè)活動(dòng)的服務(wù)器服務(wù)時(shí)間服從指數(shù)分布并且用戶的服務(wù)需求的到達(dá)過程服從泊松分布，因?yàn)檫@種假定本身與現(xiàn)實(shí)多數(shù)系統(tǒng)實(shí)際相符合［5］。因此，我們可以把工作流模型看成M／M／1 排隊(duì)網(wǎng)，在M／M／1隊(duì)列中，平均執(zhí)行時(shí)間為W＝1／（μλ），其中μ 是服務(wù)率，λ是到達(dá)率。

Figure 1 Example of network圖1 網(wǎng)絡(luò)圖例子

關(guān)鍵活動(dòng)的執(zhí)行時(shí)間直接影響著工作流的執(zhí)行時(shí)間，關(guān)鍵路徑法是基于工作流控制結(jié)構(gòu)和工作流實(shí)例的平均執(zhí)行時(shí)間的。網(wǎng)絡(luò)圖中，除了控制塊內(nèi)部以外，所有順序控制結(jié)構(gòu)都屬于關(guān)鍵路徑；如果控制塊內(nèi)部是循環(huán)控制結(jié)構(gòu)，則將其等價(jià)轉(zhuǎn)換為順序控制結(jié)構(gòu)；如果控制塊內(nèi)部是AND 或OR 控制結(jié)構(gòu)，則選取控制結(jié)構(gòu)中平均執(zhí)行時(shí)間最長的路徑作為子關(guān)鍵路徑。經(jīng)過變換，可以將任何一個(gè)工作流模型簡化為一個(gè)順序控制結(jié)構(gòu)。因此，整個(gè)工作流的關(guān)鍵路徑是由各個(gè)模型控制塊的子關(guān)鍵路徑構(gòu)成的。

為了識(shí)別整個(gè)工作流的關(guān)鍵路徑，需要先求出每個(gè)控制塊的子關(guān)鍵路徑。下面給出四種控制結(jié)構(gòu)的具體變換方法。

（1）順序結(jié)構(gòu)。

順序結(jié)構(gòu)中，第i個(gè)活動(dòng)的平均執(zhí)行時(shí)間是Wi＝1／（μi－λ），其中μi是服務(wù)器為第i個(gè)活動(dòng)服務(wù)時(shí)的服務(wù)率，λ是到達(dá)率。圖2所示的順序結(jié)構(gòu)的平均執(zhí)行時(shí)間是每個(gè)活動(dòng)平均執(zhí)行時(shí)間的總和：

Figure 2 Transformation of a sequence圖2 順序結(jié)構(gòu)的轉(zhuǎn)換

（2）AND 控制結(jié)構(gòu)。

圖3 所示是工作流模型的AND 控制結(jié)構(gòu)。設(shè)活動(dòng)1，2，…，n的平均執(zhí)行時(shí)間為隨機(jī)變量X1，X2，…，Xn，因?yàn)榈趇個(gè)活動(dòng)的平均執(zhí)行時(shí)間就是Wi＝1／（μi－λi），所以Xi的概率密度函數(shù)為fXi（t）＝1－e－（μi－λ）t，i＝1，…，n。

設(shè)AND控制結(jié)構(gòu)的平均執(zhí)行時(shí)間為隨機(jī)變量Y，Y 是max（X1，X2，…，Xn），其累計(jì)分布函數(shù)：

Figure 3 Transformation of an AND control structure圖3 AND 控制結(jié)構(gòu)的轉(zhuǎn)換

AND 控制結(jié)構(gòu)的平均執(zhí)行時(shí)間為：

（3）OR 控制結(jié)構(gòu)。

Figure 4 Transformation of an OR control structure圖4 OR 控制結(jié)構(gòu)的轉(zhuǎn)換

OR 控制結(jié)構(gòu)的平均執(zhí)行時(shí)間為：

（4）LOOP控制結(jié)構(gòu)。

圖5所示是工作流模型的LOOP 控制結(jié)構(gòu)。因?yàn)槊總€(gè)活動(dòng)都被認(rèn)為是獨(dú)立的M／M／1 隊(duì)列系統(tǒng)，我們可以把LOOP 控制結(jié)構(gòu)轉(zhuǎn)化為串行控制結(jié)構(gòu)。因?yàn)長OOP控制結(jié)構(gòu)的到達(dá)率Λ 是它的原始到達(dá)率λ 和它的回饋到達(dá)率（1－p）Λ 之和。LOOP控制結(jié)構(gòu)的到達(dá)率為Λ＝λ＋（1－p）Λ，從而得到Λ＝λ／p。

Figure 5 Transformation of an LOOP control structure圖5 LOOP控制結(jié)構(gòu)的轉(zhuǎn)換

LOOP控制結(jié)構(gòu)的平均執(zhí)行時(shí)間為：

3.3 工作流松弛時(shí)間分配方法

經(jīng)過上述變換，任何一個(gè)工作流模型最終都能轉(zhuǎn)換成一個(gè)順序控制結(jié)構(gòu)，從而可確定工作流的關(guān)鍵路徑。在給定整個(gè)工作流的截止期限后，便可以計(jì)算出每個(gè)活動(dòng)的截止期限。工作流的松弛時(shí)間是指工作流截止期限與工作流關(guān)鍵路徑的平均執(zhí)行時(shí)間之差。已完成活動(dòng)的松弛時(shí)間是指該活動(dòng)的截止期限與實(shí)際執(zhí)行時(shí)間之差。未執(zhí)行活動(dòng)的松弛時(shí)間是指該活動(dòng)的截止期限與平均執(zhí)行時(shí)間之差。每個(gè)活動(dòng)的松弛時(shí)間越多，工作流最終在指定時(shí)間內(nèi)完成的可能性越大。

活動(dòng)的實(shí)際完成時(shí)間與其靜態(tài)分配的截止期限有滿足和不滿足兩種狀態(tài)。如果已完成活動(dòng)呈滿足狀態(tài)，該活動(dòng)就會(huì)將自身剩余的松弛時(shí)間按關(guān)鍵路徑的平均執(zhí)行時(shí)間的比例分配到該活動(dòng)的后續(xù)活動(dòng)中，那么每個(gè)后續(xù)活動(dòng)分得的松弛時(shí)間就會(huì)增加；如果已完成活動(dòng)執(zhí)行超時(shí)，導(dǎo)致無法滿足時(shí)間約束，呈不滿足狀態(tài)，此時(shí)應(yīng)進(jìn)入異常處理程序進(jìn)行時(shí)間違反的處理。常見的異常處理方式有選擇執(zhí)行最好條件分支、放棄可忽略活動(dòng)、選擇較短可替換分支、分配額外的資源等。

工作流中，建模和流程剛開始運(yùn)行時(shí)，很難給出某些時(shí)間約束的準(zhǔn)確狀態(tài)，不能簡單用滿足或不滿足來描述這些復(fù)雜的情況，而異常觸發(fā)頻率較高會(huì)導(dǎo)致流程執(zhí)行細(xì)致程度的下降、運(yùn)行效率的降低和成本的增加。因此，有必要引入一種中間狀態(tài)，即弱不滿足狀態(tài)，將部分不滿足的時(shí)間約束轉(zhuǎn)化為中間狀態(tài)，經(jīng)過調(diào)整，弱不滿足狀態(tài)的時(shí)間約束可以轉(zhuǎn)化至可滿足狀態(tài)或者仍為不滿足狀態(tài)，這樣可以減少不滿足時(shí)間約束的數(shù)量，降低異常發(fā)生頻率，提高運(yùn)行效率。

隨著工作流程的運(yùn)行，每個(gè)活動(dòng)分得的松弛時(shí)間是動(dòng)態(tài)變化著的，已完成活動(dòng)若在分配的時(shí)間內(nèi)完成，它的剩余松弛時(shí)間將按關(guān)鍵路徑的平均執(zhí)行時(shí)間的比例分配到該活動(dòng)的后續(xù)活動(dòng)中，使未完成活動(dòng)具備更多的松弛時(shí)間。下一個(gè)活動(dòng)如果也在分配的時(shí)間內(nèi)完成，每個(gè)活動(dòng)完成后的剩余時(shí)間又會(huì)匯聚到時(shí)間約束的松弛時(shí)間中。最終，隨著工作流的運(yùn)行，在活動(dòng)完成及時(shí)率較高的情況下，某些原本處于弱不滿足狀態(tài)的時(shí)間約束可以達(dá)到可滿足狀態(tài)。

已完成活動(dòng)若在分配的時(shí)間內(nèi)完成，它的剩余松弛時(shí)間將按關(guān)鍵路徑的平均執(zhí)行時(shí)間的比例分配到該活動(dòng)的后續(xù)活動(dòng)中。松弛時(shí)間分配方法如下：

4 結(jié)束語

協(xié)同虛擬樣機(jī)工程中的工作流管理是協(xié)同支撐平臺(tái)的重要組成部分，支持和控制分布異地的多個(gè)開發(fā)團(tuán)隊(duì)的動(dòng)態(tài)協(xié)同設(shè)計(jì)過程，實(shí)現(xiàn)對(duì)虛擬樣機(jī)協(xié)同設(shè)計(jì)過程的有效管理。本文重點(diǎn)對(duì)工作流時(shí)間管理進(jìn)行了研究，通過對(duì)路由結(jié)構(gòu)的分析，采取松弛時(shí)間分配方法，調(diào)整部分弱不滿足時(shí)間約束至可滿足狀態(tài)，使更多的工作流實(shí)例滿足截止期限，降低異常的觸發(fā)頻率，節(jié)省了處理開銷，提高了運(yùn)行效率。

［1］Zhu Yao－qin，Wu Hui－zhong，Yang Yong.Research on information integration of collaborative virtual prototype［J］.Computer Simulation，2004，21（12）：136－138.（in Chinese）

［2］Li Bo－h(huán)u，Chai X－dong，Xiong Guang－leng，et al.Research and primary practice on virtual prototyping engineering of complex product［J］.Journal of System Simulation，2002，14（3）：336－341.（in Chinese）

［3］Tang Da，Liu Dan－ni.Method for dynamic verification of activity deadlines in timed workflow［J］.Computer Integrated Manufacturing Systems，2004，10（9）：1154－1159.（in Chinese）

［4］Son J H，Kim J H，Kim M H.Deadline allocation in a timeconstrained workflow［J］.International Journal of Cooperative Information Systems，2001，10（4）：509－530.

［5］Tao Ze，Xie Li－yang，Yuan Feng.Study of performance based on time－constrained workflow processing［J］.Machinery Design ＆ Manufacture，2004，10（6）：49－51.（in Chinese）

［6］Liu Li，Mao Fei.Workflow－based project management system for complex software prototyping［J］.Journal of Beijing University of Aeronautics and Astronautics，2007，33（5）：585－589.（in Chinese）

［7］Li Hui－fang，F(xiàn)an Yu－shun.Overview on managing time in workflow systems［J］.Journal of Software，2002，13（8）：1552－1558.（in Chinese）

［8］Son J H，Kim M H.Improving the performance of time－constrained workflow processing［J］.The International Journal of Systems and Software，2001（58）：211－219.

［9］Li Hui－fang，F(xiàn)eng Fu－jian.Management and dynamic monitoring of deadlines in time－constrained workflows［J］.Transactions of Beijing Institute of Technology，2011，31（8）：937－943.（in Chinese）

附中文參考文獻(xiàn)：

［1］朱耀琴，吳慧中，楊勇.協(xié)同虛擬樣機(jī)的信息集成研究［J］.計(jì)算機(jī)仿真，2004，21（12）：136－138.

［2］李伯虎，柴旭東，熊光楞，等.復(fù)雜產(chǎn)品虛擬樣機(jī)工程的研究與初步實(shí)踐［J］.系統(tǒng)仿真學(xué)報(bào)，2002，14（3）：336－341.

［3］唐達(dá)，劉丹妮.一種工作流時(shí)間截止期限的動(dòng)態(tài)驗(yàn)證方法［J］.計(jì)算機(jī)集成制造系統(tǒng)，2004，10（9）：1154－1159.

［5］陶澤，謝里陽，袁鋒.基于時(shí)間約束的工作流進(jìn)程的性能研究［J］.機(jī)械設(shè)計(jì)與制造，2004，10（6）：49－51.

［6］劉麗，毛菲.基于工作流的復(fù)雜系統(tǒng)虛擬樣機(jī)項(xiàng)目管理系統(tǒng)［J］.北京航空航天大學(xué)學(xué)報(bào)，2007，33（5）：585－589.

［7］李慧芳，范玉順.工作流系統(tǒng)時(shí)間管理［J］.軟件學(xué)報(bào)，2002，13（8）：1552－1558.

［9］李慧芳，馮復(fù)劍.時(shí)間約束工作流的截止期限管理及其動(dòng)態(tài)監(jiān)控［J］.北京理工大學(xué)學(xué)報(bào)，2011，31（8）：937－943.