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)
A heuristic for minimizing the expected makespan in two-machine flow shops with consistent coefficients of variation. (English) Zbl 1079.90070
Summary: The paper deals with the classical problem of minimizing the makespan in a two-machine flow shop. When the job processing times are deterministic, the optimal job sequence can be determined by applying Johnson’s rule. When they are independent and exponential random variables, Talwar’s rule yields a job sequence that minimizes the makespan stochastically. Assuming that the job processing times are independently and Weibull distributed random variables, we present a new job sequencing rule that includes both Johnson’s and Talwar’s rules as special cases. The proposed rule is applicable as a heuristic whenever the job processing times are characterized by their means and the same coefficient of variation. Simulation results show that it leads to very encouraging results when the expected makespan is minimized.

90B36Scheduling theory, stochastic
90C59Approximation methods and heuristics
Full Text: DOI
[1] Allahverdi, A.; Sotskov, Y.: Two-machine flow shops minimum-length scheduling problem with random and bounded processing times. International transactions in operational research 10, 65-76 (2003) · Zbl 1027.90026
[2] Bendell, A.; Solomon, D.; Carter, J. M.: Evaluating project completion times when activity times are Erlang distributed. Journal of operational research society 46, 867-882 (1995) · Zbl 0832.90054
[3] Cunnigham, A. A.; Dutta, S. K.: Scheduling jobs with exponentially distributed processing times on two machines of a flow shop. Naval research logistics quarterly 16, 69-81 (1973) · Zbl 0254.90021
[4] Dodin, B.: Determining the optimal sequences and the distributional properties of their completion times in stochastic flow shops. Computers & operations research 23, No. 9, 829-843 (1996) · Zbl 0868.90064
[5] Elmaghraby, S. E.; Thoney, K. A.: The two-machine stochastic flowshop problem with arbitrary processing time distributions. IIE transactions 31, No. 5, 467-477 (1999)
[6] Garey, M. R. D.; Johnson, D. S.; Sethi, R.: The complexity of flow shop and job shop scheduling. Mathematics of operations research 1, 117-129 (1976) · Zbl 0396.90041
[7] Halpern, S. W.: The effect of having unequal branch gains in practical predetection diversity systems for mobile radio. IEEE transactions on vehicular technology 26, 94-104 (1977)
[8] James, F.: RANLUX: a Fortran implementation of the high-quality pseudorandom number generator of luscher. Computer physics communications 97, No. 3, 357 (1996)
[9] Johnson, N. L.; Kotz, S.; Balakrishnan, N.: Continuous univariate distributions, vol. 1. (1994) · Zbl 0811.62001
[10] Johnson, S. M.: Optimal two- and three-stage production schedules with setup times included. Naval research logistics quarterly 1, 61-68 (1954)
[11] Kamburowski, J.: Stochastically minimizing the makespan in two-machine flow shops without blocking. European journal of operational research 112, No. 2, 304-309 (1999) · Zbl 0938.90029
[12] 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
[13] Pinedo, M.: Scheduling: theory, algorithms, and systems. (2002) · Zbl 1145.90394
[14] Portugal, V.; Trietsch, D.: Makespan-related criteria for computing schedules in stochastic environments. Journal of operational research society 52, 1188-1195 (1998) · Zbl 1140.90417
[15] Righter, R.: A generalized Johnson’s rule for stochastic assembly systems. Naval research logistics quarterly 44, 211-220 (1997) · Zbl 0891.90084
[16] Shaked, M.; Shanthikumar, J. G.: Stochastic orders and their applications. (1994) · Zbl 0806.62009
[17] Talwar, P. P.: A note on sequencing problems with uncertain job times. Journal of operations research society Japan 9, 93-97 (1967)