Abstract
In this paper a survey is made of some of the recent results in stochastic shop scheduling. The models dealt with include:
-
(i)
Open shops.
-
(ii)
Flow shops with infinite intermediate storage (permutation flow shops).
-
(iii)
Flow shops with zero intermediate storage and blocking.
-
(iv)
Job shops.
Two objective functions are considered: Minimization of the expected completion time of the last job, the so-called makespan, and minimization of the sum of the expected completion times of all jobs, the so-called flow time. The decision-maker is not allowed to preempt. The shop models with two machines and exponentially distributed processing times usually turn out to have a very nice structure. Shop models with more than two machines are considerably harder.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Avi-Itzhak, B., “A Sequence of Service Stations with Arbitrary Input and Regular Service Times”: 1965, Man. Sci. 11, pp. 565–573.
Bagga, P.C., “N-Job, 2 Machine Sequencing Problem with Stochastic Service Times”: 1970, Opsearch 7, pp. 184–199.
Garey, M.R., Johnson, D.S. and Sethi, R., “The Complexity of Flowshop and Jobshop Scheduling”: 1976, Math. Operations Res. 1, pp. 117–129.
Gonzalez, T., and Sahni, S., “Open Shop Scheduling to Minimize Finish Time”: 1976, J. Assoc. Comput. Mach. 23 pp. 665–679.
Graham, R.L., Lawler, E.L., Lenstra, J.K. and Rinnooy Kan, A.H.G., “Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey”: 1979, Ann. Discr. Math. 5, pp. 287–326.
Jackson, J.R., “An Extension of Johnson’s Results on Job Lot Scheduling”: 1956, Naval Res. Logist. Quart. 3, pp. 201–203.
Johnson, S.M., “Optimal Two and Three Stage Production Schedules with Setup Times Included”: 1954, Naval Res. Logist. Quart. 1, pp. 61–68.
McMahon, G.B. and Florian, M., “On Scheduling with Ready Times and Due Dates to Minimize Maximum Lateness”: 1975, Operations Res. 23, pp. 475–482.
Pinedo, M.L., “Minimizing the Expected Flow Time in a Stochastic Open Shop with and without Preemptions”: 1981, Technical Report, Georgia Institute of Technology.
Pinedo, M.L. “Minimizing the Makespan in a Stochastic Flow Shop”: 1981, to appear, Operations Research.
Pinedo, M.L., “On the Optimal Order of Stations in Tandem Queues”: 1981, to appear, Proceedings of the Applied Probability-Computer Science: The Interface, Conference at Boca Raton, Florida.
Pinedo, M.L. “A Note on the Two Machine Job Shop with Exponential Processing Times”: 1981, to appear, Naval Research Logistics Quarterly.
Pinedo, M.L. and Ross, S.M., “Minimizing the Expected Makespan in a Stochastic Open Shop”: 1981, submitted to Journal of Applied Probability.
Reddi, S.S. and Ramamoorthy, C.V., “On the Flowshop Sequencing Problem with No Wait in Process”: 1972, Operational Res. Quart. 23, pp. 323–330.
Weber, R.R., “The Interchangeability of Tandem · ∣M∣1 Queues in Series”: 1979, J. of Applied Prob. 16, pp. 690–695.
Wismer, D.A., “Solution of Flowshop-Scheduling Problem with No Intermediate Queues”: 1972, Operations Res. 20, pp. 689–697.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1982 D. Reidel Publishing Company
About this paper
Cite this paper
Pinedo, M., Schrage, L. (1982). Stochastic Shop Scheduling: A Survey. In: Dempster, M.A.H., Lenstra, J.K., Rinnooy Kan, A.H.G. (eds) Deterministic and Stochastic Scheduling. NATO Advanced Study Institutes Series, vol 84. Springer, Dordrecht. https://doi.org/10.1007/978-94-009-7801-0_9
Download citation
DOI: https://doi.org/10.1007/978-94-009-7801-0_9
Publisher Name: Springer, Dordrecht
Print ISBN: 978-94-009-7803-4
Online ISBN: 978-94-009-7801-0
eBook Packages: Springer Book Archive