[1]许晓云,王?? 龙.方差优化问题的复杂性：从生产线到计算机网络[J].智能系统学报,2009,4(6):475-482.[doi:10.3969/j.issn.1673-4785.2009.06.002]
XU Xiao-yun,WANG Long.Complexity of variance optimization: from production lines to computer networks[J].CAAI Transactions on Intelligent Systems,2009,4(6):475-482.[doi:10.3969/j.issn.1673-4785.2009.06.002]
点击复制
XU Xiao-yun,WANG Long.Complexity of variance optimization: from production lines to computer networks[J].CAAI Transactions on Intelligent Systems,2009,4(6):475-482.[doi:10.3969/j.issn.1673-4785.2009.06.002]
方差优化问题的复杂性：从生产线到计算机网络
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
4
期数:
2009年第6期
页码:
475-482
栏目:
综述
出版日期:
2009-12-25
- Title:
- Complexity of variance optimization: from production lines to computer networks
- 文章编号:
- 1673-4785(2009)06-0475-08
- 分类号:
- TP3
- 文献标志码:
- A
- 摘要:
- 在许多工程系统中，方差优化对保持性能稳定、提高系统服务质量具有重要的意义.方差优化问题也是组合优化中较困难的二阶离散优化问题.通过引入完成时间方差和等候时间方差这2个重要的子类问题，具体论述了此领域的研究现状与最新理论进展，讨论了方差优化的2个重要特例问题的复杂性，指出了其中一个特例问题属于P类问题, 其所有最优解均具有对称螺旋结构，且此螺旋型的结构还存在于一大类任意阶的偏差问题.基于方差问题的特性，总结并拓展了其在实际工程领域、特别是计算机网络系统领域的新应用.
- 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 optimization. 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 implementation of the variance optimization problem were summarized and further extended to the area of computers and their network systems.
- 参考文献/References:
-
［1］CHENG T C E, PODOLSKY S. Justintime manufacturing: 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 internet［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: McGrawHill/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.
［5］YE N. Secure computer and network systems: modeling, analysis and design［M］. London, UK: John Wiley and Sons, 2008: 53-79.
［6］GAREY M R, JOHNSON D S. Computers and intractability: 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 Science, 1972, 18(9): 518-528.
［8］YE N. QoS-centric stateful resource management in information systems［J］. Information Systems Frontiers, 2002, 4(2): 149-160.
［9］VENTURA J A, WENG M X. Minimize singlemachine 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 & Industrial Engineering, 2007, 52(1): 41.
［12］CAI X. Minimization of agreeably weighted variance in single machine systems［J］. European Journal of Operational Research, 1995, 85(3): 576-592.
［13］SCHRAGE L. Minimizing the time-in-system variance for a finite jobset［J］. Management Science, 1975, 21(5): 540-543.
［14］KANET J J. Minimizing variation of flow time in single machine systems［J］. Management Science, 1981, 27(12): 1453-1459.
［15］VANI V, RAGHAVACHARI M. Deterministic and random single machine sequencing with variance minimization ［J］. Operations Research, 1987, 35(1): 111-120.
［16］HALL N G, KUBIAK W. Proof of a conjecture of Schrage about the completion time variance problem［J］. Operations Research Letters, 1991, 10(8): 467-472.
［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.
［18］BAGCHI U, SULLIVAN 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.
［19］De P, GHOSH J B, WELLS C E. On the minimization of completion time variance with a bicriteria extension［J］. Operations Research, 1992, 40(6): 1148-1155.
［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, 1993, 70(3): 289-303.
［21］KUBIAK W. New result on the completion time variance minimization［J］. Discrete Applied Mathematics, 1995, 58(2): 157-168.
［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.
［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): 3069-3083.
［24］HALL N G. Single and multiple processor models for minimizing completion time variance［J］. Naval Research Logistics Quarterly, 1986, 33(1): 49-54.
［25］CAI X, CHENG T C E. Multimachine scheduling with variance minimization［J］. Discrete Applied Mathematics, 1998, 84(1/3): 55-70.
［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.
［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.
［28］KUBIAK W. Completion time variance on a single machine is difficult［J］. Operations Research Letters, 1993, 14(1): 49-59.
［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.
［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.
［31］CAI X. A solvable case of the variance minimization problem［J］. Applied Mathematics Letters, 1993, 6(6): 97-100.
［32］XU X. Generalized completion time deviation problem on a single machine［R］. Beijing:Peking University， 2009.
［33］PINEDO M L. Scheduling: theory, algorithms, and systems［M］. 3rd ed. New York, USA: Springer, 2008: 111-142.
备注/Memo
收稿日期：2009-06-21.
基金项目：国家自然科学基金资助项目（10972002）.
作者简介：
许晓云，男，1980年生，博士后，主要研究方向为计算复杂性理论、计算机运筹规划以及计算机网络等.发表学术论文多篇.
王 龙，男，1964年生，教授、博士生导师，主要研究方向为复杂系统智能控制、多机器人系统的协调与控制、网络化控制系统的分析与综合、集群行为与集群智能、演化博弈与群体决策等，特别是在参数摄动系统、离散事件系统、混合集成系统的分析与控制方面，作出了突出贡献，取得了一系列具有国际水平的重要成就.日本学术振兴基金获得者.其研究成果被国内外广泛引用，并获得国家教委霍英东奖（研究类一等奖）、国家自然科学奖、国家教委科技进步奖（一等奖）、第一届Ho Outstanding Paper Award、第一届关肇直控制理论奖等多项奖励.
更新日期/Last Update:
2010-02-17