徐 揚(yáng)

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

一、引言

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

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

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

二、模型定義與證明

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

1.模型定義

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

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

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

圖2 認(rèn)證-校正過程

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

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

2.問題描述

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

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

3.定理證明

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

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

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

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

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

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

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

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

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

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

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

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

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

證畢。

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

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

三、討論

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

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

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

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

四、結(jié)論

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

[1]陳文波，黃麗華，陳琪彰，潘善琳.企業(yè)信息系統(tǒng)實(shí)施中的意義建構(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)濟(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]廖吉林，劉建一.論企業(yè)信息化建設(shè)中的業(yè)務(wù)流程重構(gòu)問題[J].技術(shù)經(jīng)濟(jì)與管理研究，2009(03)：48-50.