[1]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]
Copy

Complexity of variance optimization: from production lines to computer networks

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 4 Number of periods: 2009 6 Page number: 475-482 Column: 综述 Public date: 2009-12-25
Title:
Complexity of variance optimization: from production lines to computer networks
Author(s):
XU Xiao-yun; WANG Long
Department of Industrial Engineering and Management, Peking University, Beijing 100871, China
Keywords:
completion time variance;  waiting time variance;  quality of service;  just-in-time
CLC:
TP3
DOI:
10.3969/j.issn.1673-4785.2009.06.002
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. Justintime 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: McGraw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.
［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 singlemachine 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. Multimachine 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.
Similar References:

Memo

-

Last Update: 2010-02-17

Copyright © CAAI Transactions on Intelligent Systems