基于PN的可重入醫(yī)學(xué)檢測調(diào)度系統(tǒng)優(yōu)化研究

戴婉儀，張　梅*，胡躍明，陳廣森

（1.華南理工大學(xué)自動化科學(xué)與工程學(xué)院，廣州510641；2.精密電子制造裝備教育部工程研究中心，廣州510641）

基于PN的可重入醫(yī)學(xué)檢測調(diào)度系統(tǒng)優(yōu)化研究

戴婉儀1，2，張梅1，2*，胡躍明1，2，陳廣森1，2

（1.華南理工大學(xué)自動化科學(xué)與工程學(xué)院，廣州510641；2.精密電子制造裝備教育部工程研究中心，廣州510641）

基于一類具有可重入特點(diǎn)的醫(yī)學(xué)檢測過程的設(shè)備調(diào)度問題，研究了具有約束條件的優(yōu)化解.首先分析了調(diào)度約束條件和優(yōu)化目標(biāo)，建立了其Petri Networks（PN）形式化模型，并分析了其規(guī)則調(diào)度系統(tǒng)的穩(wěn)定性和其他性能.然后利用PN模型和調(diào)度約束條件解出調(diào)度可行解結(jié)合對醫(yī)學(xué)檢測部分工序要求連續(xù)的基礎(chǔ)上建立時(shí)間約束矩陣，對可行解進(jìn)一步優(yōu)化，最終得到滿足所有約束條件的優(yōu)化可行解.通過對實(shí)際醫(yī)學(xué)檢測系統(tǒng)的實(shí)例分析和CPN Tools仿真，結(jié)果表明所建立的模型和方法的有效性.

可重入系統(tǒng)；Petri網(wǎng)；醫(yī)學(xué)檢測；調(diào)度

可重入生產(chǎn)系統(tǒng)［1］有別于 Job-Shop和 Flow-Shop的第三類生產(chǎn)調(diào)度系統(tǒng)，由于具有可重入性特點(diǎn)，其調(diào)度過程更加復(fù)雜.目前可重入生產(chǎn)系統(tǒng)的調(diào)度研究主要集中在半導(dǎo)體、鋼鐵鍛造等生產(chǎn)系統(tǒng)，已獲得了較好的研究進(jìn)展，并形成多種建模方法，如Kelly Networks模型、Queuing Networks模型、Brownian模型、Fluid Networks模型、Petri Networks模型和QBD模型等［2-10］.針對具有可重入特點(diǎn)的醫(yī)學(xué)檢測過程的調(diào)度問題研究甚少［11］.

本文所提出的可重入醫(yī)學(xué)檢測優(yōu)化調(diào)度問題來源于實(shí)際醫(yī)學(xué)檢測過程.該問題可看成離散事件動態(tài)系統(tǒng)的優(yōu)化問題，而PN模型是研究該類系統(tǒng)的重要建模工具，可較準(zhǔn)確地描述調(diào)度過程的并發(fā)和并行等特性.本文在分析系統(tǒng)約束條件和優(yōu)化目標(biāo)的基礎(chǔ)上，首先利用PN對調(diào)度問題進(jìn)行建模研究，確定模型中庫所的P集合和變遷T集合，借助它通過可達(dá)樹和關(guān)聯(lián)矩陣進(jìn)行可重入醫(yī)學(xué)檢測調(diào)度優(yōu)化系統(tǒng)穩(wěn)定性及其他性能的分析和評價(jià).并利用PN模型和約束條件得到一個(gè)可行調(diào)度方案，利用該可行調(diào)度方案與系統(tǒng)的時(shí)間約束矩陣相結(jié)合進(jìn)一步獲得更優(yōu)的調(diào)度方案.

1　問題描述

圖1為某醫(yī)學(xué)生化指標(biāo)檢測過程，具有明顯的可重入特性.整個(gè)檢測過程將在全自動免疫分析檢測設(shè)備上多次經(jīng)過加樣頭、機(jī)械手、孵育振蕩器、洗板機(jī)和分析儀等子模塊而完成.當(dāng)多個(gè)項(xiàng)目同時(shí)進(jìn)行檢測時(shí)，有效地調(diào)度這些資源將提高設(shè)備利用率，降低檢測成本和提高檢測時(shí)間周期.這類具有可重入性的優(yōu)化調(diào)度問題是一類NP-hard優(yōu)化調(diào)度問題［1］.

圖1　某免疫檢測項(xiàng)目可重入系統(tǒng)的工作流程圖Figure 1　A medical and biochemical indicator testing process

一臺檢驗(yàn)設(shè)備中各子模塊的個(gè)數(shù)可通過需求進(jìn)行配備，子模塊個(gè)數(shù)越多，可使用的檢測資源越充足，但設(shè)備成本也將顯著增大.因此，研究在一定數(shù)量的子模塊下，建立調(diào)度優(yōu)化模型，充分利用資源，降低檢測成本，提高檢測效率.

本文研究的調(diào)度系統(tǒng)檢測設(shè)備子模塊有5個(gè)，包括1個(gè)加樣頭、1個(gè)機(jī)械手、12個(gè)溫育振蕩器、2臺洗板機(jī)、1臺分析儀.把檢驗(yàn)相同生化指標(biāo)且放于同一檢驗(yàn)板上的樣本集合，定義為一個(gè)檢驗(yàn)項(xiàng)目.每個(gè)檢驗(yàn)項(xiàng)目均需經(jīng)過若干檢驗(yàn)步驟（稱為工序）才能完成某項(xiàng)生化指標(biāo)的檢驗(yàn).整個(gè)檢測過程滿足下列的基本約束:

①不同的檢驗(yàn)項(xiàng)目間不存在優(yōu)先級限制，且在零時(shí)刻所有的項(xiàng)目都可被檢驗(yàn)；

②同一項(xiàng)目符合鏈?zhǔn)郊s束:同一檢驗(yàn)項(xiàng)目l的工序必須按自然順序；

③其中某些工序盡量滿足連續(xù)性，最好無等待時(shí)間；

④設(shè)備使用的約束:對于某些設(shè)備不可同時(shí)使用，以免發(fā)生碰撞，但與其他設(shè)備可以同時(shí)進(jìn)行，如加樣頭和機(jī)械手不能同時(shí)運(yùn)動，以免相撞；

⑤設(shè)備資源是有限的；

⑥工序的不間斷性:每臺設(shè)備每個(gè)時(shí)刻只能執(zhí)行一道工序，即某一道工序一旦在某設(shè)備上執(zhí)行就不能中斷直到該工序完成；

⑦每道工序的執(zhí)行時(shí)間是固定的.

針對現(xiàn)有醫(yī)學(xué)要求檢驗(yàn)樣本量大，為降低檢測成本往往需要資源共享，要求一臺檢驗(yàn)設(shè)備同時(shí)進(jìn)行多個(gè)項(xiàng)目的檢測，而且要求在檢驗(yàn)過程中以最小化最大完工時(shí)間為目標(biāo)提高設(shè)備的工作效率，并且盡量減少檢測誤差，提高檢驗(yàn)的準(zhǔn)確性和檢驗(yàn)過程的穩(wěn)定性.因此，本文提出了該類醫(yī)學(xué)檢測過程的PN調(diào)度模型和求解調(diào)度方案的方法.

2　基于PN的建模與分析

為更清晰表述調(diào)度問題，定義如下的符號與變量:a表示需檢驗(yàn)的項(xiàng)目數(shù)；Pl（l=1，2，…，a）表示單個(gè)的檢驗(yàn)項(xiàng)目；Nl表示項(xiàng)目Pl的工序總數(shù)；k（k=1，2，…，Nl；l=1，2，…，a）表示各項(xiàng)目中的每一道工序；Plk表示第l個(gè)項(xiàng)目的第k道工序；表示第l個(gè)項(xiàng)目的第k道工序的固定執(zhí)行時(shí)間；表示第l個(gè)項(xiàng)目的第k道工序的開始時(shí)間；表示第l個(gè)項(xiàng)目的第k道工序的完成時(shí)間；表示第l個(gè)項(xiàng)目的第k道工序的緊前工序集合；表示第l個(gè)項(xiàng)目的第k道工序與第k+1道工序的時(shí)間間隔；En表示第n類設(shè)備；AT表示在T時(shí)段內(nèi)正在進(jìn)行的項(xiàng)目及工序的集合；pi（i=1，2，…）表示庫所；ρlk（k= 1，2，…）表示第l個(gè)檢測項(xiàng)目的第k道工序變遷向量；ρT表示在T時(shí)段內(nèi)工序變遷向量的集合.

針對調(diào)度系統(tǒng)以最小化最大完工時(shí)間為目標(biāo)，目標(biāo)函數(shù)表示為:

以某免疫檢測項(xiàng)目（表1）為例進(jìn)行PN建模.項(xiàng)目l=1，2，…，工序k=1，2，…，17，F(xiàn)Tlk表示第l個(gè)項(xiàng)目的第k道工序的固定執(zhí)行時(shí)間，單位為min，設(shè)備編號En（n=1，2，…，5；E1=加樣頭，E2=移板臂，E3=溫育振蕩器，E4=洗板機(jī)，E5=分析儀），用表示在工序進(jìn)行中需要的設(shè)備號和執(zhí)行時(shí)間.

表1　某免疫檢測項(xiàng)目工序過程及工序時(shí)間表Table 1　Testing process and its executing time for a biochemical indicator testing item

圖2　可重入調(diào)度系統(tǒng)在FBFS下的PN模型Figure 2　PN model for reentrant scheduling system according to FBFS

為了建立該調(diào)度過程的PN模型，在每次可重入檢測過程時(shí)，設(shè)立了3個(gè)虛擬緩沖區(qū)，待檢驗(yàn)的樣本將在緩沖區(qū)內(nèi)等待資源進(jìn)行下一步檢測.可重入調(diào)度中的工序、設(shè)備狀態(tài)等用庫所表示，工序開始或結(jié)束用變遷來表示，圖1所示的檢測過程PN模型如圖2所示，其中p1，p12，p19為虛擬的緩沖區(qū)庫所，p3，p5，p7，p10，p25為設(shè)備組庫所，其余的pi為正在進(jìn)行的工序庫所，而ti（i=1，2，…，20）表示工序開始或結(jié)束的變遷.在緩沖區(qū)p1中存在一定量的待檢測的項(xiàng)目，可以允許有新項(xiàng)目的進(jìn)入，（k=1，2，…，Nl；l=1，2，…，a）已知.為考慮緩沖區(qū)的優(yōu)先級，項(xiàng)目開始時(shí)按調(diào)度規(guī)則FBFS（First Buffer First Served）進(jìn)行，同時(shí)由于洗板機(jī)數(shù)量較少且工序執(zhí)行時(shí)間相對較長，在調(diào)度過程中應(yīng)優(yōu)先對其進(jìn)行調(diào)度.在明確了調(diào)度規(guī)則后，對系統(tǒng)的穩(wěn)定性進(jìn)行分析是十分必要的.

2.1調(diào)度的穩(wěn)定性分析

根據(jù)文獻(xiàn)［2］，生產(chǎn)系統(tǒng)的穩(wěn)定性解釋為:（1）緩沖區(qū)中的工件數(shù)目是有限的；（2）進(jìn)入生產(chǎn)系統(tǒng)的工件在有限的時(shí)間內(nèi)可以離開.基于圖2所示的PN模型，得到它的關(guān)聯(lián)矩陣

這里的行標(biāo)代表25個(gè)庫所，列標(biāo)代表20個(gè)變遷，其中

設(shè)x=（x1，x2，x3，…，x24，x25）T，求解線性方程組xTA=0.由于Rank（A）=20，可得S-不變量［5］含有5個(gè)自由未知量λi（i=1，2，…，5），滿足x，其中ξi（i=1，2，…，5）為基礎(chǔ)解系.從 ξi（i=1，2，…，5）中發(fā)現(xiàn)，其各分量反映了5個(gè)設(shè)備在工序中的使用情況（ξi中的1表示第i種設(shè)備在該工序中被用，0表示不被用）和設(shè)備庫所.如ξ1表示為:ξ1=（0，1，1，0，0，0，0，0，0，0，0，0，1，0，0，0，0，0，0，1，0，0，0，0，0）T；因而x可表示為

注意到在x中各分量，去除第1、12和19是3個(gè)緩沖區(qū)庫所的位置和第3、5、7、10、25的設(shè)備的庫所位置，剩下的各分量下標(biāo)的順序就是檢驗(yàn)過程中設(shè)備的使用順序.根據(jù)實(shí)際的意義，λi（i=1，2，…，5）應(yīng)滿足λ1≤1，λ2≤1，λ3≤12，λ4≤2，λ5≤1.根據(jù)S-不變量的性質(zhì)［5］，還應(yīng)滿足:

其中，φ=（a1，a2，…，a25）T，ai（i=1，2，…，25）為庫所pi（i=1，2，…，25）中的令牌數(shù)；φ0為最初的各庫所的令牌數(shù)，即φ0=（a，0，1，0，1，0，12，0，0，2，0，0，0，0，0，0，0，0，0，0，0，0，0，0，1）T，這里a是要檢測的項(xiàng)目數(shù)，允許進(jìn)來新的檢測項(xiàng)目.根據(jù)式（1）可得

解式（2）得到

其中ki≥0（i=1，2，…，25），但根據(jù)檢測項(xiàng)目的實(shí)際意義，ki（i=1，2，…，25）的取值應(yīng)該滿足下列的條件:k2，k3，k5，k7，k9，k10，k12，k14，k16，k17，k19，k20= 0，1；k4，k11，k18=0，1，…，12；k6，k13=0，1，2；由此可見，庫所p2，p3，p4，p5，p6，p7，p9，p10，p11，p12，p13，p14， p16，p17，p18，p19，p20中的令牌數(shù)有界，而k1，k8，k15是緩沖區(qū)庫所的令牌數(shù)，令k=max｛k1，k8，k15｝，故所有庫所的令牌數(shù)有限，則PN是有界的.也就是說在FBFS調(diào)度規(guī)則下，圖2所示的可重入式的調(diào)度問題是穩(wěn)定的.

2.2在調(diào)度規(guī)則下，性能指標(biāo)與模型參數(shù)的關(guān)系分析

在整個(gè)調(diào)度過程中，pi（i=2，…，25）中的令牌數(shù)變化可以通過PN的可達(dá)樹來描述.令［ti，δi］（i=1，2，…，20），其中ti為當(dāng)前被激發(fā)的變遷，δi為變遷ti發(fā)生所需的時(shí)間，也即當(dāng)前工序的執(zhí)行時(shí)間.變遷的過程即PN的可達(dá)樹如圖3所示，變遷中的第一個(gè)分量*代表檢驗(yàn)項(xiàng)目的來源情況.

圖3　PN可達(dá)樹Figure 3　Reachability tree of Petri Net

圖3的變遷時(shí)間表明時(shí)間間隔最小為0.5 min，于是把每類設(shè)備用時(shí)間按0.5 min的標(biāo)準(zhǔn)分割成一些點(diǎn)集.在同一個(gè)時(shí)間間隔［t，t+0.5］，必須滿足下述不等式:

由于加樣頭和機(jī)械手采用一條導(dǎo)軌運(yùn)動，所以還應(yīng)該滿足

如果把每一次的變遷用ρlk表示，其中緩沖區(qū)庫所的令牌數(shù)和設(shè)備庫所令牌數(shù)都用*代替.如使用E2的變遷包含:

其他設(shè)備的使用變遷類似.這些變遷在任意［t，t+ 0.5］時(shí)間段里，應(yīng)滿足:

其中η=［*，t1，*，t2，*，t3，*，t4，t5，*，t6，*，t7，t8，t9，t10，t11，t12，*，t13，t14，t15，t16，t17，*］，且滿足:t1+t2+t4+t6+t7+t8+t10+t12+t13+ t14+t16≤1；t3+t9+t15≤12；t5+t11≤2；t17≤1.

根據(jù)隊(duì)列理論，把每一次的新進(jìn)項(xiàng)目看成是隊(duì)列的入隊(duì).項(xiàng)目檢查完畢就是隊(duì)列的出隊(duì).隊(duì)列遵循先進(jìn)先出原則，因此，此檢測過程的工序的調(diào)度可看成隊(duì)列排序，以隊(duì)列理論可求出調(diào)度可行解.

3　實(shí)例分析

對表1的數(shù)據(jù)進(jìn)行實(shí)例分析，根據(jù)PN模型圖2，檢測開始時(shí)項(xiàng)目在緩沖區(qū)處于等待狀態(tài)，所有的設(shè)備都可使用.從表1知最小的工序執(zhí)行時(shí)間是0.5 min，因此以［t，t+0.5］時(shí)間區(qū)間對檢測過程進(jìn)行劃分，在每個(gè)［t，t+0.5］時(shí)間區(qū)間中調(diào)度需滿足式（3）和式（4）的約束關(guān)系.假設(shè)有a個(gè)項(xiàng)目待檢測，即項(xiàng)目l（l=1，2，…，a）的工序分別表示為Pl1，Pl2，…，Pl，17（l=1，2，…，a）.由于各檢測項(xiàng)目具有鏈?zhǔn)郊s束，即滿足式（5）:

依據(jù)式（5）可得到一個(gè)滿足鏈?zhǔn)郊s束的調(diào)度方案Pα11，Pα2β1，…，Pα3β2，Pα4，17，其中:若 α1=α2，則 β1=2；若α1≠α2，則β1=1；若α2=α3，則β1＜β2；若α3=α4，則β2=16；α3≠α4，則β2=17.而αi=1，2，…，a；βj=1，2，…，17.由此可見調(diào)度的可行解個(gè)數(shù)將出現(xiàn)組合爆炸，該調(diào)度問題是一個(gè)NP難問題.本文根據(jù)問題約束條件建立時(shí)間約束矩陣，將尋求最小完工時(shí)間問題變?yōu)樽钚』瘯r(shí)間約束矩陣問題，利用易于求解的最小化時(shí)間約束矩陣求出最優(yōu)檢測過程調(diào)度方案.具體的算法及過程如下:

（1）首先根據(jù)約束式（3）和式（4）尋找一組調(diào)度可行解.

由于洗板機(jī)數(shù)量較少且工序執(zhí)行時(shí)間相對較長，在調(diào)度過程中應(yīng)優(yōu)先考慮對其進(jìn)行調(diào)度.加上檢驗(yàn)項(xiàng)目的精確性要求，需在孵育工序后盡快進(jìn)行洗板工序，即（k=3，…，5，9，…，11，15，16）盡量小.由于加樣頭和機(jī)械手采用一條導(dǎo)軌運(yùn)動，假如首先P1進(jìn)入調(diào)度隊(duì)列，根據(jù)鏈?zhǔn)郊s束在完成P11和P12，即在［0，3］時(shí)間區(qū)間后，才可插入新的成員.若此時(shí)在［3，3.5］加入新成員P2，后續(xù)尋解過程如下:

則η=ρ12；

根據(jù)上述尋解過程及式（3）～（5）的調(diào)度約束條件，可以得到同時(shí)進(jìn)行12個(gè)檢測項(xiàng)目的工序開始時(shí)間向量yl（l=1，2，…，12）為:

y1=［0，2，2.5，62.5，63.5，69.5，70.5，73，73.5，133.5，134.5，143.5，144，146，146.5，152.5，153.5］；

y2=［2.5，4.5，5，65，66，72.5，74.5，78，78.5，138.5，139.5，148.5，150，152，152.5，162，163］；

y3=［5，7，7.5，67.5，70.5，76.5，78.5，82，82.5，146.5，147.5，156.5，158，162.5，163，168.5，169.5］；

y4=［7.5，9.5，10，73.5，74.5，80.5，82.5，86，86.5，149，150，160，163.5，163.5，167，173，174］；

y5=［10，12，12.5，77，78，84.5，86.5，90，90.5，157，158，167，169.5，176.5，177，183.5，184.5］；

y6=［12.5，14.5，15，81，82，88.5，90.5，94，94.5，160.5，161.5，171，174，179，179.5，187，188］；

y7=［15，17，17.5，85，86，92.5，94.5，98，99，167.5，168.5，177.5，179.5，184.5，185，190，191］；

y8=［17.5，19.5，20，89，90，96.5，99，102，102.5，172，173，182，185，189.5，190，195，196］；

y9=［20，22，22.5，93，94，100.5，104.5，106.5，107.5，178，179，188，191，194.5，195，201，202］；

y10=［22.5，24.5，25，97，98，104，107，109，109.5，182.5，183.5，193，196，198，198.5，203.5，204.5］；

y11=［25，27，27.5，101，102，109.5，110，112，112.5，188.5，189.5，198.5，199，202，202.5，208，209］；

y12=［27.5，29.5，30，104，105，112.5，113，115，115.5，193.5，194.5，204.5，205，207，207.5，213，214］.

則完成12個(gè)檢驗(yàn)項(xiàng)目總時(shí)間是216 min.相比于12個(gè)項(xiàng)目按順序完成（需要的時(shí)間是1 842 min）在效率上提高了8.5倍多，可見建立的調(diào)度方案具有較好的時(shí)間優(yōu)越性，但不代表是較好的可行調(diào)度解，因此需要對其進(jìn)行可行解的進(jìn)一步分析.

（2）可行解的進(jìn)一步優(yōu)化和調(diào)整.

如果只做一個(gè)檢測項(xiàng)目，根據(jù)工序的鏈?zhǔn)郊s束及工序工作時(shí)間，可得該項(xiàng)目的工序開始時(shí)間向量為y0=［0，2，2.5，62.5，63.5，69.5，70，72，72.5，132.5，133.5，142.5，143，145，145.5，150.5， 151.5］，則=0（k=1，2，…，16）是最理想的檢驗(yàn)狀態(tài).12個(gè)檢驗(yàn)項(xiàng)目的可行調(diào)度方案與它的圖形用圖4表示，可見每條項(xiàng)目檢測曲線與理想檢測曲線是基本相似的.

圖4　12個(gè)檢測項(xiàng)目時(shí)間與理想檢測時(shí)間曲線圖Figure 4　Process time of 12 testing items and idea testing time

下面討論所得到的12個(gè)調(diào)度方案與理想狀態(tài)的差異.令:

稱為項(xiàng)目工序開始時(shí)間矩陣.

稱C為各項(xiàng)目工序檢測等待時(shí)間矩陣.根據(jù)檢驗(yàn)項(xiàng)目的精確性要求，需在孵育工序后盡快進(jìn)行洗板工序，即（k=3，4，5；9，10，11；15，16）盡量小.特別地，若C滿足，，則記為C*，稱為工序時(shí)間約束矩陣.所以所有得到的可行調(diào)度方案，不僅在時(shí)間上要提高效率，也要在時(shí)間約束上滿足時(shí)間約束矩陣的要求.根據(jù)矩陣 B可以得到相應(yīng)的矩陣 C，其中.再計(jì)算.發(fā)現(xiàn)P2，P5，…，P12都不滿足時(shí)間約束的要求，所以根據(jù)所得矩陣C在時(shí)間上作調(diào)整，尋求更優(yōu)解.步驟如下:

（1）根據(jù)最初矩陣C，對工序開始時(shí)間調(diào)整，滿足:

（2）重新得到一個(gè)新的項(xiàng)目工序開始時(shí)間矩陣B1；

（3）重新計(jì)算得到一個(gè)新的矩陣C，并與C*做比較；

（4）判斷是否滿足，否者重復(fù)從第（1）步開始.經(jīng)過計(jì)算都滿足了C*的要求，說明全部項(xiàng)目的檢驗(yàn)時(shí)間都滿足檢驗(yàn)的時(shí)間約束.調(diào)整后的時(shí)間需驗(yàn)證各時(shí)間段是否滿足η檢驗(yàn)過程要求.因此，可以考慮對所有的工序開始時(shí)間進(jìn)行排列，得到按一個(gè)滿足約束關(guān)系含有204個(gè)數(shù)據(jù)的調(diào)度方案 Pα11，Pα2β1，…，Pα3β2，Pα4，17進(jìn)行分析.根據(jù)數(shù)據(jù)排列，用MATLAB軟件可以找回每一個(gè)時(shí)間點(diǎn)相應(yīng)項(xiàng)目工序.如利用［i，j］=find（U=5），可找5的位置是P32和P13，這樣下去，就可以列出所有工序的排列情況，再利用前面的隊(duì)列和ρlk（l=1，2，…，12；k=1，2，…，17），可以驗(yàn)證調(diào)度方案是可行的，且此時(shí)得到的調(diào)度方案同時(shí)在工作效率和滿足連續(xù)性上都達(dá)到了實(shí)際的要求.

3）模型的仿真分析.針對上述的12個(gè)相同的項(xiàng)目的研究，用CPN Tools進(jìn)行模型仿真（圖5）.

圖5　CPN Tools的仿真截圖Figure 5　Simulation of CPN Tools screenshot

因?yàn)槔锩娴姆抡鏁r(shí)間只能為整數(shù)仿真，所以模型里面的所有變遷時(shí)間全部加倍，因此實(shí)際的總花費(fèi)時(shí)間為仿真時(shí)間的一半.每次經(jīng)過336步的多次仿真結(jié)果顯示，最好的總的工序時(shí)間為206.5 min.這個(gè)運(yùn)行結(jié)果與通過PN模型得出的結(jié)果幾乎是一致的，總的時(shí)間減少了9.5 min，這說明PN模型建立的有效性.

4　結(jié)束語

本文對一類可重入的醫(yī)學(xué)檢測過程建立了Petri網(wǎng)模型，利用其關(guān)聯(lián)矩陣和可達(dá)樹分析了模型的穩(wěn)定性態(tài)及其他性能.根據(jù)PN模型和約束條件，找到一個(gè)在工作效率上提高了8.5倍多的可行調(diào)度方案，再通過時(shí)間約束矩陣的要求，調(diào)整某些工序的開始執(zhí)行時(shí)間，最終得到較優(yōu)的調(diào)度方案，且利用MATLAB軟件驗(yàn)證所得到的調(diào)度方案滿足了問題的約束要求，最后，利用CPN Tools進(jìn)行模型仿真，結(jié)果顯示總的工序時(shí)間幾乎是一致的.本文的研究結(jié)果在一定程度上擴(kuò)充了可重入調(diào)度研究問題的領(lǐng)域，符合醫(yī)學(xué)的實(shí)際生化免疫檢測的需要.為了適合實(shí)際的免疫檢測，對不同工序的不同檢測項(xiàng)目的建模分析，仍需要進(jìn)行進(jìn)一步的理論研究和探討.

［1］Kumar P R.Re-entrant lines［J］.Queuing Systems，1993，13（1-2）:87-110.

［2］Lu S H，Kumar P R.Distributed scheduling based on due dates and buffer priorities［J］.IEEE Transaction on Automatic Control，1991，36（12）:1406-1416.

［3］Zhou M C，Jeng M D.Modeling，analysis，simulation，scheduling，and control of semiconductor manufacturing system:A Petri Net approach［J］.IEEE Transaction on Semiconductor Manufacturing，1998，11（3）:333-357.

［4］Lin M H，F(xiàn)u L C.Modeling，analysis，simulation，scheduling，and control of semiconductor manufacturing system:A generalized stochastic colored timed Petri Net approach，systems，man，and cybe-rnetics［J］.IEEE SMC’99 Conference Proceeding，1999（3）:769-774.

［5］任艷頻，張佐，吳秋峰.一類規(guī)則調(diào)度系統(tǒng)的Petri網(wǎng)研究方法［J］.計(jì)算機(jī)集成制造，1999，5（2）:58-61. Ren Y P，Zhang Z，Wu Q F.Research on a class of rulebased scheduling system using Petri net［J］.Computer Integrate Manufacturing Systems，1999，5（2）:58-61.

［6］呂文彥.黨延忠.基于Petri網(wǎng)與遺傳算法的可重入生產(chǎn)系統(tǒng)調(diào)度［J］.計(jì)算機(jī)工程與應(yīng)用，2005，19:226-228；232. Lv W Y，Dang Y Z.Scheduling reentrant lines based on Petri Net and GA［J］.Computer Engineering and Applications，2005，19:226-228；232.

［7］趙麗娜.可重入生產(chǎn)系統(tǒng)的調(diào)度優(yōu)化與性能分析［D］.北京:中國科學(xué)院自動化研究所，1999. Zhao L N.Scheduling optimization and performance analysis of reentrant lines［M］.Beijing:Institute of Automation Chinese Academy of Sciences，1999.

［8］ 鄭應(yīng)平，趙麗娜，王利存.可重入生產(chǎn)系統(tǒng)的QBD型模型［J］.自動化學(xué)報(bào)，2001，27（5）:593-605. Zheng Y P，Zhao L N，Wang L C.Quasi-birth-and-death type models of reentrant lines［J］.Acta Automatica Sinica，2001，27（5）:593-605

［9］陳曉慧，張啟忠.可重入式生產(chǎn)車間調(diào)度的計(jì)算機(jī)仿真與優(yōu)化研究［J］.計(jì)算機(jī)科學(xué)，2009，36（9）:297-299；302. Chen X H，Zhang Q Z.Production scheduling simulation and optimization of reentrant produce jop shop［J］.Computer Science，2009，36（9）:297-299；302.

［10］錢省三，郭永輝.多重入芯片復(fù)雜制造系統(tǒng)生產(chǎn)優(yōu)化與控制［M］.北京:電子工業(yè)出版社，2008:1-130.

［11］高臣杰，張梅，胡躍明.基于改進(jìn)的遺傳算法的鏈?zhǔn)郊s束排序問題的研究［EB/OL］.（2011-12-23）［2014 -03-12］.北京:中國科技論文在線，http://www.paper.edu.cn/html/releasepaper/2011/12/680/. Gao C J，Zhang M，Hu Y M.Research of sequencing with chain constraints based on improved genetic algorithm［EB/OL］.（2011-12-23）［2014-03-12］.Bei Jing: Sciencepaper Online，http://www.paper.edu.cn/html/ releasepaper/2011/12/680/.

【中文責(zé)編：莊曉瓊英文責(zé)編：肖菁】

Research on PN-Based Scheduling Optimization for Reentrant Medical Testing System

Dai Wanyi1，2，Zhang Mei1，2*，Hu Yueming1，2，Chen Guangsen1，2
（1.College of Automatic Science and Engineering，South China University of Technology，Guangzhou 510641，China；2.Engineering Research Centre for Precision Electronic Manufacturing Equipments of Ministry of Education，Guangzhou 510641，China）

The optimal solution to the scheduling problem to reentrant medical devices testing process for the constraint conditions is studied.Firstly，a formal Petri Net（PN）model is built by analysis of scheduling constraints，optimization objectives，system stability and other system properties.Furthermore，based on the PN model and its scheduling constraints，a feasible scheduling solution is calculated.It combines with continuous recycling constraint of medical test and established time constraint matrix.The feasible solution is eventually optimized.Finally，the practical analysis of medical testing systems and CPN Tools simulation method turn out the result for the established models and methods are valid.

reentrant system；Petri net；medical testing；scheduling

TP301

A

1000-5463（2015）03-0151-08

2014-07-10《華南師范大學(xué)學(xué)報(bào)（自然科學(xué)版）》網(wǎng)址:http://journal.scnu.edu.cn/n

廣東省產(chǎn)學(xué)研重點(diǎn)項(xiàng)目（2011A090200047）；廣州市科技重大專項(xiàng)計(jì)劃-產(chǎn)學(xué)研專項(xiàng)（2012Y5-00004）；中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金資助（2014zz0033）

張梅，副教授，Email:zhangmei@scut.edu.cn.