×

zbMATH — the first resource for mathematics

Stochastic programming approaches to stochastic scheduling. (English) Zbl 0870.90067
Summary: Practical scheduling problems typically require decisions without full information about the outcomes of those decisions. Yields, resource availability, performance, demand, costs, and revenues all vary. Incorporating these quantities into stochastic scheduling models often produces difficulties in analysis that may be addressed in a variety of ways. In this paper, we present results based on stochastic programming approaches to the hierarchy of decisions in typical stochastic scheduling situations. Our unifying framework allows us to treat all aspects of a decision in a similar framework. We show how views from different levels enable approximations that can overcome nonconvexities and duality gaps that appear in deterministic formulations. In particular, we show that the stochastic program structure leads to a vanishing Lagrangian duality gap in stochastic integer programs as the number of scenarios increases.

MSC:
90B35 Deterministic scheduling theory in operations research
90C15 Stochastic programming
90C10 Integer programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] V.I. Arkin and I.V. Evstigneev (1979). Stochastic Models of Control and Economic Dynamics. Nauka, Moscow. (In Russian). English translation by E.A. Medova and M.A.H. Dempster. Academic, Orlando (1986). · Zbl 0477.90033
[2] D. Bai, T. Carpenter and J.M. Mulvey (1994). Stochastic programming to promote network survivability. Technical Report SOR-94-14, Statistics and Operations Research. Princeton University, August 1994.
[3] J.C. Bean and J.R. Birge (1986). Match-up real-time scheduling. In Real-Time Optimization in Automated Manufacturing Facilities, R.H.F. Jackson and A.W.T. Jones, eds., NBS Special Publication 724, National Bureau of Standards, 197-212.
[4] J.C. Bean, J.R. Birge, J. Mittenthal and C.E. Noon (1991). Match-up scheduling with multiple resources, release dates and disruptions Operations Research 39, 470-483. · Zbl 0742.90041 · doi:10.1287/opre.39.3.470
[5] D.P. Bertsekas (1982). Constrained Optimization and Lagrange Multiplier Methods. Academic Press, New York. · Zbl 0572.90067
[6] D. Bertsimas (1994). A mathematical programming approach to stochastic and dynamic optimization problems. Technical Report, Sloan School of Management and Operations Research Center. Massachusetts Institute of Technology, March 1994.
[7] D. Bertsimas and J. Niño-Mora (1993). Conservation laws, extended polymatroids and multi-armed bandit problems: A unified approach to indexable systems. Technical Repor, Sloan School of Management, Massachusetts Institute of Technology, March 1993. · Zbl 0921.90088
[8] J.R. Birge (1982). The value of the stochastic solution in stochastic linear programs with fixed recourse. Mathematical Programming 24, 314-325. · Zbl 0502.90065 · doi:10.1007/BF01585113
[9] J.R. Birge and M.A.H. Dempster (1992). Optimality for match-up strategies in stochastic scheduling. Technical Report, Department of Industrial and Operations Engineering, The University of Michigan. Submitted to: Mathematics of Operations Research. · Zbl 0819.90042
[10] J.R. Birge and M.A.H. Dempster (1995). Optimal match-up strategies in stochastic scheduling. Discrete Applied Mathematics 57, 105-120. · Zbl 0819.90042 · doi:10.1016/0166-218X(94)00098-X
[11] J.R. Birge, J.B.G. Frenk, J. Mittenthal and A.H.G. Rinnooy Kan (1990). Single machine scheduling subject to stochastic breakdowns. Naval Research Logistics 37, 661-677. · Zbl 0725.90038 · doi:10.1002/1520-6750(199010)37:5<661::AID-NAV3220370506>3.0.CO;2-3
[12] J.R. Birge and K.D. Glazebrook (1988). Assessing the effects of machine breakdowns in stochastic scheduling. Operations Research Letters 7, 267-271. · Zbl 0665.90046 · doi:10.1016/0167-6377(88)90056-9
[13] J.R. Birge and J-B. Wets (1986). Designing approximation schemes for stochastic optimization problems, in particular. for stochastic programs with recourse. Mathematical Programming Study 27. 54-102. · Zbl 0603.90104
[14] J.A. Buzacott and J.G. Shanthikumar (1980). Models for understanding flexible manufacturing systems. AIIE Transactions 12, 339-350.
[15] H. Chen and A. Mandelbaum (1991). Stochastic discrete flow networks: Diffusion approximations and bottlenecks. Annals of Probability 19, 1463-1510. · Zbl 0757.60094 · doi:10.1214/aop/1176990220
[16] G.B. Dantzig (1963). Linear Programming and Extensions. Princeton University Press, Princeton, NJ. · Zbl 0108.33103
[17] M.A.H. Dempster (1988). On stochastic programming: II. Dynamic problems under risk. Stochastics 25, 15-42. · Zbl 0653.90054
[18] M.A.H. Dempster (1994). Hierarchical approximation of telecommunications networks. BT Technology J. 12, 40-49.
[19] M.A.H. Dempster, M.L. Fisher, L. Jansen, B.J. Lageweg, J.K. Lenstra and A.H.G. Rinnooy Kan. (1983). Analysis of heuristics for stochastic programming: Results for hierarchical sceduling problems. Mathematics of Operations Research 8, 525-537. · Zbl 0532.90078 · doi:10.1287/moor.8.4.525
[20] M.A.H. Dempster, P.B. Key and E.A. Medova (1995). Integrated system modelling for ATM. Research Report 95-7, Department of Mathematics, University of Essex. Submitted to: Telecommunications Research.
[21] M.A.H. Dempster, J.K. Lenstra and A.H.G. Rinnooy Kan, eds. (1982). Deterministic and Stochastic Scheduling. Reidel, Dordrecht. · Zbl 0477.00028
[22] M.A.H. Dempster and E. Solel (1987). Stochastic scheduling via stochastic control. Proceedings 1st World Conference of the Bernoulli Society. K. Krickeberg and A. Shiryaev, eds. VNU Science Press, Utrecht, 783-788. · Zbl 0673.90093
[23] S.D. Flåm (1983). Asymptotically stable solutions to stochastic problems of Bolza. Chr. Michelsen Institute Report, Fantoft, Norway.
[24] S.D. Flåm (1985). Nonanticipativity in stochastic programming. Journal of Optimization Theory and Applications 46, 23-30. · Zbl 0542.90071 · doi:10.1007/BF00938756
[25] R. Garbe and K.D. Glazebrook (1995). Conservation laws, submodular returns and greedy heuristics for job selection and scheduling problems. Research Report, Department of Mathematics and Statistics, University of Newcastle. April 1995. · Zbl 0996.90048
[26] J.C. Gittins (1981). Multiserver scheduling of jobs with increasing completion times. Jounrals of Applied Probability 16, 321-324. · Zbl 0453.90050 · doi:10.2307/3213196
[27] K.D. Glazebrook (1981). On nonpreemptive strategies in stochastic scheduling. Naval Research Logistics Quarterly 28, 289-300. · Zbl 0462.90040 · doi:10.1002/nav.3800280211
[28] K.D. Glazebrook (1984). Scheduling stochastic jobs on a single machine subject to breakdowns. Naval Research Logistics Quarterly 31, 251-264. · Zbl 0538.90031 · doi:10.1002/nav.3800310207
[29] K.D. Glazebrook (1987). Evaluating the effects of machine breakdowns in stochastic scheduling problems. Naval Research Logistics 34, 319-335. · Zbl 0648.90042 · doi:10.1002/1520-6750(198706)34:3<319::AID-NAV3220340303>3.0.CO;2-5
[30] K.D. Glazebrook (1991). On non-preemptive policies for stochastic single machine scheduling with breakdowns. Probability in Engineering and Informational Sciences 5, 77-87. · Zbl 1134.90406 · doi:10.1017/S026996480000190X
[31] S.C. Graves (1981). A review of production scheduling. Operations Research 29, 646-675. · Zbl 0464.90034 · doi:10.1287/opre.29.4.646
[32] J.M. Harrison (1985). Brownian Motion and Stochastic Flow Systems. John Wiley, New York. · Zbl 0659.60112
[33] J-B. Hiriart-Urruty (1982). Extension of Lipschitz integrands and minimization of nonconvex integral functionals: Applications to the optimal recourse problem in discrete time. Probability and Mathematical Statistics 3, 19-36. · Zbl 0526.90068
[34] J.Y. Hui and E. Karasan (1995). A thermodynamic theory for broadband networks. Proceedings of the Third INFORMS Telecommunications Conference, Boca Raton, Florida, March 1995. F.P. Kelly (1991). Loss networks. Annals Applied Probability 1, 319-378.
[35] A.J. King and R. J-B Wets (1991). Epiconsistency of convex stochastic programs. Stochastics and Stochastics Reports 34, 83-92. · Zbl 0733.90049
[36] H.J. Kushner (1972). Necessary conditions for discrete parameter stochastic optimization problems. In: Proceedings Sixth Berkeley Symposium Math. Stats. and Probability, J. Neyman, ed. U. California, Berkeley, 667-685. · Zbl 0275.93062
[37] L. McKenzie (1976). Turnpike theory. Econometrica 44, 841-864. · Zbl 0356.90006 · doi:10.2307/1911532
[38] T.L. Magnanti, J.F. Shapiro, and M. H. Wagner (1976). Generalized linear programming solves the dual. Management Science 22, 1195-1203. · Zbl 0352.90059 · doi:10.1287/mnsc.22.11.1195
[39] E.A. Medova (1993). ATM admission control and routing. BT Laboratories Performance Engineering Report DS DZ/783-03/DP/00029, December 1993.
[40] J. Mittenthal (1986). Single Machine Scheduling Subject to Random Breakdowns. Ph.D. dissertation, The University of Michigan, Ann Arbor, Michigan.
[41] M.L. Pinedo (1983). Stochastic scheduling with release dates and due dates. Operations Research 31, 559-572. · Zbl 0523.90046 · doi:10.1287/opre.31.3.559
[42] M.L. Pinedo and S.M. Ross (1980). Scheduling jobs subject to nonhomogeneous Poisson shocks. Management Science 26, 1250-1257. · Zbl 0447.90043 · doi:10.1287/mnsc.26.12.1250
[43] R. Righter (1994). Scheduling. Chapter 13 in M. Shaked and J.G. Shanthikumar, Stochastic Orders and their Applications. Academic Press, San Diego, CA.
[44] A.H.G. Rinnooy Kan (1976). Machine Scheduling Problems: Classification, Complexity and Computations. Martinus Nijhoff, The Hague.
[45] R.T. Rockafellar (1976). Integral Functionals, Normal Integrands and Measurable Selections. Lecture Notes in Mathematics 543. Springer-Verlag, Berlin. · Zbl 0374.49001
[46] R.T. Rockafellar and R. J-B. Wets (1983). Deterministic and stochastic optimization problems of Bolza type in discrete time. Stochastics 10, 273-312. · Zbl 0534.49022
[47] S. Sen, R.D. Doverspike and S. Cosares (1992). Network planning with random demand. Technical Report, Systems and Industrial Engineering Department, University of Arizona, December 1992.
[48] S.P. Sethi, H.M. Soner, Q. Zhang and J. Jiang (1992). Turnpike sets and their analysis in stochastic production planning problems. Mathematics of Operations Research 17, 932-950. · Zbl 0770.90030 · doi:10.1287/moor.17.4.932
[49] S.P. Sethi and Q. Zhang (1995). Multilevel hierarchical decision making in stochastic marketing-production systems. SIAM J. Control and Optimization 33, 529-553. · Zbl 0826.93070 · doi:10.1137/S0363012993250542
[50] M. Shaked and J.G. Shanthikumar (1994). Stochastic Orders and their Applications. Academic Press. San Diego, CA. · Zbl 0806.62009
[51] J.G. Shanthikumar and D. Yao (1992). Multiclass queueing systems: Polymatroid structure and optimal scheduling and control, Operations Research 40, S293-S299. · Zbl 0764.90036 · doi:10.1287/opre.40.3.S293
[52] E. Solel (1986). A Dynamic Approach to Stochastic Scheduling via Stochastic Control. Ph.D. dissertation, Dalhousie University, Halifax, Nova Scotia.
[53] S. Takriti, J.R. Birge and E. Long (1994 a). A stochastic model for the unit commitment problem. IEEE Transactions on Power Systems, to appear.
[54] S. Takriti, J.R. Birge and E. Long (1994 b). Lagrangian solution techniques and bounds for loosely-coupled mixed-interger stochastic programs. Technical Report, Department of Industrial and Operations Engineering, University of Michigan, December 1994.
[55] M.H. van der Vlerk (1995). Stochastic Programming with Integer Recourse. Ph.D. Thesis, University of Groningen. · Zbl 0880.90109
[56] L.C. Young (1969). Lectures on the Calculus of Variations and Optimal Control Theory. W.B. Saunders, Philadelphia. · Zbl 0177.37801
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.