Exact Algorithms for Distributionally β-Robust Machine Scheduling with Uncertain Processing Times

References

• Alimoradi S, Hematian M, Moslehi G (2016) Robust scheduling of parallel machines considering total flow time. Comput. Indust. Engrg. 93(March):152–161.Crossref, Google Scholar
• Ben-Tal A, El Ghaoui L, Nemirovski A (2009) Robust Optimization (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Bertsimas D, Popescu I (2005) Optimal inequalities in probability theory: A convex optimization approach. SIAM J. Optim. 15(3):780–804.Crossref, Google Scholar
• Bertsimas D, Sim M (2003) Robust discrete optimization and network flows. Math. Programming 98(1):49–71.Crossref, Google Scholar
• Bijsterbosch J, Volgenant A (2010) Solving the rectangular assignment problem and applications. Ann. Oper. Res. 181(1):443–462.Crossref, Google Scholar
• Burkard RE (2013) Quadratic Assignment Problems (Springer, Berlin).Crossref, Google Scholar
• Burkard RE, Dell’Amico M, Martello S (2009) Assignment Problems (SIAM, Philadelphia).Crossref, Google Scholar
• Daniels RL, Carrillo JE (1997) β-robust scheduling for single-machine systems with uncertain processing times. IIE Trans. 29(11):977–985.Crossref, Google Scholar
• Daniels RL, Kouvelis P (1995) Robust scheduling to hedge against processing time uncertainty in single-stage production. Management Sci. 41(2):363–376.Link, Google Scholar
• Delage E, Ye Y (2010) Distributionally robust optimization under moment uncertainty with application to data-driven problems. Oper. Res. 58(3):595–612.Link, Google Scholar
• Godwin H (1955) On generalizations of Tchebychef′s inequality. J. Amer. Statist. Assoc. 50(271):923–945.Crossref, Google Scholar
• Goren S, Sabuncuoglu I (2008) Robustness and stability measures for scheduling: Single-machine environment. IIE Trans. 40(1):66–83.Crossref, Google Scholar
• Grimmett G, Stirzaker D (2001) Probability and Random Processes (Oxford University Press, Oxford, UK).Crossref, Google Scholar
• Hafizoglu AB, Gel ES, Keskinocak P (2013) Expected tardiness computations in multiclass priority M/M/C queues. INFORMS J. Comput. 25(2):364–376.Link, Google Scholar
• Horst R, Pardalos PM, Van Thoai N (2000) Introduction to Global Optimization (Springer, Berlin).Crossref, Google Scholar
• Jonker R, Volgenant A (1987) A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing 38(4):325–340.Crossref, Google Scholar
• Kasperski A, Zieliński P (2008) A 2-approximation algorithm for interval data minmax regret sequencing problems with the total flow time criterion. Oper. Res. Lett. 36(3):343–344.Crossref, Google Scholar
• Kasperski A, Kurpisz A, Zieliński P (2012) Approximating a two-machine flow shop scheduling under discrete scenario uncertainty. Eur. J. Oper. Res. 217(1):36–43.Crossref, Google Scholar
• Kennington J, Wang Z (1992) A shortest augmenting path algorithm for the semi-assignment problem. Oper. Res. 40(1):178–187.Link, Google Scholar
• Khatamia SM, Ranjbara M, Davari M (2015) Maximizing service level in a β-robust job shop scheduling model. J. Indust. Systems Engrg. 8(4):61–73.Google Scholar
• Kouvelis P, Yu G (1997) Robust Discrete Optimization and Its Applications (Kluwer Academic Publishers, Boston).Crossref, Google Scholar
• Kouvelis P, Daniels RL, Vairaktarakis G (2000) Robust scheduling of a two-machine flow shop with uncertain processing times. IIE Trans. 32(5):421–432.Crossref, Google Scholar
• Lu CC, Ying KC, Lin SW (2014) Robust single machine scheduling for minimizing total flow time in the presence of uncertain processing times. Comput. Indust. Engrg. 74(August):102–110.Crossref, Google Scholar
• Mangasarian OL (1994) Nonlinear Programming (SIAM, Philadelphia).Crossref, Google Scholar
• Nikolova E (2010) Approximation algorithms for reliable stochastic combinatorial optimization. Serna M, Shaltiel R, Jansen K, Rolim J, eds. Proc. 13th Internat. Conf. Approximation, 14 Internat. Conf. Randomization, Combin. Optim.: Algorithms Techniques, Barcelona, Spain, 338–351.Google Scholar
• Palacios JJ, González-Rodríguez I, Vela CR, Peinador JP (2014) β-robust solutions for the fuzzy open shop scheduling. Laurent A, Strauss O, Bouchon-Meunier B, Yager RR, eds. Internat. Conf. Information Processing Management Uncertainty Knowledge-Based Systems, Montpellier, France, 447–456.Google Scholar
• Pereira J (2016) The robust (minmax regret) single machine scheduling with interval processing times and total weighted completion time objective. Comput. Oper. Res. 66(February):141–152.Crossref, Google Scholar
• Pishevar A, Tavakkoi MR (2014) β-robust parallel machine scheduling with uncertain durations. Universal J. Indust. Bus. Management 2(3):69–74.Crossref, Google Scholar
• Popescu I (2007) Robust mean-covariance solutions for stochastic optimization. Oper. Res. 55(1):98–112.Link, Google Scholar
• Radzik T (2013) Fractional combinatorial optimization. Pardalos PM, Du DZ, Graham RL, eds. Handbook of Combinatorial Optimization (Springer, New York), 1311–1355.Crossref, Google Scholar
• Ranjbar M, Davari M, Leus R (2012) Two branch-and-bound algorithms for the robust parallel machine scheduling problem. Comput. Oper. Res. 39(7):1652–1660.Crossref, Google Scholar
• Sabuncuoglu I, Goren S (2009) Hedging production schedules against uncertainty in manufacturing environment with a review of robustness and stability research. Internat. J. Comput. Integrated Manufacturing 22(2):138–157.Crossref, Google Scholar
• Sahni S, Gonzalez T (1976) P-complete approximation problems. J. ACM 23(3):555–565.Crossref, Google Scholar
• Sarin SC, Sherali HD, Liao L (2014) Minimizing conditional-value-at-risk for stochastic scheduling problems. J. Scheduling 17(1):5–15.Crossref, Google Scholar
• Shen ZJM, Qi L (2007) Incorporating inventory and routing costs in strategic location models. Eur. J. Oper. Res. 179(2):372–389.Crossref, Google Scholar
• Shu J, Teo CP, Shen ZJM (2005) Stochastic transportation-inventory network design problem. Oper. Res. 53(1):48–60.Link, Google Scholar
• Sniedovich M (1986) C-programming and the minimization of pseudolinear and additive concave functions. Oper. Res. Lett. 5(4): 185–189.Crossref, Google Scholar
• Tadayon B, Smith JC (2015) Algorithms and complexity analysis for robust single-machine scheduling problems. J. Scheduling 18(6): 575–592.Crossref, Google Scholar
• Ullah S, Zakria G, Abid M (2010) A heuristic for robust scheduling of two machine flow shop. Tech. World Quart. J. 2(1):253–257.Google Scholar
• Volgenant A (1996) Linear and semi-assignment problems: A core oriented approach. Comput. Oper. Res. 23(10):917–932.Crossref, Google Scholar
• Wu CW, Brown KN, Beck JC (2009) Scheduling with uncertain durations: Modeling β-robust scheduling with constraints. Comput. Oper. Res. 36(8):2348–2356.Crossref, Google Scholar
• Wu SD, Byeon ES, Storer RH (1999) A graph-theoretic decomposition of the job shop scheduling problem to achieve scheduling robustness. Oper. Res. 47(1):113–124.Link, Google Scholar
• Yang J, Yu G (2002) On the robust single machine scheduling problem. J. Combin. Optim. 6(1):17–33.Crossref, Google Scholar
• Yu YL, Li Y, Schuurmans D, Szepesvári C (2009) A general projection property for distribution families. Bengio Y, Schuurmans D, Lafferty JD, Wiliams CKI, Culotta A, eds. Advances in Neural Information Processing Systems (Wiley, New York), 2232–2240.Google Scholar
• Zhang Y, Shen ZJM, Song S (2016a) Distributionally robust optimization of two-stage lot-sizing problems. Production Oper. Management 25(12):2116–2131.Crossref, Google Scholar
• Zhang Y, Shen ZJM, Song S (2016b) Parametric search for the bi-attribute concave shortest path problem. Transportation Res. Part B: Methodological 94(December):150–168.Crossref, Google Scholar
• Zhang Y, Shen ZJM, Song S (2017) Lagrangian relaxation for the reliable shortest path problem with correlated link travel times. Transportation Res. Part B: Methodological 104(October):501–521.Crossref, Google Scholar
• Zhang Y, Song S, Shen ZJM, Wu C (2018) Robust shortest path problem with distributional uncertainty. IEEE Trans. Intelligent Transportation Systems 19(4):1080–1090.Crossref, Google Scholar