Abstract
This paper deals with single machine scheduling problems with stochastic precedence relations (so calledGERT networks). Until now most investigations on such problems, dealt with algorithms running in polynomial time. On the other hand, for scheduling problems with deterministic precedence relations exist a lot of results about time complexity. Therefore, the object of this paper is to consider time complexity of scheduling problems with stochastic precedence constraints and to describe the boundary between theNP-hard problems and those which can be solved in polynomial time.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bruno JL (1976) Scheduling Algorithms for Minimizing the Mean Weighted Flow-Time Criterion. In: Coffman EG Jr (ed) Computer and Job-Shop Scheduling Theory. Wiley, New York
Bruno JL, Downey P, Frederickson GN (1981) Sequencing Tasks with Exponential Service Times to Minimize the Expected Flow Time or Makespan. JACM 28:100–113
Bücker M (1990) Ein-Maschinen-Scheduling-Probleme mit stochastischen Reihenfolgebeziehungen unter besonderer Berücksichtigung polynomialer Algorithmen. Ph D Thesis, Karlruhe
Bücker M, Neumann K, Rubach T (1991) Algorithms for Single-Machine Scheduling with Stochastic Or Precedence Relations to Minimize Weighted Expected Flow-Time or Maximum Expected Lateness (in preparation)
Elmaghraby SE (1979) Activity Networks: Project Planning and Control by Network Models. Wiley, New York
Garey MR, Johnson DS (1979) Computers and Intractability. Freeman, San Francisco
Lawler EL (1973) Optimal Sequencing of a Single Machine Subject to Precedence Constraints. Management Sci 19:544–546
Lawler EL, Lenstra JK, Rinnooy Kan AHG (1982) Recent Developments in Deterministic Sequencing and Scheduling: A Survey. In: Dempster MAH, Lenstra JK, Rinnooy Kan AHG (eds) Deterministic and Stochastic Scheduling. Riedel, Dordrecht
Lenstra JK, Rinnooy Kan AHG (1978) Complexity of Scheduling under Precedence Constraints. Operat Res 26:22–35
Neumann K (1990) Stochastic Project Networks: Temporal Analysis, Scheduling and Cost Optimization. Lecture Notes in Economics and Math Systems, Vol 344. Springer, Berlin Heidelberg New York
Neumann K, Steinhardt U (1979)GERT-Networks and the Time-Oriented Evaluation of Projects. Lecture Notes in Economics and Math Systems, Vol 172. Springer, Berlin Heidelberg New York
Pinedo M (1982) On the Computational Complexity of Stochastic Scheduling Problems. In: Dempster MAH, Lenstra JK, Rinnooy Kan AHG (eds) (1982) Deterministic and Stochastic Scheduling. Riedel, Dordrecht
Rinnooy Kan AHG (1976) Machine Scheduling Problems, Classification, Complexity and Computations. Martinus Nijhoff, Den Haag
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Bücker, M. Time complexity of single machine scheduling with stochastic precedence constraints. ZOR - Methods and Models of Operations Research 36, 211–225 (1992). https://doi.org/10.1007/BF01415888
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF01415888