大規(guī)模個性化信息系統(tǒng)中的應(yīng)答協(xié)議研究

徐 揚

（北京大學(xué)，北京 100871）

一、引言

隨著社會的發(fā)展，人與信息系統(tǒng)的有效交互變得越來越重要，其影響因素也有很多，包括人的因素、知識系統(tǒng)的因素、任務(wù)因素、管理因素和環(huán)境因素等，而一個組織的競爭力對信息的依賴越來越強[1]。信息系統(tǒng)作為各類系統(tǒng)的一個重要組成部分，其高效性至為關(guān)鍵，其中，檢索任務(wù)響應(yīng)時間的合理控制是滿足客戶需求的一個重要方面，實際上這也是大規(guī)模個性化定制策略的核心研究問題[2，3]。合理的時間分配是信息檢索系統(tǒng)構(gòu)建中的重要內(nèi)容和關(guān)鍵問題，一個最簡單的思路就是減少無效時間，所謂無效時間，就是非生產(chǎn)時間，包括等待時間和準(zhǔn)備時間等。在信息檢索系統(tǒng)中，所謂生產(chǎn)時間就是實際用于檢索的時間。在檢索系統(tǒng)的設(shè)計中，雖然增大批量可以減少任務(wù)切換次數(shù)從而減少準(zhǔn)備時間，但是會大大增加檢索成本和調(diào)度難度。因此，在系統(tǒng)設(shè)計的過程中，既要減少準(zhǔn)備時間，同時又要減小檢索任務(wù)批量，以降低檢索任務(wù)的庫存級別，改進客戶服務(wù)[4]。在通常采用的系統(tǒng)中，將任務(wù)準(zhǔn)備與任務(wù)處理分開是一個積極的策略，該策略被許多生產(chǎn)與管理系統(tǒng)所采用[5]，包括準(zhǔn) 時 生 產(chǎn) (Just-In-Time，JIT)[6]，成 組 技 術(shù) (Group Technology，GT)[7]和單元制造(Cellular Manu facturing)[8]等。與生產(chǎn)系統(tǒng)類似，信息系統(tǒng)在設(shè)計過程中，也常將任務(wù)準(zhǔn)備和任務(wù)處理分開。

在信息檢索系統(tǒng)中，合理的應(yīng)答協(xié)議設(shè)計，輔以相應(yīng)的調(diào)度規(guī)則可以優(yōu)化系統(tǒng)性能[9]。其中，調(diào)度規(guī)則設(shè)計的一般原則是要避免某個檢索任務(wù)過長時間地占有某項資源，而使其它檢索任務(wù)處于等待狀態(tài)。在設(shè)計中，涉及一些決策規(guī)則的制訂，包括是否、何時斷開任務(wù)與資源的連接等。

應(yīng)答協(xié)議研究在信息系統(tǒng)中有著重要的應(yīng)用，包括實現(xiàn)資源有效分配、發(fā)現(xiàn)錯誤、避免死鎖[10]等。例如，在某個檢索系統(tǒng)中，不同類型的檢索任務(wù)往往會對昂貴而有限的資源，如服務(wù)器，進行競爭，這時就需要制定應(yīng)答協(xié)議——如果一個檢索任務(wù)過長時間地占據(jù)服務(wù)器而使其處于空閑狀態(tài)，就要將其中斷，而允許其它檢索任務(wù)訪問服務(wù)器。這里，“過長時間”往往通過一個時間閾值來判斷，因此應(yīng)答協(xié)議設(shè)計中的一個關(guān)鍵問題就是如何設(shè)定時間閾值，從而優(yōu)化系統(tǒng)，提高性能。

二、模型定義與證明

本節(jié)中，將首先給出一個通用的系統(tǒng)模型定義，進而對系統(tǒng)應(yīng)答問題進行形式化的描述，最后給出關(guān)于最優(yōu)超時閾值的定理及證明。

1.模型定義

首先定義一個系統(tǒng)S=(W，Q，R)，其中W={wi}是一個工作站集，每一個工作站wi負責(zé)完成某一類任務(wù)，且一次只做一個任務(wù)；Q是一個認證服務(wù)器，廣義地說，它就是系統(tǒng)中不同任務(wù)競爭的那個“稀缺資源”；R是一個路由器，負責(zé)控制從工作站出來的任務(wù)與服務(wù)器的連接與斷開。系統(tǒng)如圖1所示。

圖1 系統(tǒng)S=(W，Q，R)模型

在這個系統(tǒng)中，認證服務(wù)器Q每次只能處理一個任務(wù)，對于每個被處理的任務(wù)x(x=1，2，…，n)，準(zhǔn)備時間(Setup Time)Sx，認證時間(Qualifcation Time)為qx，如果通過了認證，則進入任務(wù)處理階段，否則，它必須回到原來的工作站wi中進行校正，校正時間(Adjusting Time)為 ax，然后再到Q中進行檢測。本模型中，任務(wù)的傳輸時間是可忽略的。認證-校正過程具體如圖2所示。

圖2 認證-校正過程

在一個信息系統(tǒng)中，所謂認證的過程，就是判定一個檢索任務(wù)是否可以被執(zhí)行，例如格式是否正確[11]，內(nèi)容是否合法等；而所謂校正過程，就是將一個“不合格”的檢索任務(wù)進行校正，使其滿足檢索條件。該認證-校正過程就是信息系統(tǒng)中的應(yīng)答協(xié)議，即只有通過認證，檢索服務(wù)器才會對檢索任務(wù)進行應(yīng)答，否則，不予應(yīng)答，防止檢索服務(wù)器產(chǎn)生額外的負擔(dān)。

在這個認證-校正過程中，可以是任務(wù)向認證服務(wù)器傳遞，也可以是認證服務(wù)器向工作站移動（如一個專家?guī)еO(shè)備在工作站中進行認證工作），推而廣之，上述模型及其描述的問題是通用的，不僅適用于信息系統(tǒng)，也可以應(yīng)用于其它類似系統(tǒng)，如計算系統(tǒng)、通訊系統(tǒng)、網(wǎng)絡(luò)系統(tǒng)、生產(chǎn)系統(tǒng)等。

2.問題描述

當(dāng)某項任務(wù)x認證未通過時，有關(guān)應(yīng)答協(xié)議的問題就產(chǎn)生了。此時，系統(tǒng)必須做出如下決策：在工作站wi對任務(wù)x進行校正的過程中，要么任務(wù)x繼續(xù)占據(jù)認證服務(wù)器Q，直至任務(wù)x“合格”，檢索服務(wù)器產(chǎn)生應(yīng)答；要么將其斷開，如果選擇斷開任務(wù)x與認證服務(wù)器Q，那么就需要確定多久之后斷開。這就是應(yīng)答協(xié)議需要解決的問題。文章試圖用一個時間閾值η來控制整個決策過程，即是否斷開以及何時斷開。于是，應(yīng)答協(xié)議的問題簡化為：任務(wù)x占據(jù)認證服務(wù)器Q多久可以使系統(tǒng)的性能最大化，即求使得系統(tǒng)性能最優(yōu)的時間閾值η。

對于時間閾值η，我們有0≤η≤∞。η=0意味著一旦任務(wù)x認證未通過，就立即釋放認證服務(wù)器Q；η=∞意味著任務(wù)x一直占據(jù)認證服務(wù)器Q，直至校正完畢并通過認證；其余情況表示若任務(wù)x認證未通過，在占據(jù)認證服務(wù)器Q一段時間后再將其釋放。

3.定理證明

直觀地看，為了增加系統(tǒng)“稀缺資源”的使用率，應(yīng)該令η=0，這樣Q才會始終保持處于工作狀態(tài)。然而，若η=0，任務(wù)的切換頻率最大，而每次任務(wù)切換都會產(chǎn)生一個準(zhǔn)備時間sx，而這段時間內(nèi)，Q是空閑的，因此為了使∑sx最小，應(yīng)該令η=∞，即令任務(wù)的切換次數(shù)最小化。此時，貌似會有一個0＜η=μ＜∞能夠平衡兩者。然而，當(dāng)μ≥ax時，任務(wù)x可以在占據(jù)Q的時間內(nèi)完成校正，則η=μ與η=∞效果一樣；當(dāng)μ＜ax時，任務(wù)x無法在占據(jù)Q的時間內(nèi)完成校正，則與其令η=μ，不如令η=0。

由上述直觀推理，我們可以得到如下定理，并給出證明。

定理：當(dāng)時間閾值η取極值，即η=0或η=∞時，系統(tǒng)的應(yīng)答協(xié)議最優(yōu)。

證明：設(shè)x和y兩個先后連續(xù)通過Q的任務(wù)；時間閾值η=μ，0≤μ≤∞；所考察的時間段time：x完成校正與再認證的時間+y完成首次認證的時間（y的認證結(jié)果及其后的行為屬于下一個time周期）。

存在μ≥ax和μ＜ax兩種情況：

（1）情況1：μ＜ax（任務(wù)x在其占據(jù)Q的時間內(nèi)，未完成校正）

①：ax≤sy+qy（在Q對任務(wù)y進行處理（準(zhǔn)備+認證）的時間內(nèi)，任務(wù)x完成了校正）

因此，η=0或η=∞時，time最小，應(yīng)答協(xié)議最優(yōu)。②：ax＞sy+qy（在Q對任務(wù)y進行處理（準(zhǔn)備+認證）的時間內(nèi)，任務(wù)x未完成校正）

至于 time｜(η=0)與 time｜(η=∞)的比較，取決于 sx與sr+qy，但time的最小值一定在η=0或η=∞時取到。

因此，η=0或η=∞時，time最小，應(yīng)答協(xié)議最優(yōu)。

（2）情況2：μ≥ax（任務(wù)x在其占據(jù)Q的時間內(nèi)，完成校正）

因此，η=0或η=∞時，time最小，應(yīng)答協(xié)議最優(yōu)。

綜上所述，η=0或η=∞時，time最小時，應(yīng)答協(xié)議最優(yōu)。

證畢。

在定理的證明過程中，我們發(fā)現(xiàn) time｜(η=0)與time｜(η=∞)的大小關(guān)系有時候依賴于具體任務(wù)的準(zhǔn)備時間s和認證時間q，但無論如何，time的最小值總在η=0或η=∞這兩個極值點取到。

直觀來看，切斷某項檢索任務(wù)對核心資源的超時占有，并通過授予處于等待狀態(tài)的檢索任務(wù)在某一中間的時間閾值之后獲得資源的權(quán)力，可以提高系統(tǒng)效率。盡管這一論述貌似合理，但文章證明了最優(yōu)結(jié)果并不是賦予時間閾值一個中間值，而是邊界極值，即始終占有或立即放棄。

三、討論

在一般系統(tǒng)中，應(yīng)答協(xié)議部分往往采用結(jié)構(gòu)化設(shè)計方法。應(yīng)答協(xié)議一般通過循環(huán)等待并判斷超時條件是否成立來實現(xiàn)，或者通過調(diào)用支持超時操作的函數(shù)來實現(xiàn)，即如果在指定時間內(nèi)無法滿足條件，則進入超時狀態(tài)，并執(zhí)行相應(yīng)處理，否則順序執(zhí)行下一步。

基于這樣的結(jié)構(gòu)化系統(tǒng)設(shè)計方法，本文提出當(dāng)時間閾值η取極值，即η=0或η=∞時，檢索系統(tǒng)的應(yīng)答協(xié)議最優(yōu)。同時，如果系統(tǒng)中任務(wù)的準(zhǔn)備時間可以忽略，那么時間閾值一定為η=0。實際上，如果是同類型檢索任務(wù)之間的切換，那么準(zhǔn)備時間就會比較短，如果是不同類型檢索任務(wù)之間的切換，準(zhǔn)備時間會比較長。任務(wù)切換是影響系統(tǒng)效率的重要因素之一，因此將檢索任務(wù)進行分類，并將同類型的檢索任務(wù)集中在某一個工作站，可以縮短準(zhǔn)備時間，提高應(yīng)答效率。因此，對檢索系統(tǒng)進行設(shè)計時，應(yīng)首先建立一個分類模塊，對檢索任務(wù)進行分類，將同類型的檢索任務(wù)發(fā)往同一個檢索工作站。

一項檢索任務(wù)本質(zhì)是指用戶希望得到某種服務(wù)而向系統(tǒng)發(fā)出的請求，不同類型的任務(wù)對資源有不同的需求和偏好。通過分析任務(wù)的請求方式和內(nèi)容，提取任務(wù)特征，根據(jù)貝葉斯分類算法、人工神經(jīng)網(wǎng)絡(luò)、支持向量機等分類方法，對任務(wù)進行分類，進而將同類型的任務(wù)歸于同一邏輯集合[12]。在有些系統(tǒng)中，檢索任務(wù)之間的切換不僅需要較長的時間，還需要高昂的其它代價，如空間、風(fēng)險等。任務(wù)切換成本普遍產(chǎn)生于各類系統(tǒng)中[13]，例如計算機和通信設(shè)備通過硬件鎖定來控制成本，當(dāng)然，通過提升系統(tǒng)的兼容性，可以有效降低切換成本。

大規(guī)模個性化定制(Mass Customization)追求以大規(guī)模生產(chǎn)的成本去實現(xiàn)客戶個性化的需求，從而實現(xiàn)生產(chǎn)效率和效益的提升，這就需要同時考慮規(guī)模經(jīng)濟(Economies of Scale)和范圍經(jīng)濟(Economies of Scope)。隨著人民生活水平的日益提高，消費者不再簡單的滿足對產(chǎn)品功能的需求，而越來越多的希望定制個性化的產(chǎn)品。然而，個性化的生產(chǎn)必然導(dǎo)致規(guī)?？s小，范圍擴大，成本上升，無法用單個模板制造多個產(chǎn)品，因此必然存在多個模板共用一條生產(chǎn)線的情況。這里廣義的生產(chǎn)線就是本模型中認證服務(wù)器所代表的稀缺資源點。由多個模板爭奪有限稀缺資源點所引起的資源爭奪矛盾，可以用本模型進行控制，即將等待時間的閾值設(shè)為0或∞，可使系統(tǒng)整體效率最優(yōu)。同時，可以用本模型的準(zhǔn)備時間乘以某個系數(shù)，用帶權(quán)重的準(zhǔn)備時間囊括任務(wù)切換的時間成本、空間成本、經(jīng)濟成本和風(fēng)險成本等。對準(zhǔn)備時間、認證時間、校正時間的權(quán)重處理可以大大增強本模型的通用性。

四、結(jié)論

目前，關(guān)于應(yīng)答協(xié)議的研究往往集中于網(wǎng)絡(luò)通訊協(xié)議的分析與設(shè)計，而在現(xiàn)實應(yīng)用中，應(yīng)答協(xié)議是任何復(fù)雜系統(tǒng)設(shè)計都會涉及到的，比如越來越多地應(yīng)用于大規(guī)模個性化定制生產(chǎn)系統(tǒng)中。在該系統(tǒng)中，不同的客戶需求與不同的產(chǎn)品簇形成映射，進而得到多個生產(chǎn)模板。如何處理好有限條生產(chǎn)線和相對多的生產(chǎn)模板之間的平衡，使單體產(chǎn)品成本較低，且滿足市場快速響應(yīng)的要求，是大規(guī)模個性化定制系統(tǒng)需要重點關(guān)注的研究內(nèi)容。文章模型探討了多個任務(wù)爭奪單個（可擴展為有限多個）資源點涉及的響應(yīng)時間問題，為提升大規(guī)模個性化定制系統(tǒng)效率提供了有益的參考。大規(guī)模個性化定制模式能夠有效降低產(chǎn)品的成本，縮短產(chǎn)品的市場效應(yīng)時間，極大促進商品繁榮，重視客戶之間的差異，使得客戶個性需要得到尊重，能夠滿足大量客戶的物質(zhì)與精神需要。它已經(jīng)成為當(dāng)今制造領(lǐng)域和服務(wù)行業(yè)不可逆轉(zhuǎn)的趨勢，被越來越多地企業(yè)（如服裝企業(yè)、公共交通企業(yè)、通信企業(yè)、食品企業(yè)等）所采納并付諸實施。合理的應(yīng)答協(xié)議可以有效滿足用戶在響應(yīng)時間內(nèi)的服務(wù)需求，其實質(zhì)是合理的資源分配，尤其是稀缺資源的分配，提高生產(chǎn)效率。文章構(gòu)造的通用應(yīng)答協(xié)議模型，不僅能夠解決信息系統(tǒng)在資源配置中的相關(guān)問題，還可以通過引入權(quán)重的方法，解決資源競爭中的非時間問題。雖然文章只討論了包含一個認證服務(wù)器，即一個“稀缺資源”的情況，但即使現(xiàn)實的信息系統(tǒng)中有多個認證結(jié)服務(wù)器或稀缺資源點，由于其稀缺性決定了必然會存在瓶頸，實際上，本模型的Q是對這種瓶頸的抽象，因此適用于企業(yè)與政府信息化建設(shè)的諸多方面[14]。

[1]陳文波，黃麗華，陳琪彰，潘善琳.企業(yè)信息系統(tǒng)實施中的意義建構(gòu)：以S公司為例 [J].管理世界，2011(6)：142-151.

[2]Fogliatto F.S.，da SilveiraG.J.C.，Borenstein D.Themass custom-ization decade：An updated review of the literature[J].Internatio-nal JournalofProduction Economics，2012，138(1)：14-25.

[3]周水銀，陳榮秋.大規(guī)模定制的發(fā)展與應(yīng)用研究 [J].中國軟科學(xué)，2003(1)：155-156.

[4]全春光.供應(yīng)商管理庫存研究現(xiàn)狀及展望 [J].技術(shù)經(jīng)濟與管理研究，2010(4)：101-104.

[5]AllahverdiA.，Gupta J.N.D.，Aldowaisan T.A review ofschedu-ling research involving setup considerations[J].Omega-Interna-tional JournalofManagementScience，1999，27(2)：219-239.

[6]Inman RA，Sale RS，Green Jr.KW，Whitten D.Agilemanufactu-ring:Relation to JIT，operationalperformanceand firm performance[J].JournalofOperationsManagement，2011，29(4)：343-355.

[7]Alhourani F.Clustering algorithm for solving group technologyproblem withmultiple process routings[J].Computers IndustrialEngineering，2013，66(4)：781-790.

[8]Ah kioon S，Bulgak AA，Bektas T.Integrated cellularmanufactu-ring systems design with production planning and dynamic systemreconfiguration[J].European Journal of Operational Research，2009，192(2)：414-428.

[9]Baykasogˇlu A，O¨zbak1r L.Analyzing the effect of dispatchingrules on the scheduling performance through grammar basedflexible scheduling system[J].International Journalof ProductionEconomics，2010，124(2)：369-381.

[10]Jue J.P.，Borella M.S.，Mukherjee B.Performance analysis ofthe rainbowWDM opticalnetwork prototype[J].IEEE JournalonSelected Areas in Communications，1996，14(5)：945-951.

[11]Xu Y.，Bernard A.Measurementofenterprise knowledgeby statecharacterization[J].ExpertSystems，2010，27(5)：374-387.

[12]Md.Farid D，Zhang L，Rahman CM，Hossain MA，Strachan R.Hybrid decision tree and na l¨ve Bayes classifiers formulti-classclassification tasks[J].Expert Systemswith Applications，2014，41(4)：1937-1946.

[13]BiglaiserG，Crémer J，DobosG.Thevalueofswitching costs[J].JournalofEconomic Theory，2013，148(3)：935-952.

[14]廖吉林，劉建一.論企業(yè)信息化建設(shè)中的業(yè)務(wù)流程重構(gòu)問題[J].技術(shù)經(jīng)濟與管理研究，2009(03)：48-50.