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)
Schedule execution for two-machine flow-shop with interval processing times. (English) Zbl 1165.90464
Summary: This paper addresses the issue of how to best execute the schedule in a two-phase scheduling decision framework by considering a two-machine flow-shop scheduling problem in which each uncertain processing time of a job on a machine may take any value between a lower and upper bound. The scheduling objective is to minimize the makespan. There are two phases in the scheduling process: the off-line phase (the schedule planning phase) and the on-line phase (the schedule execution phase). The information of the lower and upper bound for each uncertain processing time is available at the beginning of the off-line phase while the local information on the realization (the actual value) of each uncertain processing time is available once the corresponding operation (of a job on a machine) is completed. In the off-line phase, a scheduler prepares a minimal set of dominant schedules, which is derived based on a set of sufficient conditions for schedule domination that we develop in this paper. This set of dominant schedules enables a scheduler to quickly make an on-line scheduling decision whenever additional local information on realization of an uncertain processing time is available. This set of dominant schedules can also optimally cover all feasible realizations of the uncertain processing times in the sense that for any feasible realizations of the uncertain processing times there exists at least one schedule in this dominant set which is optimal. Our approach enables a scheduler to best execute a schedule and may end up with executing the schedule optimally in many instances according to our extensive computational experiments which are based on randomly generated data up to 1000 jobs. The algorithm for testing the set of sufficient conditions of schedule domination is not only theoretically appealing (i.e., polynomial in the number of jobs) but also empirically fast, as our extensive computational experiments indicate.
90B35Scheduling theory, deterministic
[1]Pinedo, M.: Scheduling: theory, algorithms, and systems, (1995)
[2]Elmaghraby, S.; Thoney, K. A.: Two-machine flowshop problem with arbitrary processing time distributions, IIE transactions 31, 467-477 (2000)
[3]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 · doi:10.1016/S0377-2217(97)00424-4
[4]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 · doi:10.1287/opre.34.1.130
[5]Portougal, V.; Trietsch, D.: Johnson’s problem with stochastic processing times and optimal service level, European journal of operational research 169, 751-760 (2006) · Zbl 1079.90071 · doi:10.1016/j.ejor.2004.09.056
[6]Allahverdi, A.: Stochastically minimizing total flowtime in flowshops with no waiting space, European journal of operational research 113, 101-112 (1999) · Zbl 0933.90024 · doi:10.1016/S0377-2217(97)00438-4
[7]Allahverdi, A.; Mittenthal, J.: Two-machine ordered flowshop scheduling under random breakdowns, Mathematical and computer modelling 20, 9-17 (1994) · Zbl 0810.90060 · doi:10.1016/0895-7177(94)90202-X
[8]Lai, T. -C.; Sotskov, Yu.N.; Sotskova, N.; Werner, F.: Optimal makespan scheduling with given bounds of processing times, Mathematical and computer modelling 26, 67-86 (1997) · Zbl 0895.90118 · doi:10.1016/S0895-7177(97)00132-5
[9]Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Kan, A. H. G. Rinnooy: Optimization and approximation in deterministic sequencing and scheduling. A survey, Annals of discrete mathematics 5, 287-326 (1979) · Zbl 0411.90044
[10]Jansen, K.; Mastrolilli, V.; Solis-Oba, R.: Approximation schemes for job shop scheduling problems with controllable processing times, European journal of operational research 167, 297-319 (2005) · Zbl 1075.90029 · doi:10.1016/j.ejor.2004.03.025
[11]Janiak, A.: General flow-shop scheduling with resource constraints, International journal of production research 26, 125-138 (1988)
[12]Ng, C. T.; Cheng, T. C. E.; Kovalyov, M. Y.: Single machine batch scheduling with jointly compressible setup and processing times, European journal of operational research 153, 211-219 (2004) · Zbl 1137.90512 · doi:10.1016/S0377-2217(02)00732-4
[13]Cheng, T. C. E.; Kovalyov, M. Y.; Shakhlevich, N. V.: Scheduling with controllable release dates and processing times: makespan minimization, European journal of operational research 175, 751-768 (2006) · Zbl 1142.90395 · doi:10.1016/j.ejor.2005.06.021
[14]Lai, T. -C.; Sotskov, Yu.N.: Sequencing with uncertain numerical data for makespan minimization, Journal of the operational research society 50, 230-243 (1999) · Zbl 1054.90549
[15]N.M. Leshchenko, Yu.N. Sotskov, Two-machine minimum-length shop-scheduling problems with uncertain processing times, in: Proceedings of XI-th International Conference ”Knowledge-Dialogue-Solution”, vol. 2, Varna, Bulgaria, June 20–0, 2005 pp. 375–381
[16]Lai, T. -C.; Sotskov, Yu.N.; Sotskova, N.; Werner, F.: Mean flow time minimization with given bounds of processing times, European journal of operational research 159, 558-573 (2004) · Zbl 1065.90038 · doi:10.1016/S0377-2217(03)00424-7
[17]Allahverdi, A.; Sotskov, Yu.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 · doi:10.1111/1475-3995.00393
[18]Sotskov, Yu.N.; Allahverdi, A.; Lai, T. -C.: Flowshop scheduling problem to minimize total completion time with random and bounded processing times, Journal of the operational research society 55, 277-286 (2004) · Zbl 1095.90049 · doi:10.1057/palgrave.jors.2601682
[19]Allahverdi, A.; Aldowaisan, T.; Sotskov, Yu.N.: Two-machine flowshop scheduling problem to minimize makespan or total completion time with random and bounded setup times, International journal of mathematical sciences 39, 2475-2486 (2003) · Zbl 1041.90020 · doi:10.1155/S016117120321019X
[20]Leshchenko, N. M.; Sotskov, Yu.N.: Realization of an optimal schedule for the two-machine flow-shop with interval job processing times, International journal ”information theories and applications” 14, No. 2, 182-189 (2007)
[21]Johnson, S. M.: Optimal two- and three-stage production schedules with setup times included, Naval research logistics quarterly 1, 61-68 (1954)
[22]Taillard, E.: Benchmarks for basic scheduling problems, European journal of operational research 64, 278-285 (1993) · Zbl 0769.90052 · doi:10.1016/0377-2217(93)90182-M
[23]Daniels, R. L.; Kouvelis, P.: Robust scheduling to hedge against processing time uncertainty in single-stage production, Management science 41, No. 2, 363-376 (1995) · Zbl 0832.90050 · doi:10.1287/mnsc.41.2.363
[24]Wu, S. D.; Byeon, E. -S.; Storer, R.: A graph-theoretical decomposition of the job-shop scheduling problem to achieve scheduling robustness, Operations research 47, No. 1, 113-124 (1999) · Zbl 0979.90030 · doi:10.1287/opre.47.1.113
[25]Kouvelis, P.; Daniels, R. L.; Vairaktarakis, G.: Robust scheduling of a two-machine flow shop with uncertain processing times, IIE transactions 32, 421-432 (2000)
[26]Averbakh, I.: Minmax regret solutions for minmax optimization problems with uncertainty, Operations research letters 27, 57-65 (2000) · Zbl 0988.90026 · doi:10.1016/S0167-6377(00)00025-0
[27]Lebedev, V.; Averbakh, I.: Complexity of minimizing the total flow time with interval data and minmax regret criterion, Discrete applied mathematics 154, 2167-2177 (2006) · Zbl 1111.90043 · doi:10.1016/j.dam.2005.04.015