Two-machine flow-shop minimum-length scheduling with interval processing times. (English) Zbl 1180.90134

Summary: The flow-shop minimum-length scheduling problem with \(n\) jobs processed on two machines is addressed where processing times are uncertain: only lower and upper bounds of the random processing times are given before scheduling, but their probability distributions are unknown. For such a problem, there may not exist a dominant schedule that remains optimal for all possible realizations of the processing times and so we look for a minimal set of schedules that are dominant. We obtain necessary and sufficient conditions for the case when it is possible to fix the order of two jobs in a minimal set of dominant schedules. The necessary and sufficient conditions are proven for the case when one schedule dominates all the others. We characterize also the case where there does not exist non-trivial schedule domination. All the conditions proven may be tested in polynomial time of \(n\).


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


[1] Allahverdi A., International Journal of Mathematical Sciences 39 pp 2475–
[2] DOI: 10.1111/1475-3995.00393 · Zbl 1027.90026
[3] DOI: 10.1016/j.ejor.2003.08.027 · Zbl 1115.90025
[4] DOI: 10.1016/j.ejor.2004.10.027 · Zbl 1079.90050
[5] DOI: 10.1016/j.ejor.2005.02.001 · Zbl 1079.90001
[6] DOI: 10.1002/nav.3800010110 · Zbl 1349.90359
[7] Kouvelis P., IIE Transactions 32 pp 421–
[8] DOI: 10.1007/978-1-4757-2620-6
[9] DOI: 10.1057/palgrave.jors.2600690 · Zbl 1054.90549
[10] Lai T.-C., Mathematical and Computer Modelling 26 pp 67–
[11] DOI: 10.1016/S0377-2217(03)00424-7 · Zbl 1065.90038
[12] DOI: 10.1016/j.ejor.2005.09.017 · Zbl 1103.90043
[13] Pinedo M., Scheduling: Theory, Algorithms, and Systems (1995) · Zbl 1145.90393
[14] Slowinski R., Scheduling Under Fuzziness (1999)
[15] DOI: 10.1057/palgrave.jors.2601682 · Zbl 1095.90049
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.