大規模個性化信息系統中的應答協議研究

徐 揚

（北京大學，北京 100871）

一、引言

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

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

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

二、模型定義與證明

本節中，將首先給出一個通用的系統模型定義，進而對系統應答問題進行形式化的描述，最后給出關于最優超時閾值的定理及證明。

1.模型定義

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

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

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

圖2 認證-校正過程

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

在這個認證-校正過程中，可以是任務向認證服務器傳遞，也可以是認證服務器向工作站移動（如一個專家帶著設備在工作站中進行認證工作），推而廣之，上述模型及其描述的問題是通用的，不僅適用于信息系統，也可以應用于其它類似系統，如計算系統、通訊系統、網絡系統、生產系統等。

2.問題描述

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

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

3.定理證明

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

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

定理：當時間閾值η取極值，即η=0或η=∞時，系統的應答協議最優。

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

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

（1）情況1：μ＜ax（任務x在其占據Q的時間內，未完成校正）

①：ax≤sy+qy（在Q對任務y進行處理（準備+認證）的時間內，任務x完成了校正）

因此，η=0或η=∞時，time最小，應答協議最優。②：ax＞sy+qy（在Q對任務y進行處理（準備+認證）的時間內，任務x未完成校正）

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

因此，η=0或η=∞時，time最小，應答協議最優。

（2）情況2：μ≥ax（任務x在其占據Q的時間內，完成校正）

因此，η=0或η=∞時，time最小，應答協議最優。

綜上所述，η=0或η=∞時，time最小時，應答協議最優。

證畢。

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

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

三、討論

在一般系統中，應答協議部分往往采用結構化設計方法。應答協議一般通過循環等待并判斷超時條件是否成立來實現，或者通過調用支持超時操作的函數來實現，即如果在指定時間內無法滿足條件，則進入超時狀態，并執行相應處理，否則順序執行下一步。

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

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

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

四、結論

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

[1]陳文波，黃麗華，陳琪彰，潘善琳.企業信息系統實施中的意義建構：以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]周水銀，陳榮秋.大規模定制的發展與應用研究 [J].中國軟科學，2003(1)：155-156.

[4]全春光.供應商管理庫存研究現狀及展望 [J].技術經濟與管理研究，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]廖吉林，劉建一.論企業信息化建設中的業務流程重構問題[J].技術經濟與管理研究，2009(03)：48-50.