第4卷第6期 智能系统学报 Vol.4 No.6 2009年12月 CAAI Transactions on Intelligent Systems Dec.2009 doi:10.3969/j.issn.16734785.2009.06.002 方差优化问题的复杂性：从生产线到计算机网络 许晓云，王龙 (北京大学工学院，北京100871) 摘要：在许多工程系统中，方差优化对保持性能稳定、提高系统服务质量具有重要的意义.方差优化问题也是组合 优化中较困难的二阶离散优化问题.通过引入完成时间方差和等候时间方差这2个重要的子类问题，具体论述了此 领域的研究现状与最新理论进展，讨论了方差优化的2个重要特例问题的复杂性，指出了其中一个特例问题属于P 类问题，其所有最优解均具有对称螺旋结构，且此螺旋型的结构还存在于一大类任意阶的偏差问题.基于方差问题 的特性，总结并拓展了其在实际工程领域、特别是计算机网络系统领域的新应用 关键词：完成时间方差；等候时间方差；服务质量；准时化生产原则 中图分类号：TP3文献标识码：A文章编号：16734785(2009)06047508 Complexity of variance optimization: from production lines to computer networks XU Xiao-yun,WANG Long (Department of Industrial Engineering and Management,Peking University,Beijing 100871,China) Abstract:Variance optimization is essential to providing performance stability and quality of service (QoS)in many engineering systems.It is widely regarded as one of the more difficult problems in quadratic combinatorial optimiza- tion.Two important subclasses are the completion time variance problem and the waiting time variance problem. The current status of research and new theoretical developments in these fields needed to be examined in detail. The complexities of two special cases of these problems were explored,and one of them was shown to belong to Class P.It was further shown that a symmetrical spiral-shaped structure inheres in all optimal solutions of this case, and also exists in a more generalized case of the deviation problem with arbitrary order.Aspects of practical imple- mentation of the variance optimization problem were summarized and further extended to the area of computers and their network systems. Keywords:completion time variance;waiting time variance;quality of service;just-in-time 方差作为一种描述系统不确定性的数学概念，流程具有重要影响.系统中方差如果过大，工作的完 在实际中常用于衡量系统的准确反应能力和服务质成则很难做到准时，时间上不是过早就是过晚，整个 量的优劣.它是准时化生产原则(just-in-time,JT) 流程中的制品（work in process,WP)数量将显著 的核心组成部分，也是评估服务质量(quality of 增加，使得生产系统的缓存区迅速被占满，整个流程 service,QoS)的重要标准之一21，在生产领域与计 陷入迟滞3].由于方差优化问题数学结构整齐，且 算机领域都有着广泛的应用。 具有很强的实际应用背景，因此近年来在学术领域 方差优化问题是许多工程系统中经常碰到的一 受到了广泛的关注4.作为一大类有关提前(earli: 类问题.例如在生产系统中，工件的准时完成对生产 ness)和拖期(tardiness)规划问题的代表，其相关研 究已由传统的生产领域拓展到了计算机和网络领 收稿日期：20090621. 基金项目：国家自然科学基金资助项目(10972002)， 域5. 通信作者：许晓云.E-mail:xiaoyun.x@pku.edu.cm 本文将对方差优化问题的相关研究进行全面回
·476 智能系统学报 第4卷 顾，并探讨其问题本身的复杂性以及相应2个特例 证明了在单台服务器(single machine)上，WCTV问 问题的复杂性.本文进一步指出其中一个特例问题 题和WWTV问题是等效的，即给定WCTV问题的 存在特殊的解析结构，属于P类问题6，且最优解 一个任意可行解，将其工作顺序逆反后将成为 具有螺旋状的几何特征，并指出螺旋最优性的结果 WWTV问题的可行解，且目标方程的值与原WCTV 广泛存在于一大类任意阶的偏差问题： 问题相等.转换过程只需O().这个重要性质的发 现，使得后续研究只需要处理WCTV问题或是 1方差优化问题研究现状 WWTV问题中的一个即可，且一个问题的任何有关 方差优化问题最早由Merten和Muller]于 工作排序的性质都可以直接转换为另一个问题的相 1972年在解决计算机文件整理系统问题时提出.他 关性质.这个结果深化了对该问题排序结构的认识， 们定义了规划中最常见的2类方差优化的问题：第 实现了单台服务器上的WCTV问题和WWTV问题 1类称为“加权完成时间方差(weighted completion 的统一 time variance,.WCTV)优化”，也称“流程时间方差 加权二阶排序问题在数学结构上的复杂性对直 (weighted flow time variance)优化”.此类优化问题 接研究原问题提出了很高的要求.因此，很多研究者 着眼于工作时间的一致性，使得同一组工作尽可能 都转向研究原问题的一类重要的特例，即所有工作 在接近的时间完成，从而体现出服务稳定性；第2类 都具有相同权重的情况.由于这种假设在实际生产 问题称为“加权等候时间方差(weighted waiting time 中普遍存在3)，应用也相对广泛，因此得到了学术 variance,.WWTV)优化”.此类优化问题则侧重描述 界的重视.对于此类特例问题，相应的WCTV和 队列特性及用户体验，使得通过处理器的各个工作 WWTV问题的标称符号也就化简为CTV(comple- (或用户)在队列中等候的时间尽可能相等.这2类 tion time variance)WTV(waiting time variance). 问题均为生产系统T研究1和计算机领域QoS优 Elon和Chowdhury1研究了单台服务器WTV问 化研究[8]的重要组成部分，因此一直受到学术界的 题，并提出了其最优解一定呈V型，即最小的工作 广泛关注. 之前的工作一定都按从大到小排列，而其之后的工 Merten和Muller刃提出了方差优化问题的基本 作一定都按从小到大排列.这也是继Merten和 数学模型：给定n个工作，由j表示其编号.每个工作 Muller等效性证明后的最重要的结果之一.此性质 的加工时间p和权重均为正常数且已知，如何将 给出了最优解必须服从的几何形式，大大降低了寻 这些工作排序，才能使得目标方程公(9~©)》 找最优解的难度，并为后续启发式算法的研究搭建 了平台.i等进一步指出单台服务器WTV问题 (wCTV问题)或Σ，(-o)2(WWTV问题)最 的最优解一定是紧凑的(tight schedule),证明了单 机最优解的可穷举性.Ci2]将V型最优的结果推 小化？在目标方程中，c为第j个工作的完成时间， 广到了一般的WCTV问题.他指出，如果工作较大 c=（9)()是加权平均完成时间；同理， 意味着其权重较小（称为“一致加权”(agreeably weighted)),则最优解仍将维持V型.尽管“一致加 ,为第j个工作的等待时间，0=（∑马四，）/（∑） 权”属于非常强的条件，但由于其解释了一大类原 为加权平均等候时间， 问题的最优解结构，因此也具有重要的意义， 可以看出，此类问题属于优化中的二阶组合优 对于单台服务器CTV问题的研究也有一系列 化问题.其目标方程中既包括c与c(或w;与w)时 有意义的成果.1975年Schrage1s]证明了最大的工 间差的二阶罚函数，又附加了对工作权重的考虑，数 作一定会排在最前，并对前4个最大的工作在最优 学结构较一般一阶规划问题复杂.从整数规划建模 解中对应的位置提出了猜想，此猜想后来也称为 的角度看，其目标方程与约束方程的构造形式将至 Schrage猜想.针对于此，Kanet4提出了一个包含8 少不低于二阶91，很可能达到三阶甚至四阶。 个工作的反例.Vani和Raghavachariis1随后给出了 方差优化问题的研究工作在过去30年中持续 对包含18个以下工作的Schrage猜想的弱条件证 开展，取得了一系列重要的成果.Merten和Muller) 明.Schrage猜想的完全解决由Hall和Kubiak[16]于
第6期 许晓云，等：方差优化问题的复杂性：从生产线到计算机网络 ·477· 1991年完成.与猜想的原命题不同，他们指出只有 并行服务器环境下均属于Class P问题，并提供了相 前三大（而不是前四大）的工作的位置是符合原始 应的算法；Cai和Chengt25]发现了并行服务器CTV 猜想的.此外，Manna和Prasad7]给出了单机CTV 问题最优解所具备的一系列重要性质，并证明了在 问题中最小工作可能位置的一个界定；Bagchi等 并行服务器下CTV问题与二阶公共到期时间方差 人[us考虑了一个二阶的公共到期时间(common due 问题等效，从而推广了Bagchi等人的单台服务器结 date)问题，即优化完成时间与公共到期时间之差的 果1.基于最优解的性质，Cai和Cheng提出了2个 平方和(min名(9-4).他们证明了单机CcV 算法：其中一个为最优算法(optimal algorithm),可 以在0(n2p(P-p)-/[m"(m-1)!]2)时间 问题与公共到期时间问题等效，指出了方差优化问 内得到最优解，其中m为平行服务器个数，P= 题是公共到期时间问题二阶罚函数的一个特殊形 式.这个结果建立了单台服务器下方差优化问题与 立，P产为m个最大的工作的加工时间之和；另一 公共到期时间问题的直接关联，也进一步拓展了方 个算法为近似算法，计算速度较最优算法快，可以在 差优化问题的应用领域： 0(nP(P-m)m-/[m2(m-1)])时间内找到一 随着更多更好的性质的发现，单机CTV和WTV 个接近最优解的近似解.由于他们的算法中存在隐 问题的算法研究也取得了长足的进展.Elon和 性穷举，因此计算速度相对较慢.在启发式算法的设 Chowdhury1针对WTV问题提出了第一组启发式算 计方面，Marango等人[26针对同样的问题提出了4 法，其结构非常简单，但并不能保证找到最优解；D 个不同的启发式算法，比较结果显示，模拟退火算法 等人为CTV问题提出了O(n2∑P)的伪多项式 (simulated annealing)表现最优，在验证集测试中获 得了离最优解下限5%~10%的解，但是，由于文章 时间算法，也从一个角度揭示了CTV问题不可能是 强NP-hard问题(NP-hard in the strong sense6);Gup 中给出的相应模拟退火计算设定的描述过于简略， ta等0]对CTV问题提出了一个基于遗传算法的启发 因此不利于重复试验结果.在序列特征方面，Xu和 式算法；Ventura和Weng9从建模出发，对CTV问题 Ye71从并行服务器WTV问题入手，证明了CTV问 提出了一个新的（相对于Kubiak的动态规划模 题和WTV问题在并行服务器上也是等效的，即任 型21们)二阶整数规划模型，并通过拉格朗日优化方法 取其中一个问题的可行解，就可在O(mnlg n)时间 得到了问题的最优解的一个下限.在近似算法方面， 内(m为平行服务器个数)建立另一个问题的对应 最好的结果目前由Kubiak[2]保持，其算法可以在 可行解，且两者目标方程值相同.这个证明将Merten 0(n2/∈)内得到任意逼近最优解的结果，但是由于 和Muller的等效性结果71从单台服务器环境推广 其算法基于动态规划，且结构相对复杂，因此不利于 到了并行服务器环境.另外，Xu和Ye证明了在多台 实时实现.最近的一个针对WTV的启发式算法由Ye 并行服务器的情况下，最优解不一定是紧凑的，即服 等人2a提出，称为“Yelf螺旋”.由于“Yelf螺旋”的 务器牺牲一定的等候时间将有利于最小化方差.此 计算结果在统计上优于Eilon和Chowdhury1的一系 结果也显示出ⅱ等在单机环境最优解的紧凑结 列启发式算法，且算法结构非常简单，因此适用于如 果是不可以简单推广的， CPU规划等需要高速运算的环境中. 2方差优化问题的复杂性 作为一个二阶组合优化问题，方差优化在单机 情况下已经相对复杂，当其推广到并行服务器( 由于方差优化问题的重要性，其计算复杂性一直 dentical Parallel Machine)环境中时则难度更高.这 受到广泛的关注，然而，这方面的研究工作进展相对 也一定程度上导致了并行服务器下有关CTV和 缓慢.这一方面是由于原问题本身结构复杂，直接构 WTV的研究成果相对稀少.Hal24]从到期时间角度 建最优算法的难度较大；另一方面也是因为一直没有 出发，解决了一个一阶的类似问题，即优化完成时间 能够找到合适的其他NP-hard6问题与之相对应. 与公共到期时间(common due date)之差的绝对值 在试图直接处理原问题遇到困难后，研究者开 始转为考虑原问题的2个常见的特例情况，即所有 的和（∑1S-d1).Hall证明了此问题在单台和 工作具有相同权重(“等权重”)和所有工作具有相
478 智能系统学报 第4卷 同的加工时间(“等大小”).与原问题相比，这2个 行序列，将其顺序逆反后，就可以得到一个与原序列 特例问题都仅考虑了工作的一个属性（大小或权 目标方程值相同的序列.然而对于其最优解的结构， 重)，显著降低了问题难度， 他们表示： Merten和Muller们首先研究了这2种特例情 "In the search for the minimum variance sched- 况.他们证明了在“等权重”和“等大小”这2种情况 ules,certain relationships can be derived between 中，WTV和CTV问题的可行序列本身都存在对偶 schedules for the special problems where either all 性，即对任意一个可行序列都存在一个对偶序列，其 weights are equal or all the processing times are equal. 产生的目标方程值和原序列相同，且构建难度不超 Even in these special cases,the characteristics of the 过0(n). optimum schedules are not obvious. 对偶序列在一般规划问题中属于比较少见的强 即“等大小”和“等权重”这2类特例问题的最 性质.其发现也引发了企图证明特例问题为Class P 优解结构都不显然 的热潮.由此也产生了一系列例如Schrage猜想1a] 在1972-1992年的20年中，相关研究工作主要 最小工作的定位和最大三工作定位1等试图逼 集中在解决方差优化中的“等权重”特例问题上.这 近最优解序列结构的重要成果 很大程度上是由于“等权重”的情形在传统的生产 然而研究显示，即使是这2种特例情况，计算复 规划中十分常见.在传统生产系统中，工件的加工时 杂性的证明也具有相当的难度.对偶序列的存在虽 间往往不一，而重要程度对于整个系统来说却几乎 然体现了可行解集的良好的对称性，但是由于对偶 相同.另外，在很多情况下，由于生产需要，工厂车间 性仅证明了等效序列的存在，并没有直接阐述最优 内加工机器的布局往往是根据所需处理工件的加工 解本身的序列构成，因此并没有直接证明问题的复 时间而不是优先级来制定的3).由此可见，解决“等 杂性 权重”的特例情况对处理传统工业领域的问题具有 直至1999年，Kubiak2a]通过构建Submodular 更直接的实用价值.由于规划领域的研究一直都是 Boolean Program,证明了单机情况下CTV“等权重” 以解决传统生产行业的问题为主导，这也一定程度 的特例情况为NP-hard.这个证明结束了自1972年以 上促使了“等权重”问题先于“等大小”问题得到研 来对“等权重”问题是否为NP-hard的争论，也间接证 究和解决 明了原问题的复杂度至少为NP-hard.结合文献[19] 然而，随着计算机和网络技术的迅速发展，“等 对此问题的伪多项式时间算法，可以看出Kubiak实 大小”的特例情况也找到了重要的应用领域.在计 际上证明了“等权重”特例问题属于普通NP-hard问 算机系统中，工作（或指令）在下放到CPU处理时会 题(NP-hard in the ordinary sense[6).这表明，即使规 被分割为大小相等的数据包9]，这些数据包根据各 划问题的可行解集具有非常良好的性质（例如对偶 自所包含数据的不同，会被系统指定不同的处理优 性)，问题也有可能具有高计算复杂性， 先级.在批处理的过程中，这些数据包会在缓存区被 整合为具有固定大小的批次，然后按照CPU时钟顺 3方差优化问题的特例：螺旋最优性 序逐批处理.在这种处理模式中，数据包大小相等而 3.1方差优化中的“等大小”特例 优先级各异，CPU以固定数量为单位逐批对工作进 随着Kubiak成功地将“等权重”的特例问题归 行处理，这与“等大小”特例问题的设定几乎完全相 为NP-hard,关于方差优化原问题计算复杂性的讨 同.另外，随着网络视频、音频以及各种其他网络计 论也就此告一段落.但是，对于方差优化问题的另一 算服务的发展，如何有效地提升服务质量(QoS)成 类特例，即工作加工时间相等(“等大小”)的问题， 为近年来计算机领域的研究热点.网络服务研究表 在计算复杂性方面却没有相关的进展。 明，理想的计算机网络服务系统会对用户需求提供 “等大小”的特例情况最早由Merten和Mul- 统一而稳定的服务2]，而完成时间和等候时间是其 r]作为原问题的一个简化形式提出.他们证明了 中2个重要的性能指标.在本质上，方差优化问题要 在单台服务器情况下，无论是WTV问题还是CTV 求工作的完成时间或等候时间尽可能的一致，这也 问题，其可行序列都具有反对偶性，即对任意一个可 正反映了QoS对服务稳定性的需求.Merten和Mull-
第6期 许晓云，等：方差优化问题的复杂性：从生产线到计算机网络 ·479· er提出的网络文件整理系统[]和Ye等人提出的网 且产生的目标方程值也是相同的.这个结果也与 络准入控制系统「0都是这类应用的典型实例 Merten和Muller反对偶性证明相吻合 3.2螺旋最优性 显而易见，构建如图1和图2的螺旋在计算上 以完成时间优化为例，单台服务器环境下的 是非常简单的.在问题中的权重排序随机给出时，建 “等大小”特例情况的定义如下： 立螺旋只需要O(n+lgn),而在权重排序给定的 给定n个工作，加工时间全部相同，其区别反映 情况下则更为容易，仅需O(n). 在不同的权重上.如何能找到这些工作的一个排序， 最优解的螺旋特征具有重要意义，从复杂性理 使得完成时间的加权方差最小，即 论的角度，它证明了“等大小”的特例问题属于Class minΣy(g-c) P,而不是NP-hard,结束了长久以来学术界对这个 问题复杂性的争论.在数学结构上，“等大小”问题 Ca311的研究显示此问题可解，但并未指出其最优 与“等权重”问题均属于二阶组合优化问题，且目标 解的几何结构必须呈现对称螺旋形.为了描述方便， 方程的构成非常相似，但却在计算复杂性上出现了 考虑如下的简单情形： 巨大差异，这是一个很有趣的现象.从解的几何结构 给定9个工作，工作大小均相等，而权重为1， 角度，对称螺旋的构型在形式上拓展了已知的规划 2,…,8,9.这些工作在单台服务器上按一定顺序逐 解的几何模式（包括最小时间优先、最大时间优先 个完成.此问题的最优解的排序形式如图1和图2 和简单V型等)，也从另一个侧面解释为什么Ye等 所示： 人提出的Yef螺旋a1启发式算法会提供好的结果。 从实际应用的角度，螺旋的结果使得计算最优解的 复杂程度变成像排序一样简单，而且理论上任何能 够进行排序操作的机器都可以完成这样的工作.算 法的易用性使得那些仅能完成基本排序寻址操作的 简单网络服务器都可以直接采用这个算法，一般的 计算型CPU则更可以胜任这种简单的操作， 图19个工作情况下的螺旋最优（形式1） 在优化方差的前提下，螺旋最优性指出：重要的 Fig.1 Spiral optimality in a nine job case (Form 1) 工作的“重要度”并不体现在它的完成时间最早，而 是体现在它的完成时间最准确.从目标方程可以直 观看出，越重要的工作应该放置在越接近c的位置 上，换言之，如果认为c是公共到期时间「18]，则优化 的意义就在于令重要工作的完成时间尽可能准时完 成，从而提高系统整体服务的一致性.最优解的螺旋 特征也正体现了这样的特点.从图1和图2中都可 以明显看出，权重较高的工作都被集中放置在中间， 图29个工作情况下的螺旋最优（形式2） 而相对权重较低的工作则被分配在两侧，这样使得 Fig.2 Spiral optimality in a nine job case (Form 2) 值得强调的是，本文中给出的螺旋线仅为结构 高权重的工作能够更准时地完成，也为后续处理环 示意，不同的画图方式或可产生相同示意效果的图 节的时间准确性打下了良好的基础。 为了不产生歧义，给出图1和图2中的螺旋线作法： 3.3一阶螺旋 螺旋线自具有最小权重的工作开始，螺旋向内，到权 值得注意的是，螺旋最优性在规划问题中尽管 重最大的工作结束，螺旋线在起始端的初始旋转方 少见，但并不是这个问题独有的.Kanet4在1981 向垂直向下. 年考虑了“等权重”的方差优化问题.他并没有对模 最优解的排序既可以为图1中的形式，也可以 型直接求解，而是提出了一个与二阶“等权重”优化 为图2中的形式.这2种螺旋形式不仅结构对称，而 模型相对应的一阶模型，其目标方程如下：
·480 智能系统学报 第4卷 minΣΣ1c,-Sl. 需要一种怎样的方程结构？ “台台 Xu321考虑了如下的一个广泛的目标方程形式： Kanet的模型令完成时间之间的差别尽可能减 小.从数学形式上看，这个模型可以认为是方差模型 min∑∑g1g与-cl. 台台 的一阶形式.在方差优化中，目标方程采用的是二阶 式中：a和B为常数，且α≥0，B>0. 罚函数，而Kanet模型中采用的是一阶罚函数， 以上的问题称为“广义加权完成时间偏差问 Kanet证明了这个问题属于Class P,并指出此 generalized weighted completion time deviation 问题任意实例(instance)的最优解集都包含 problem,GWCD).从方程形式可以看出，此目标方 2exp([n/2]-1)个元素.文章也给出相应的一个复 程试图减小工作完成时间之间的差别，且要求重要 杂度为O(n+nlgn)的最优算法. 的工作应在相对接近的时间完成.目标方程中对工 而Kanet并没有发现，在这个一阶“等权重”问 作重要性和完成时间接近程度的要求十分灵活，在 题的最优解集中存在一个且仅有一个螺旋最优解。 实际应用中可以通过调整α和B的大小来控制. 考虑如下的简单情形：给定7个工作，每个工作权重 GWCD问题的目标方程结构自由度很高，可以 相同，加工时间大小为1、3、5、7、9、11、13.则问题的 转化为很多规划领域的其他常见问题.当α=0， 最优解如图3所示： B=1时，此问题可以转化为上一节提到的Kanet模 型4；当&=1，B=1时，此问题成为了Kanet模型 的一阶加权推广；当α=1，B=2时，此问题可以转 化为一般的完成时间方差优化问题2]；当α=0， B=2时，此问题转化为方差优化问题中“等权重” 的特例情况，进而等效于Bagchi等人提出的优化完 成时间与公共到期时间之差的平方和问题]；当将 完成时间c变为等候时间o,此问题又可转化为相 图37工作情况下的Kanet螺旋 应的等候时间方差问题] Fig.3 Kanet spiral in a seven job case Xu的研究指出1，在存在权重(a>0)的一 Kanet螺旋的几何示意图在本文中的作法如下 般情况下，如果工作大小相等，则此问题的最优解一 所示：螺旋线自加工时间最大的工作开始，螺旋向 定呈螺旋型，且任意紧凑可行解的反序都与原序列 内，到最小的工作结束.螺旋线在起始端的初始旋转 目标方程值相同.这个结果将螺旋最优性和排序对 方向垂直向下， 称性从简单的二阶拓展到任意阶的情况，推广了 从图3可以看出，螺旋线是由第一个位置开始 Merten和Muller以及Cai]的相关结论，证明了螺 的.可以证明，Kanet一阶问题中的最优螺旋线一定 旋型排序广泛存在于一大类非常规性能量度问题 是从第一个位置开始.这是由最大的工作一定要放 (non-regular performance measure)中，极大拓展了结 在第一个位置31所决定的.当Kanet问题从一阶形 论的适用范围。 式升级为二阶时，不仅难度变为NP-hard2],而且其 除了螺旋最优性外，Xu从模型中还可以得到一 螺旋最优性也没有被相应的二阶“等权重”问题所 些更一般的结论，例如：当工作的大小和权重呈正比 继承，而是在二阶“等大小”问题中重新出现，且其 时（P/=c,c为正常数)，最优的工作顺序在a= 最优解的形式也由很多种变成了只能为左右螺旋的 1,B≥1时为LPT(longest processing time),即工作 2种.这在一定程度上体现了二阶形式对方程解的 按从大到小排为最优.另外，此模型在任意阶都等效 结构要求更为严格。 于相应的等候时间偏差问题(generalized weighted 3.4广泛的螺旋最优性 waiting time deviation problem,GWWD),即将任一问 螺旋型是一个良好的数学结构，它的几何形式 题的紧凑可行解逆序就可以得到其对应问题的一个 优美，而且计算非常简单.随之而来的问题是：类似 可行解，且目标方程值相等.此结果将Merten和 的螺旋形式是否广泛存在？产生这种螺旋型最优解 Muller的二阶等效性结果1推广到了任意阶，拓展
第6期 许晓云，等：方差优化问题的复杂性：从生产线到计算机网络 ·481· 了这2类问题等效性的适用范围， 输等需要更快速、更稳定性能的环境中.新的应用领 域对原有的优化问题和处理方式也提出了新的要 4结束语 求：一方面，问题的变量出现了新的限制（如要求工 本文回顾了方差优化问题的发展.对其2个特 作大小一致、权重各异等)：另一方面，问题的解法 例问题的工程背景、数学模型和研究进展进行了综 也要求必须简单高效.以网络服务器为例，一般的网 述，指出其中一类特例问题属于Class P,且发现具 络服务器每秒钟需要处理超过1MB的数据流量， 有螺旋最优性.还进一步指出螺旋型的存在并不是 其中央处理器也只能完成类似排序的简单操作9] 此问题独有的性质，在其他相关问题中也有出现，并 这就意味着非排序类的“复杂”算法，如模拟退火算 可以拓展到任意阶的情况.螺旋型的结构简单，实现 法、遗传算法、分支定界法等将很难在这些应用领域 难度与排序相仿且为最优解，可以直接应用于CPU 得以实现.这也对推度较高的规划问题的解决方法 规划等快速计算环境.螺旋型是一种解结构的强性 提出了新的挑战， 质.它一方面显示了问题解的特殊几何特征，另一方 向也是一类问题的最优解.本文指出，在工作大小相 参考文献： 等而权重各异时，螺旋最优性广泛存在于一大类非 [1]CHENG T C E,PODOLSKY S.Just-in-time manufactur- 常规性能量度问题中.是否工作大小不等时也存在 ing:an introduction[M].2nd ed.London,UK:Chapman 类似性质则值得进一步探讨.另外，给出螺旋最优性 &Hall,1996:6-12. 的更一般的存在条件也将对解决类似问题提供有效 [2]CHEN Y,FARLEY T,YE N.QoS requirements of network applications on the intemet[J].Information,Knowledge, 的帮助： Systems Management,2003,4(1):55-76. 从解决方差优化问题的文献数量上看，直接处 [3]HOPP W J,SPEARMAN M L.Factory physics[M].2nd 理原命题（既包含工作大小，也包含权重）的结果相 ed.New York,USA:MeGraw-Hill/Irwin,2000:287-331. 对稀少，大多数研究都在处理原命题下的各类子问 [4]BAKER K R,SCUDDER G D.Sequencing with earliness 题.由于方差问题的广泛性与实用性，对原命题相应 and tardiness penalties:a review[J].Operations Research, 的研究工作可以在未来进一步开展. 1990,38(2):193-242. 此外，从文中的Kanet螺旋的目标方程可以看 [5]YE N.Secure computer and network systems:modeling,a- 出，此类问题与方差问题非常类似，是一种利用一阶 nalysis and design M].London,UK:John Wiley and 手段描述完成时间（或等待时间）离散程度的方法 Sons,2008:53-79 [6]GAREY M R,JOHNSON D S.Computers and intractabili- 这种简化一定程度上保持了描述的物理量的基本结 ty:a guide to the theory of NP-completeness[M].New 构，并显著降低了问题的复杂性.因此，将此类方程 York,USA:W H Freeman and Company,1979:1-181. 推广到既包含工作大小，也包含权重的情况将是一 [7 MERTEN A G,MULLER M E.Variance minimization in 个有意义的研究方向。 single machine sequencing problems[J].Management Sci- 目前方差优化问题的研究工作主要集中在单台 ence,1972,18(9):518-528: 服务器上.在大型生产或并行计算环境中，常常存在 [8]YE N.QoS-centric stateful resource management in informa- 多台服务器并联同时处理工作的情况3).因此在多 tion systems[J].Information Systems Frontiers,2002,4 台并行服务器的环境中考虑方差优化问题也是一个 (2):149-160. 有意义的研究方向.另外，研究还可以进一步扩展到 [9]VENTURA J A,WENG M X.Minimize single-machine 存在混合连接结构的job shop中，相关的理论进展 completion time variance [J].Management Science,1995, 41(9):1448. 将对方差优化的实际应用产生一定的指导意义. [10]EILON S,CHOWDHURY I G.Minimizing waiting time 相对于其他规划问题，方差优化问题更关注完 variance in the single machine problem[J].Management 成时间（或等待时间）的集中性和准确性.这也是计 Science,1977,23(6):567-575. 算机和网络服务质量评估的一个重要方面.随着计 [11]LI X,YE N,LIU T,et al.Job scheduling to minimize the 算机和网络技术的迅速发展，规划问题的研究对象 weighted waiting time variance of jobs[J].Computers 也从传统的工业领域转移到了如CPU调度、网络传 Industrial Engineering,2007,52(1):41
482· 智能系统学报 第4卷 [2]]CAI X.Minimization of agreeably weighted variance in sin- [26]MARANGOS C A.GOVANDE V.SRINIVASAN G.et gle machine systems[J].European Journal ofOperational al.Algorithms to minimize completion time variance in a Research,1995,85(3):576-592. two machine flowshop[].Computers and Industrial Engi- [13]'SCHRAGE L.Minimizing the time-in-system variance for a neering,1998,35(1/2)）:101-104 finite jobset[J].Management Science,1975,21(5)): [27].XU X,YE N.Minimization of job waiting time variance on 540-543. identical parallel machines[J].IEEE Transactions on Sys- [14]KANET JJ.Minimizing variation of flow time in single tems,Man,and Cybernetics,2007,37(5))::917-927. machine systems [J].Management Science,1981,27 [28]KUBIAK W.Completion time variance on a single machine (12)：1453-1459. is dffioult[J].Operations Research Letters,1993,14 [15]VANI V.RAGHAVACHARI M.Deterministic and random ①，：49-59. single machine sequencing with variance minimization [.NULL L,LOBUR J.The essentials of computer organiza- [I..Operations Research,1987,35(1)):111-120. tion and architecture[M].2nd ed.London,UK:Jones [16]]HALL N G,KUBIAK W.Proof of a conjecture of Schrage and Bartlett Publishers,Inc,2006:177-179. about the completion time variance problem[J.Opera- 30YE N,FARLEY T.LI X.et al.Batch scheduled admis- ions Research Letters,1991,10(8):467-472 sion control for computer and network systems[J].Infor- [17]]MANNA D K,PRASAD V R.Bounds for the position of mation Knowledge Systems Management,2005,5(4)): the smallest job in completion time variance minimization 211-226. European Journal of Operational Research,1999, [31]]CAI X.A solvable case of the variance minimization prob- 1142②))：411-419. lem[J].Applied Mathematics Letters,1993,6(6):97 [18]:BAGCHI U,SULIVAN R S,CHANG Y L.Minimizing 100. mean squared deviation of completion times about a com- [3XUX.Generalized completion time deviation poblem on a mon due date[J]:.Management Science,1987,33(7): single machine[R].Beijing:Peking University,2009. 894-906. [33]PINEDO ML.Scheduling:theory,algorithms,and sys- [19]]De P,GHOSH J B,WELIS C E.On the minimization of tems[M].3rd ed.New York,USA:Springer,2008: completion time variance with a bicriteria extension[J]. 111-142. Operations Research,1992,40(6):1148-1155. 作者简介： [20]]GUPTA M C,GUPTA Y P.KUMAR A.Minimizing flow 许晓云，男，1980年生，博士后，主 time variance in a single machine system using genetic al- 要研究方向为计算复杂性理论、计算机 gorithm[J].European Journal of Operational Research, 运筹规划以及计算机网络等.发表学术 [993,70(3):289-303. 论文多篇， [21]KUBIAK W.New result on the completion time variance minimization[J]].Discrete Applied Mathematics,1995. 58②157-168. [22]KUBIAK W,CHENG J,KOVALYOV M Y.Fast fully 王龙，男，1964年生，教授、博士 polynomial approximation schemes for minimizing comple- 生导师，主要研究方向为复杂系统智能 tion time variance[J].European Journal of Operational 控制、多机器人系统的协调与控制、 Research,,2002,137(2)::303-309. 网络化控制系统的分析与综合、集群 23]]YE N,LI X,FARLEY T.et al.Job scheduling methods 行为与集群智能、演化博弈与群体决策 for reducing waiting time variance[J].Computer and Op- 等，特别是在参数摄动系统、离散事件 erations Research,,2007,34(10)1;3069-3083. 系统、混合集成系统的分析与控制方面，作出了突出贡献， [4]HALLN G.Single and multiple processor models for mini- 取得了一系列具有国际水平的重要成就.日本学术振兴基 mizing completion time variance[J].Naval Research Lo- 金获得者.其研究成果被国内外广泛引用，并获得国家教委 gistics Quarterly,1986,33(1)):49-54. 霍英东奖（研究类一等奖）、国家自然科学奖、国家教委科技 [25]CAI X,CHENG T C E.Multi-machine scheduling with 进步奖（一等奖）、第一届Ho Outstanding Paper Award、第一 variance minimization[J].Discrete Applied Mathematics, 届关肇直控制理论奖等多项奖励. 1998,84(1/3):.5570
作者简介: 482· [33] PINEDO M L. Scheduling: theory,algorithms, and systems[ M] . 3rd ed. New York,USA: Springer,2008: 111-142. [15] VANI V,RAGHAVACHARI M. Deterministic and random single machine sequencing with variance minimization [J] . Operations Research,1987,35(1) :111-120. [32] XU X. Generalized completion time deviation poblem on a single machine[ R]. Beijing: Peking University,2009. [19] De P,GHOSH J B,WELIS C E. On the minimization of completion time variance with a bicriteria extension[J] . Operations Research,1992,40(6) : 1148-1155. [26] MARANGOS C A,GOVANDE V,SRINIVASAN G,et al. Algorithms to minimize completion time variance in a two machine flowshop[J] . Computers and Industrial Engineering,1998,35(1/2) : 101-104. 23] YE N,LI X,FARLEY T,et al. Job scheduling methods for reducing waiting time variance[J] . Computer and Operations Research,2007,34(10) : 等,特别是在参数摄动系统、离散事件 系统、混合集成系统的分析与控制方面,作出了突出贡献, 取得了一系列具有国际水平的重要成就.日本学术振兴基 金获得者.其研究成果被国内外广泛引用,并获得国家教委 霍英东奖(研究类一等奖) 、国家自然科学奖、国家教委科技 进步奖(一等奖)、第一届Ho Outstanding Paper Award、第一 王 龙,男,1964年生,教授、博士 生导师,主要研究方向为复杂系统智能 控制、多机器人系统的协调与控制、 网络化控制系统的分析与综合、集群 行为与集群智能、演化博弈与群体决策 届关肇直控制理论奖等多项奖励. 3069-3083. [29] NULL L,LOBUR J. The essentials of computer organization and architecture[ M].2nd ed. London,UK: Jones and Bartlett Publishers,Inc,2006: 177-179 [28] KUBIAK W. Completion time variance on a single machine is dffioult[J] . Operations Research Letters,1993,14 (1) : 49-59. 许晓云,男,1980年生,博士后,主 要研究方向为计算复杂性理论、计算机 运筹规划以及计算机网络等.发表学术 论文多篇. [31] CAI X. A solvable case of the variance minimization problem[J]. Applied Mathematics Letters,1993,6(6) : 97- 100. [21] KUBIAK W. New result on the completion time variance minimization[J] . Discrete Applied Mathematics,1995, 58(2) : 157-168. [12] CAI X. Minimization of agreeably weighted variance in single machine systems[J] . European Journal of Operational Research,1995,85(3) : 576-592. [17] MANNA D K,PRASAD V R. Bounds for the position of the smallest job in completion time variance minimization [J] . European Journal of Operational Research,1999, 114(2) : 411-419. 智 能 系 统 学 报 [13] SCHRAGE L. Minimizing the time-in-system variance for a finite jobset[J]. Management Science,1975,21(5) : 540-543 [20] GUPTA M C,GUPTA Y P,KUMAR A. Minimizing flow time variance in a single machine system using genetic algorithm[J]. European Journal of Operational Research, [993,70(3) :289-303. [25] CAI X,CHENG T C E. Multi-machine scheduling with variance minimization[J] . Discrete Applied Mathematics, 1998,84(1/3) :55-70. [27] XU X,YE N. Minimization of job waiting time variance on identical parallel machines[J] . IEEE Transactions on Systems,Man,and Cybernetics,2007,37(5) : 917-927. [18] BAGCHI U,SULIVAN R S,CHANG Y L. Minimizing mean squared deviation of completion times about a common due date[J] . Management Science,1987,33(7) : 894-906. [16] HALL N G,KUBIAK W. Proof of a conjecture of Schrage about the completion time variance problem[J]. Operaions Research Letters,1991,10(8) : 467-472. [24] HALL N G. Single and multiple processor models for minimizing completion time variance[J] . Naval Research Logistics Quarterly,1986,33(1) : 49-54. 第4卷 [30] YE N,FARLEY T,LI X,et al. Batch scheduled admission control for computer and network systems[J] . Information Knowledge Systems Management,2005,5(4) : 211-226. [14] KANET J J. Minimizing variation of flow time in single machine systems [J]. Management Science,1981,27 (12) : 1453-1459. [22] KUBIAK W,CHENG J,KOVALYOV M Y. Fast fully polynomial approximation schemes for minimizing completion time variance[J]. European Journal of Operational Research,2002,137(2) : 303-309