zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Johnson’s problem with stochastic processing times and optimal service level. (English) Zbl 1079.90071
Summary: Theoretical results about Johnson’s problem with stochastic processing times are few. In general, just finding the expected makespan of a given sequence is already difficult, even for discrete processing time distributions. Furthermore, to obtain optimal service level we need to compute the entire distribution of the makespan. Therefore the use of heuristics and simulation is justified. We show that pursuing the minimal expected makespan by two heuristics is empirically effective for obtaining excellent overall distributions. The first is to use Johnson’s rule on the means. The second is based on pair-switching and converges to some known stochastically optimal solutions when they apply. We show that the first heuristic is asymptotically optimal under mild conditions. We also investigate the effect of sequencing on the makespan variance.

90B36Scheduling theory, stochastic
90C59Approximation methods and heuristics
60K10Applications of renewal theory
Full Text: DOI
[1] Allahverdi, A.; Aldowaisan, T.; Sotskov, Y. N.: Two-machine flowshop scheduling problem to minimize makespan or total completion time with random and bounded setup times. International journal of mathematics and mathematical sciences 39, 2475-2486 (2003) · Zbl 1041.90020
[2] Allahverdi, A.; Mittenthal, J.: Two-machine ordered flowshop scheduling under random breakdowns. Mathematical and computer modelling 20, 9-17 (1994) · Zbl 0810.90060
[3] Allahverdi, A.; Mittenthal, J.: Scheduling on a two-machine flowshop subject to random breakdowns with a makespan objective function. European journal of operational research 81, 376-387 (1995) · Zbl 0927.90044
[4] Allahverdi, A.; Sotskov, Y. N.: Two-machine flowshop minimum length scheduling problem with random and bounded processing times. International transactions in operational research 10, 65-76 (2003) · Zbl 1027.90026
[5] Clark, C. E.: The greatest of a finite set of random variables. Operations research 9, 145-162 (1961) · Zbl 0201.51102
[6] Dodin, B.: Determining the optimal sequences and the distributional properties of their completion times in stochastic flow shops. Computers in operations research 23, 829-843 (1996) · Zbl 0868.90064
[7] Elmaghraby, S. E.; Thoney, K. A.: The two-machine stochastic flowshop problem with arbitrary processing time distributions. IIE transactions 31, 467-477 (1999)
[8] Johnson, S. M.: Optimal two- and three-stage production schedules with setup times included. Naval research logistics quarterly 1, 61-68 (1954)
[9] Kamburowski, J.: Stochastically minimizing the makespan in two-machine flow shops without blocking. European journal of operational research 112, 304-309 (1999) · Zbl 0938.90029
[10] Ku, P. -S.; Niu, S. -C.: On Johnson’s two-machine flow shop with random processing times. Operations research 34, 130-136 (1986) · Zbl 0595.90044
[11] Kushner, H. J.: Approximation and weak convergence methods for random processes, with applications to random systems theory. (1984) · Zbl 0551.60056
[12] Pinedo, M.: Minimizing the expected makespan in stochastic flow shops. Operations research 30, 148-162 (1982) · Zbl 0481.90047
[13] Pinedo, M.: Scheduling: theory, algorithms, and systems. (2001)
[14] Portougal, V.; Trietsch, D.: Makespan-related criteria for comparing schedules in stochastic environments. Journal of the operational research society 49, 1188-1195 (1998) · Zbl 1140.90417
[15] Portougal, V.; Trietsch, D.: Stochastic scheduling with optimal customer service. Journal of the operational research society 52, 226-233 (2001) · Zbl 1131.90368
[16] Soroush, H. M.: Sequencing and due-date determination in the stochastic single machine problem with earliness and tardiness costs. European journal of operational research 113, 450-468 (1999) · Zbl 0938.90033
[17] Vollman, T. E.; Berry, W. L.; Whybark, D. C.: Manufacturing planning and control systems. (1997)