Abstract
The paper contains an introduction to recent developments in the theory of non-preemptive stochastic scheduling problems. The topics covered are: arbitrary joint distributions of activity durations, arbitrary regular measures of performance and arbitrary precedence and resource constraints. The possible instability of the problem is demonstrated and hints are given on stable classes of strategies available, including the combinatorial vs. analytical characterization of such classes. Given this background, the main emphasis of the paper is on the monotonicity behaviour of the model and on the existence of optimal strategies. Existing results are presented and generalized, in particular w.r.t. the cases of lower semicontinuous performance measures or joint duration distributions having a Lebesgue density.
Similar content being viewed by others
References
Bauer, H.: Wahrscheinlichkeitstheorie. De Gruyter, Berlin 1968.
Bertsekas, D.P., andS.E. Shreve: Stochastic Optimal Control: The Discrete Time Case. Academic Press, New York 1978.
Billingsley, P.: Convergence of Probability Measures. Wiley, New York 1968.
Conway, R.W., W.L. Maxwell, andL.W. Miller: Theory of Scheduling. Addison-Wesley, Reading, MA. 1967.
Dempster, M.A.H.: A stochastic approach to hierarchical planning and scheduling. In: Dempster, M.A.H. et al. (eds.). Deterministic and Stochastic Scheduling. D. Reidel Publishing Company, Dord-Dortrecht 1982, 271–296.
Dempster, M.A.H., J.K. Lenstra, andA.H.G. Rinnooy Kan (eds.): Deterministic and Stochastic Scheduling. D. Reidel Publishing Company, Dordrecht, 1982.
Elmaghraby, S.E.: Activity Networks. Wiley, New York 1977.
Esary, J.D., F. Proschan, andD.W. Walkup: Association of random variables with applications. Annals of Mathematical Statistics, Vol.38, 1967, 1466–1474.
Fishburn, P.C.: Utility Theory for Decision Making. Wiley, New York 1970.
Graham, R.L., E.L. Lawler, J.K. Lenstra, andA.H.G. Rinnooy Kan: Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Math.5, 1979, 287–326.
Halmos, P.R.: Measure Theory. Van Nostrand Reinhold, New York 1950.
Hansel, G., andJ.P. Troallic: Measures marginales et theorème de Ford-Fulkerson. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete43, 1978, 245–251.
Heller, U.: On the shortest overall duration in stochastic project networks. Methods of Oper. Res.42, 1981, 85–104.
Hinderer, K.: Foundation of Non-stationary Dynamic Programming with Discrete Time Parameter. Springer Verlag, Berlin 1970.
—: Grundbegriffe der Wahrscheinlichkeitstheorie. Springer Verlag, Berlin 1972.
Igelmund, G., andF.J. Radermacher: Preselective strategies for the optimization of stochastic project networks under resource constraints. Networks13, 1983a, 1–29.
—: Algorithmic approaches to preselective strategies for stochastic scheduling problems. Networks13, 1983b, 29–48.
Jakobs, K.: Measure and Integral. Academic Press, New York 1978.
Jurecka, W.: Netzwerkplanung im Baubetrieb. Teil 2: Optimierungsverfahren. Bauverlag GmbH, Wiesbaden 1972.
Kadelka, D.: On randomized policies and mixtures of deterministic policies. Methods of Oper. Res.46, 1983, 67–75.
Kamae, T., U. Krengel, andO'Brien: Stochastic inequalities on partially ordered spaces. Ann. Probability5, 1977, 899–912.
Kaerkes, R., R.H. Möhring, W. Oberschelp, F.J. Radermacher, andM.M. Richter: Netzplanoptimierung: Deterministische und stochastische Scheduling-Probleme über geordneten Strukturen. Springer Verlag, to appear in 1985.
Klein Haneveld, W.K.: Distributions with known marginals and duality of mathematical programming with applications to PERT, Preprint 90 (OR-8203). Interfaculateit der Actuariele Wetenschappen en Econometrie, University of Groningen, 1982.
Meilijson, I., andA. Nadas: Convex majorization with an application to the length of critical paths. J. Appl. Prob.16, 1979, 671–677.
Moder, J.J., andC.R. Phillips: Project management with CPM and PERT. Reinhold, New York 1964.
Möhring, R.H.: Scheduling problems with a singular solution, Ann. of Discr. Math.16, 1982, 225–239.
—: Minimizing Costs of resource requirements subject to a fixed completion time in project networks. Oper. Res.32, 1984, 89–102.
Möhring, R.H., andF.J. Radermacher: Introduction to stochastic scheduling problems. In: Neumann, K., Pallaschke, D. (Eds.): Contributions to Operations Research. Proceedings of the Oberwolfach conference on Operations Research. Springer-Verlag, Heidelberg 1985.
Möhring, R.H., F.J. Radermacher, andG. Weiss: Stochastic scheduling problems II: set strategies. (Next volume).
-: Stochastic scheduling problems III: tractable cases. (In preparation).
Neumann, K.: Operations Research Verfahren. Band III, Carl Hanser Verlag, München 1975.
Pinedo, M., andL. Schrage: Stochastic shop scheduling: a survey. In: Dempster, M.A.H. et al. (eds.). Deterministic and Stochastic Scheduling, D. Reidel Publishing Company, Dordrecht, 1982, 181–196.
Radermacher, F.J.: Kapazitätsoptimierung in Netzplänen. Math. Syst. in Econ.40, Anton Hain, Meisenheim 1978.
—: Cost-dependent essential systems of ES-strategies for stochastic scheduling problems. Methods of Oper. Res.42, 1981, 17–31.
—: Optimale Strategien für stochastische Scheduling Probleme. Habilitationsschrift, RWTH Aachen 1981. In: Schriften zur Informatik und Angewandten Mathematik98, RWTH Aachen 1984.
Raiffa, H.: Einführung in die Entscheidungstheorie, Oldenbourg Verlag, München 1973.
Rinnooy Kan, A.H.G.: Machine Scheduling Problems: Classification, Complexity and Computation. Nijhoff, The Hague 1976.
Rival, I.: Assembly lines have no timing anomalies. Preprint, 1984.
Ross, S.M.: Applied Probability Models with Optimization Applications. Holden-Day, San Francisco 1970.
—: Introduction to Probability Models (3d. ed.). Academic Press, New York 1985.
Royden, H.L.: Real Analysis. The Macmillan Company, London 1968.
Schneeweiss, H.: Entscheidungskriterien bei Risiko. Springer Verlag, Berlin 1967.
Seeling, R.: Reihenfolgenprobleme in Netzplänen, Bauwirtschaft, 1972, 1897–1904.
Shogan, A.W.: Bounding distributions for stochastic PERT networks. Networks 7, 1977, 359–381.
Spelde, H.G.: Stochastische Netzpläne und ihre Anwendung im Baubetrieb, Dissertation, RWTH Aachen 1976.
—: Bounds for the distribution function of network variables, Methods of Oper. Res.27, 1977, 113–123.
Stoyan, D.: Comparison methods for queues and other stochastic models. John Wiley, Chichester 1983.
Strassen, V.: The existence of probability measures with given marginals. Ann. Math. Statistics36, 1965, 423–439.
Strauch, R.: Negative dynamic programming. Ann. Math. Statist.37, 1966, 871–890.
Sullivan, R.S., andJ.C. Hayya: A comparison of the method of bounding distributions (MBD) and Monte Carlo simulation for analyzing stochastic acyclic networks. Oper. Res.28, 1980, 614–617.
Wald, A.: Statistical Decisions Functions. Chelsea, New York 1950.
Weber, R.R.: Optimal Organization of Multserver Systems, Ph. D. thesis, Unviersity of Cambridge 1979.
Weber, R.R., P. Varaiya, andJ. Walrand: Scheduling jobs with stochastically ordered processing times on parallel machines to minimize expected flowtime. Memorandum No. UCB/ERL M84/57, Univ. of California 1984.
Weiss, G.: Multiserver stochastic scheduling. In: Dempster, M.A.H. et al. (eds.). Deterministic and Stochastic Scheduling. D. Reidel Publishing Company, Dordrecht 1982a, 157–179.
-: Stochastic bounds on distributions of optimal value functions with applications to PERT networks, flows and reliability. Techn. Report, Lehrstuhl für Informatik IV, Techn. Univ. of Aachen 1982b.
Weiss, G., andM. Pinedo: Scheduling tasks with exponential service times on non-identical processors to minimize various cost functions. J. Appl. Probability17, 1980, 187–202.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Möhring, R.H., Radermacher, F.J. & Weiss, G. Stochastic scheduling problems I — General strategies. Zeitschrift für Operations Research 28, 193–260 (1984). https://doi.org/10.1007/BF01919323
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01919323