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

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

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

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

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

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

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

可重入生產(chǎn)系統(tǒng)［1］有別于 Job-Shop和 Flow-Shop的第三類(lèi)生產(chǎn)調(diào)度系統(tǒng)，由于具有可重入性特點(diǎn)，其調(diào)度過(guò)程更加復(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］.針對(duì)具有可重入特點(diǎn)的醫(yī)學(xué)檢測(cè)過(guò)程的調(diào)度問(wèn)題研究甚少［11］.

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

1　問(wèn)題描述

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

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

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

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

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

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

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

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

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

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

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

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

2　基于PN的建模與分析

為更清晰表述調(diào)度問(wèn)題，定義如下的符號(hà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道工序的開(kāi)始時(shí)間；表示第l個(gè)項(xiàng)目的第k道工序的完成時(shí)間；表示第l個(gè)項(xiàng)目的第k道工序的緊前工序集合；表示第l個(gè)項(xiàng)目的第k道工序與第k+1道工序的時(shí)間間隔；En表示第n類(lèi)設(shè)備；AT表示在T時(shí)段內(nèi)正在進(jìn)行的項(xiàng)目及工序的集合；pi（i=1，2，…）表示庫(kù)所；ρlk（k= 1，2，…）表示第l個(gè)檢測(cè)項(xiàng)目的第k道工序變遷向量；ρT表示在T時(shí)段內(nèi)工序變遷向量的集合.

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

以某免疫檢測(cè)項(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è)備編號(hào)En（n=1，2，…，5；E1=加樣頭，E2=移板臂，E3=溫育振蕩器，E4=洗板機(jī)，E5=分析儀），用表示在工序進(jìn)行中需要的設(shè)備號(hào)和執(zhí)行時(shí)間.

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

這里的行標(biāo)代表25個(gè)庫(kù)所，列標(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），滿(mǎn)足x，其中ξi（i=1，2，…，5）為基礎(chǔ)解系.從 ξi（i=1，2，…，5）中發(fā)現(xiàn)，其各分量反映了5個(gè)設(shè)備在工序中的使用情況（ξi中的1表示第i種設(shè)備在該工序中被用，0表示不被用）和設(shè)備庫(kù)所.如ξ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ū)庫(kù)所的位置和第3、5、7、10、25的設(shè)備的庫(kù)所位置，剩下的各分量下標(biāo)的順序就是檢驗(yàn)過(guò)程中設(shè)備的使用順序.根據(jù)實(shí)際的意義，λi（i=1，2，…，5）應(yīng)滿(mǎn)足λ1≤1，λ2≤1，λ3≤12，λ4≤2，λ5≤1.根據(jù)S-不變量的性質(zhì)［5］，還應(yīng)滿(mǎn)足:

其中，φ=（a1，a2，…，a25）T，ai（i=1，2，…，25）為庫(kù)所pi（i=1，2，…，25）中的令牌數(shù)；φ0為最初的各庫(kù)所的令牌數(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是要檢測(cè)的項(xiàng)目數(shù)，允許進(jìn)來(lái)新的檢測(cè)項(xiàng)目.根據(jù)式（1）可得

解式（2）得到

其中ki≥0（i=1，2，…，25），但根據(jù)檢測(cè)項(xiàng)目的實(shí)際意義，ki（i=1，2，…，25）的取值應(yīng)該滿(mǎn)足下列的條件: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；由此可見(jiàn)，庫(kù)所p2，p3，p4，p5，p6，p7，p9，p10，p11，p12，p13，p14， p16，p17，p18，p19，p20中的令牌數(shù)有界，而k1，k8，k15是緩沖區(qū)庫(kù)所的令牌數(shù)，令k=max｛k1，k8，k15｝，故所有庫(kù)所的令牌數(shù)有限，則PN是有界的.也就是說(shuō)在FBFS調(diào)度規(guī)則下，圖2所示的可重入式的調(diào)度問(wèn)題是穩(wěn)定的.

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

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

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

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

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

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

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

其中η=［*，t1，*，t2，*，t3，*，t4，t5，*，t6，*，t7，t8，t9，t10，t11，t12，*，t13，t14，t15，t16，t17，*］，且滿(mǎn)足: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)先出原則，因此，此檢測(cè)過(guò)程的工序的調(diào)度可看成隊(duì)列排序，以隊(duì)列理論可求出調(diào)度可行解.

3　實(shí)例分析

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

依據(jù)式（5）可得到一個(gè)滿(mǎn)足鏈?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.由此可見(jiàn)調(diào)度的可行解個(gè)數(shù)將出現(xiàn)組合爆炸，該調(diào)度問(wèn)題是一個(gè)NP難問(wèn)題.本文根據(jù)問(wèn)題約束條件建立時(shí)間約束矩陣，將尋求最小完工時(shí)間問(wèn)題變?yōu)樽钚』瘯r(shí)間約束矩陣問(wèn)題，利用易于求解的最小化時(shí)間約束矩陣求出最優(yōu)檢測(cè)過(guò)程調(diào)度方案.具體的算法及過(guò)程如下:

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

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

則η=ρ12；

根據(jù)上述尋解過(guò)程及式（3）～（5）的調(diào)度約束條件，可以得到同時(shí)進(jìn)行12個(gè)檢測(cè)項(xiàng)目的工序開(kāi)始時(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倍多，可見(jiàn)建立的調(diào)度方案具有較好的時(shí)間優(yōu)越性，但不代表是較好的可行調(diào)度解，因此需要對(duì)其進(jìn)行可行解的進(jìn)一步分析.

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

如果只做一個(gè)檢測(cè)項(xiàng)目，根據(jù)工序的鏈?zhǔn)郊s束及工序工作時(shí)間，可得該項(xiàng)目的工序開(kāi)始時(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表示，可見(jiàn)每條項(xiàng)目檢測(cè)曲線與理想檢測(cè)曲線是基本相似的.

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

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

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

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

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

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

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

（4）判斷是否滿(mǎn)足，否者重復(fù)從第（1）步開(kāi)始.經(jīng)過(guò)計(jì)算都滿(mǎn)足了C*的要求，說(shuō)明全部項(xiàng)目的檢驗(yàn)時(shí)間都滿(mǎn)足檢驗(yàn)的時(shí)間約束.調(diào)整后的時(shí)間需驗(yàn)證各時(shí)間段是否滿(mǎn)足η檢驗(yàn)過(guò)程要求.因此，可以考慮對(duì)所有的工序開(kāi)始時(shí)間進(jìn)行排列，得到按一個(gè)滿(mǎn)足約束關(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í)在工作效率和滿(mǎn)足連續(xù)性上都達(dá)到了實(shí)際的要求.

3）模型的仿真分析.針對(duì)上述的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)過(guò)336步的多次仿真結(jié)果顯示，最好的總的工序時(shí)間為206.5 min.這個(gè)運(yùn)行結(jié)果與通過(guò)PN模型得出的結(jié)果幾乎是一致的，總的時(shí)間減少了9.5 min，這說(shuō)明PN模型建立的有效性.

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

本文對(duì)一類(lèi)可重入的醫(yī)學(xué)檢測(cè)過(guò)程建立了Petri網(wǎng)模型，利用其關(guān)聯(lián)矩陣和可達(dá)樹(shù)分析了模型的穩(wěn)定性態(tài)及其他性能.根據(jù)PN模型和約束條件，找到一個(gè)在工作效率上提高了8.5倍多的可行調(diào)度方案，再通過(guò)時(shí)間約束矩陣的要求，調(diào)整某些工序的開(kāi)始執(zhí)行時(shí)間，最終得到較優(yōu)的調(diào)度方案，且利用MATLAB軟件驗(yàn)證所得到的調(diào)度方案滿(mǎn)足了問(wèn)題的約束要求，最后，利用CPN Tools進(jìn)行模型仿真，結(jié)果顯示總的工序時(shí)間幾乎是一致的.本文的研究結(jié)果在一定程度上擴(kuò)充了可重入調(diào)度研究問(wèn)題的領(lǐng)域，符合醫(yī)學(xué)的實(shí)際生化免疫檢測(cè)的需要.為了適合實(shí)際的免疫檢測(cè)，對(duì)不同工序的不同檢測(cè)項(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］任艷頻，張佐，吳秋峰.一類(lèi)規(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］.北京:中國(guó)科學(xué)院自動(dòng)化研究所，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］.自動(dòng)化學(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)車(chē)間調(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］錢(qián)省三，郭永輝.多重入芯片復(fù)雜制造系統(tǒng)生產(chǎn)優(yōu)化與控制［M］.北京:電子工業(yè)出版社，2008:1-130.

［11］高臣杰，張梅，胡躍明.基于改進(jìn)的遺傳算法的鏈?zhǔn)郊s束排序問(wèn)題的研究［EB/OL］.（2011-12-23）［2014 -03-12］.北京:中國(guó)科技論文在線，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）；廣州市科技重大專(zhuān)項(xiàng)計(jì)劃-產(chǎn)學(xué)研專(zhuān)項(xiàng)（2012Y5-00004）；中央高?；究蒲袠I(yè)務(wù)費(fèi)專(zhuān)項(xiàng)資金資助（2014zz0033）

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