×

The dominance digraph as a solution to the two-machine flow-shop problem with interval processing times. (English) Zbl 1233.90166

This article studies the two-machine flow-shop problem where the processing time for each job is not known in advance but it is assumed to lie in a known interval. The objective of the optimization is to minimize the total schedule length of the machines. After a section where the necessary background definitions, notation and literature review are presented, the authors investigate the properties of a partial job order and the dominance digraph. This helps for the construction of a minimal dominant set of schedules for the scheduling problem. Several theorems are proved in this section and the process is further explained via an example. The paper concludes with suggestions for future research and a list of relevant references.

MSC:

90B35 Deterministic scheduling theory in operations research
90C15 Stochastic programming
90C31 Sensitivity, stability, parametric optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1155/S016117120321019X · Zbl 1041.90020 · doi:10.1155/S016117120321019X
[2] DOI: 10.1111/1475-3995.00393 · Zbl 1027.90026 · doi:10.1111/1475-3995.00393
[3] DOI: 10.1016/j.ejor.2003.08.027 · Zbl 1115.90025 · doi:10.1016/j.ejor.2003.08.027
[4] DOI: 10.1016/j.ejor.2004.10.027 · Zbl 1079.90050 · doi:10.1016/j.ejor.2004.10.027
[5] DOI: 10.1002/nav.3800010110 · Zbl 1349.90359 · doi:10.1002/nav.3800010110
[6] Kouvelis P, IIE Trans. 32 pp 421– (2000)
[7] Kouvelis P, Robust Discrete Optimization and its Applications (1997) · doi:10.1007/978-1-4757-2620-6
[8] Lai T-C, J. Oper. Res. Soc. 50 pp 230– (1999) · Zbl 1054.90549 · doi:10.1057/palgrave.jors.2600690
[9] Lai T-C, Math. Comput. Model. 26 pp 67– (1997)
[10] DOI: 10.1016/S0377-2217(03)00424-7 · Zbl 1065.90038 · doi:10.1016/S0377-2217(03)00424-7
[11] Lin Y, Oper. Res. Trans. 3 pp 10– (1999)
[12] DOI: 10.1016/j.ejor.2005.09.017 · Zbl 1103.90043 · doi:10.1016/j.ejor.2005.09.017
[13] DOI: 10.1016/j.mcm.2008.02.004 · Zbl 1165.90464 · doi:10.1016/j.mcm.2008.02.004
[14] DOI: 10.1142/S0217595909002122 · Zbl 1177.90254 · doi:10.1142/S0217595909002122
[15] Pinedo M, Scheduling: Theory, Algorithms, and Systems (1995)
[16] Slowinski R, Scheduling Under Fuzziness (1999)
[17] DOI: 10.1057/palgrave.jors.2601682 · Zbl 1095.90049 · doi:10.1057/palgrave.jors.2601682
[18] DOI: 10.1016/j.mcm.2009.03.006 · Zbl 1185.90094 · doi:10.1016/j.mcm.2009.03.006
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.