×

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.

MSC:

90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Pinedo, M., Scheduling: Theory, Algorithms, and Systems (1995), Prentice-Hall: Prentice-Hall Englewood Cliffs, USA · Zbl 1145.90393
[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
[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
[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
[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
[7] Allahverdi, A.; Mittenthal, J., Two-machine ordered flowshop scheduling under random breakdowns, Mathematical and Computer Modelling, 20, 9-17 (1994) · Zbl 0810.90060
[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
[9] Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., 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
[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
[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
[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
[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
[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
[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
[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
[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, 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) · Zbl 1349.90359
[22] Taillard, E., Benchmarks for basic scheduling problems, European Journal of Operational Research, 64, 278-285 (1993) · Zbl 0769.90052
[23] Daniels, R. L.; Kouvelis, P., Robust scheduling to hedge against processing time uncertainty in single-stage production, Management Science, 41, 2, 363-376 (1995) · Zbl 0832.90050
[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, 1, 113-124 (1999) · Zbl 0979.90030
[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
[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
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.