大规模个性化信息系统中的应答协议研究

徐 扬

（北京大学，北京 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.