Optimistic and Pessimistic Result of Planning and Scheduling Dynamie Processes


  • Wiesław Wajs AGH University of Science and Technology




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].


Download data is not yet available.


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




How to Cite

Wajs, W. (2020). Optimistic and Pessimistic Result of Planning and Scheduling Dynamie Processes. Computer Science, 1(1). https://doi.org/10.7494/csci.1999.1.1.3572




Most read articles by the same author(s)