×

zbMATH — the first resource for mathematics

A MIP formulation for the minmax regret total completion time in scheduling with unrelated parallel machines. (English) Zbl 1293.90024
Summary: The paper proposes a mixed integer programming (MIP) formulation of the scheduling problem with total flow criterion on a set of parallel unrelated machines under an uncertainty context about the processing times. To model the problem we assume that lower and upper bounds are known for each processing time. In this context we consider an optimal minmax regret schedule as a suitable approximation to the optimal schedule under an arbitrary choice of the possible processing times.

MSC:
90B35 Deterministic scheduling theory in operations research
90C11 Mixed integer programming
Software:
NLPLIB; OPERA; TOMLAB
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aissi, H., Bazgan, C., Vanderpooten, D.: Complexity of the min-max and min-max regret assignment problems. Oper. Res. Lett. 33(6), 634–640 (2005) · Zbl 1141.90457 · doi:10.1016/j.orl.2004.12.002
[2] Aissi, H., Bazgan, C., Vanderpooten, D.: Min-max and min-max regret versions of combinatorial optimization problems: a survey. Eur. J. Oper. Res. 197(2), 427–438 (2009) · Zbl 1159.90472 · doi:10.1016/j.ejor.2008.09.012
[3] Arroyo, J.M., Alguacil, N., Carrión, M.: A risk-based approach for transmission network expansion planning under deliberate outages. IEEE Trans. Power Syst. 25(3), 1759–1766 (2010) · Zbl 1359.90013 · doi:10.1109/TPWRS.2010.2042310
[4] Aytug, H., Lawley, M.A., McKay, K., Mohan, S., Uzsoy, R.: Executing production schedules in the face of uncertainties: a review and some future directions. Eur. J. Oper. Res. 161(1), 86–110 (2005) · Zbl 1115.90025 · doi:10.1016/j.ejor.2003.08.027
[5] Burkard, R.E., Dell’Amico, M., Martello, S.: Assignment problems. SIAM (2009)
[6] Conde, E.: A 2-approximation for minmax regret problems via a mid-point scenario optimal solution. Oper. Res. Lett. 38, 326–327 (2010) · Zbl 1197.90337 · doi:10.1016/j.orl.2010.03.002
[7] Daniels, R.L., Kouvelis, P.: Robust scheduling to hedge against processing time uncertainty in single-stage production. Manage. Sci. 41(2), 363–376 (1995) · Zbl 0832.90050 · doi:10.1287/mnsc.41.2.363
[8] Herroelen, W., Leus, R.: Project scheduling under uncertainty: survey and research potentials. Eur. J. Oper. Res. 165(2), 289–306 (2005) · Zbl 1066.90050
[9] Kenneth, Holmström: The TOMLAB Optimization Environment in Matlab. Adv. Model. Optim. 1(1), 47–69 (1999) · Zbl 1115.90404
[10] Horn, W.A.: Minimizing average flow time with parallel machines. Operat. Res. 21(3), 846–847 (1973) · Zbl 0259.90030 · doi:10.1287/opre.21.3.846
[11] Kasperski, A.: Discrete optimization with interval data, Minmax regret and fuzzy approach. Studies in Fuzziness and Soft Computing. Springer, New York (2008) · Zbl 1154.90017
[12] Kasperski, A., Kurpisz, A., Zieliński, P.: Approximating a two-machine flow shop scheduling under discrete scenario uncertainty. Eur. J. Oper. Res. 217(1), 36–43 (2012) · Zbl 1244.90093 · doi:10.1016/j.ejor.2011.08.029
[13] Kasperski, A., Zieliński, P.: A 2-approximation algorithm for interval data minmax regret sequencing problems with the total flow time criterion. Oper. Res. Lett. 36(3), 343–344 (2008) · Zbl 1151.90417 · doi:10.1016/j.orl.2007.11.004
[14] Kasperski, A., Zieliński, P.: Possibilistic minmax regret sequencing problems with fuzzy parameters. IEEE Trans. Fuzzy Syst. 19(6), 1072–1082 (2011) · doi:10.1109/TFUZZ.2011.2159982
[15] Kouvelis, P., Daniels, R.L., Vairaktarakis, G.: Robust scheduling of a two-machine flow shop with uncertain processing times. IIE Trans. 32(5), 421–432 (2000). (Institute of Industrial Engineers)
[16] Kouvelis, P., Yu, G.: Robust discrete optimization and its applications. Kluwer Academic Publisher, USA (1997) · Zbl 0873.90071
[17] Lai, T.-C., Sotskov, YuN: Sequencing with uncertain numerical data for makespan minimisation. J. Oper. Res. Soc. 50(2–3), 230–243 (1999) · Zbl 1054.90549
[18] Lai, T.-C., Sotskov, YuN, Sotskova, N., Werner, F.: Mean flow time minimization with given bounds of processing times. Eur. J. Oper. Res. 159(3), 558–573 (2004) · Zbl 1065.90038 · doi:10.1016/S0377-2217(03)00424-7
[19] Lai, T.-C., Sotskov, YuN, Werner, F.: Optimal makespan scheduling with given bounds of processing times. Math. Comput. Model. 26(3), 67–86 (1997) · Zbl 0895.90118
[20] Lebedev, V., Averbakh, I.: Complexity of minimizing the total flow time with interval data and minmax regret criterion. Discrete Appl. Math. 154(15), 2167–2177 (2006) · Zbl 1111.90043 · doi:10.1016/j.dam.2005.04.015
[21] Lin, J., Ng, T.S.: Robust multi-market newsvendor models with interval demand data. Eur. J. Oper. Res. 212(2), 361–373 (2011) · Zbl 1237.90016 · doi:10.1016/j.ejor.2011.01.053
[22] Lu, C.-C., Lin, S.-W., Ying, K.-C.: Robust scheduling on a single machine to minimize total flow time. Comput. Oper. Res. 39(7), 1682–1691 (2012) · Zbl 1251.90167 · doi:10.1016/j.cor.2011.10.003
[23] Mahjoub, A., Pecero Sánchez, J.E.: Scheduling with uncertainties on new computing platforms. Comput. Optim. Appl. 48(2), 369–398 (2011) · Zbl 1219.90066 · doi:10.1007/s10589-009-9311-0
[24] Miranda, V., Proenca, L.M.: Why risk analysis outperforms probabilistic choice as the effective decision support paradigm for power system planning. IEEE Trans. Power Syst. 13(2), 643–648 (1998) · doi:10.1109/59.667394
[25] Montemanni, R.: A mixed integer programming formulation for the total flow time single machine robust scheduling problem with interval data. J. Math. Model. Algorithms 6(2), 287–296 (2007) · Zbl 1152.90455 · doi:10.1007/s10852-006-9044-3
[26] Owen, S.H., Daskin, M.S.: Strategic facility location: a review. Eur. J. Oper. Res. 111(3), 423–447 (1998) · Zbl 0938.90048 · doi:10.1016/S0377-2217(98)00186-6
[27] Pereira, J., Averbakh, I.: Exact and heuristic algorithms for the interval data robust assignment problem. Comput. Oper. Res. 38(8), 1153–1163 (2011) · Zbl 1208.90107 · doi:10.1016/j.cor.2010.11.009
[28] Pinedo, M.L.: Scheduling: theory, algorithms, and systems. Springer, New York (2010) · Zbl 1193.90093
[29] Siepak, M., Józefczyk, J.: Minmax regret algorithms for uncertain P||Cmax problem with interval processing times. Proceedings of ICSEng 2011: international conference on systems engineering, pp. 115–119 (2011)
[30] Snyder, L.V.: Facility location under uncertainty: a review. IIE Trans. 38(7), 547–564 (2006). (Institute of Industrial Engineers) · doi:10.1080/07408170500216480
[31] Sotskov, YuN, Egorova, N.G., Lai, T.-C.: Minimizing total weighted flow time of a set of jobs with interval processing times. Math. Comput. Model. 50, 556–573 (2009) · Zbl 1185.90094 · doi:10.1016/j.mcm.2009.03.006
[32] Yang, J., Yu, G.: On the robust single machine scheduling problem. J. Comb. Optim. 6(1), 17–33 (2002) · Zbl 1058.90029 · doi:10.1023/A:1013333232691
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.