Optimistic and Pessimistic Result of Planning and Scheduling Dynamie Processes
DOI:
https://doi.org/10.7494/csci.1999.1.1.3572Abstract
In many real-life circumstances decision problems arise. Optimisation problems can be for- mulated as decision problems as well. An optimisation problem can be expressed in terms of a model and a performance index. While the model describes the problem, the perfor mance index assigns a value to each feasible realisation of the problem [1],
An algorithm is a method to solve a class of problems with Computer. The computational complexity of an algorithm, which can be measured, is the cost. It is measured in runtime during which the algorithm is used to solve one of the problems. If the runtime is limited by a polynomial function of the amount of input data at most, the problem is said to be an easy one otherwise it is a hard problem. If a problem is easy it is enough to describe a method meeting such a constraint, when used to solve the problem. What does it mean that a problem is hard? The problem is hard when it is necessary to prove that it is impossible to find a fast method to perform the calculations which identify an optimal solution. There are a number of easy problems. Matrix inversion is easy: n * n matrix can be inverted with the Gaussian elimination method in time of cn at most. Sorting problem is easy as well. The fact that a computational problem is hard does not imply that its every instance has to be hard. The problem is hard when no algorithm can be pointed at, which could ensure a high performance for all instances of the problem. Notice that the amount of input data to the Computer in this example is smali [7].
In recent years there has been a growth in research which deals with the development and complexity analysis of combinatorial algorithms. Complexity measures are of two kinds: static, independent of the size and characteristics of the input data, and dynamie, dependent on the input data [3].
Downloads
References
Aho A.V., Hopcroft J.E., Ullman J.D.: The Design and Analysis of Computer Algorithms, Addison -W esley, Reading, MA. 1974
Berge C.: The Theory ofGraphs and itsApplications New York, John Wiley 1962
Cook J.: The Complexity o f theorem proving procedures Proc. Third Annual ACM
Symp. on Theory of Computing Machinery, New York, 1971, 151-158
Edmonds J.: Paths, trees, andflowers Canad. J. Math., 17, 1965, 449-467
Edmonds J., Karp R.M.: Theoretical improvements in algorithmic ejficiency for networkflowproblems J. Assoc. Comput. Mach., 19, 1972, 248-264
Garey M.R., Johnson D.S.: Approximation algorithms for combinatorial problems: an annotated bibliography Algorithms and Complexity: New Directions and Recent Results, J.F. Traub, ed., New York, Academic Press 1976,41-52
Garey M.R., Johnson D.S., Stockmeyer L.: Some simplified NP - complete graph
problems Theoret. Comput. Sci., 1, 1976,237-267
Karp R.M.: Reducibility among combinatorial problems Complexity and Computer Computations, R.E. Miller, and J.W. Thatcher, eds., New York, Plenum Press 1972, 85-104
KnuthD.E.:TheartofComputerprogrammingVolumeT.FundamentalAlgorithms, Addison - Wesley, Reading, MA. 1968
Knuth D.E.: The art of Computer programming Volume 2: Seminumerical Algo rithms. Addison - Wesley, Reading, MA. 1973
KnuthD.E.: Optimum binary search trees, Acta Informat. 1, 1971, 14—25
Turing A.M.: On computable numbers, with an application to the Entcheidungs problem Proc. London Math. Society, ser. 2, 42. 1937, 230-265; corrections, 43, 544-546
Wirth N.: Theprogramming language Pascal Acta Informat., 1, 1971,35-63
Baker K.R.: Introduction to Seąuencing andScheduling. New York, Wiley 1974 Conway, R.W., Maxwell W.L., Miller L.W.: Theory of scheduling. Addison - Wesley, Reading Mass. 1967
French S.: Seąuencing and Scheduling. New York, Wiley 1986
Filar T.: Application o f the Green Function in a Numeric Method fo r Heating Control o f Massive Charges. AGH Kraków 1982 Scientific Bulletins No. 799, 1982 Graham R.L., Lawler E.I., Lenstra
J.K., Rinnooy Kan A.H.G.: Optimisation and approximation in deterministic seąuencing and scheduling. Annals of Discrete Mathematics. 5, 1981, 287-326
Knuth D.E.: The Art of Computer Programming (Sorting and Searching). Reading, Mass. Addison-W esley 1973
Rinnooy Kan A. H. G.: A Machinę schedulingproblems. Stenfet Krose B.V., Leiden, Netherlands, 1976
Wajs W.: Optimal Control for Linear and Non-linear Dynamie Processes. IFAC Symposia Series, XI World Congress IFAC, Tallinn, vol. III, pp. 517-523, 1991
Cobham A.: The intrinsic computational difficult offunctions. Proc. 1964 Congress for Logic Methodology and Philosophy of Science North-Holland 24-30, 1964
Borodin A.: Computational complexity: theory and practice, in A. V. Aho (ed.)
Currents in the Theory of Computing. Prentice-Hall 35-89. 1973 Proc. 1964 Congress for Logic Methodology and Philosophy of Science North-Holland 24-30, 1964
Fisher R.A.: Statistical Methods for Research Workers., 01iver and Boyd Ltd., Edinburgh and London, 1948
Fisher R.A., Yates F.: Statistical Tables for Biological, Agricultural and Medical Research. Edinburg and London, 01iver and Boyd Ltd. 1953
Volk W.: AppliedStatisticsfor Engineers. New York, McGraw-Hill Inc. 1969
