Gutjahr, W. J.; Hellmayr, A.; Pflug, G. Ch. Optimal stochastic single-machine-tardiness scheduling by stochastic branch-and-bound. (English) Zbl 0998.90040 Eur. J. Oper. Res. 117, No. 2, 396-413 (1999). Summary: A stochastic branch-and-bound technique for the solution of stochastic single-machine-tardiness problems with job weights is presented. The technique relies on partitioning the solution space and estimating lower and upper bounds by sampling. For the lower bound estimation, two different types of sampling (“within” and “without” the minimization) are combined. Convergence to the optimal solution (with probability one) can be demonstrated. The approach is generalizable to other discrete stochastic optimization problems. In computational experiments with the single-machine-tardiness problem, the technique worked well for problem instances with a relatively small number of jobs; due to the enormous complexity of the problem, only approximate solutions can be expected for a larger number of jobs. Furthermore, a general precedence rule for the single-machine scheduling of jobs with uncertain processing times has been derived, essentially saying that “safe” jobs are to be scheduled before “unsafe” jobs. Cited in 8 Documents MSC: 90B36 Stochastic scheduling theory in operations research 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut Keywords:scheduling theory; stochastic scheduling; single-machine tardiness problem; branch-and-bound PDFBibTeX XMLCite \textit{W. J. Gutjahr} et al., Eur. J. Oper. Res. 117, No. 2, 396--413 (1999; Zbl 0998.90040) Full Text: DOI References: [1] S. French, Sequencing and Scheduling, Horwood, Chichester 1982; S. French, Sequencing and Scheduling, Horwood, Chichester 1982 [2] E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys, Sequencing and scheduling: Algorithms and complexity, in: S.C. Graves, A.H.G. Rinnooy Kan, P.H. Zipkin (Eds.), Logistis of Production and Inventory, Handbooks in Operations Research and Management, vol. 4, North-Holland, Amsterdam, 1993; E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys, Sequencing and scheduling: Algorithms and complexity, in: S.C. Graves, A.H.G. Rinnooy Kan, P.H. Zipkin (Eds.), Logistis of Production and Inventory, Handbooks in Operations Research and Management, vol. 4, North-Holland, Amsterdam, 1993 [3] M. Pinedo, Scheduling: Theory, Algorithms, and Systems, Prentice-Hall, Englewood Cliffs, NJ, 1995; M. Pinedo, Scheduling: Theory, Algorithms, and Systems, Prentice-Hall, Englewood Cliffs, NJ, 1995 · Zbl 1145.90393 [4] Du, J.; Leung, J. Y.T., Minimizing total tardiness on one machine is NP-hard, Mathematical Operations Research, 15, 483-495 (1990) · Zbl 0714.90052 [5] Gutjahr, W. J.; Pflug, G. Ch., Simulated annealing for noisy cost functions, Journal of Global Optimization, 8, 1-13 (1996) · Zbl 0857.90095 [6] I. Norkin, Y.M. Ermoliev, A. Ruszczynski, On optimal allocations of indivisibles under uncertainty, Technical Report WP-94-021, International Institute for Applied Systems Analysis, Laxenburg, Austria, 1994; I. Norkin, Y.M. Ermoliev, A. Ruszczynski, On optimal allocations of indivisibles under uncertainty, Technical Report WP-94-021, International Institute for Applied Systems Analysis, Laxenburg, Austria, 1994 · Zbl 0987.90064 [7] Birge, J. R.; Dempster, M. A.H., Stochastic programming approaches to stochastic scheduling, Journal of Global Optimization, 9, 417-451 (1996) · Zbl 0870.90067 [8] Panwalkar, S. S.; Smith, M. L.; Koulamas, C. P., A heuristic for the single machine tardiness problem, European Journal of Operational Research, 70, 304-310 (1993) · Zbl 0782.90057 [9] R.Y. Rubinstein, A. Shapiro, Discrete Event Systems: Sensitivity Analysis and Stochastic Optimization by the Score Function Method, Wiley, New York, 1993; R.Y. Rubinstein, A. Shapiro, Discrete Event Systems: Sensitivity Analysis and Stochastic Optimization by the Score Function Method, Wiley, New York, 1993 · Zbl 0805.93002 [10] M.G. Kendall, A. Stuart, Advanced Theory of Statistics, Griffin and Company, London, 1958; M.G. Kendall, A. Stuart, Advanced Theory of Statistics, Griffin and Company, London, 1958 · Zbl 0416.62001 [11] A. Marshall, I. Olkin, Inequalities: Theory of Majorization and its Applications, Academic Press, New York, 1979; A. Marshall, I. Olkin, Inequalities: Theory of Majorization and its Applications, Academic Press, New York, 1979 · Zbl 0437.26007 [12] Schrage, L. E.; Baker, K. R., Dynamic programming solutions of sequencing problems with precedence constraints, Operations Research, 26, 444-449 (1978) · Zbl 0383.90054 [13] W.J. Gutjahr, C. Strauss, E. Wagner, A stochastic branch-and-bound approach to activity crashing in project management, Technical Report, University of Vienna; W.J. Gutjahr, C. Strauss, E. Wagner, A stochastic branch-and-bound approach to activity crashing in project management, Technical Report, University of Vienna · Zbl 1034.90005 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.