Parallel Machine Scheduling Under Uncertainty: Models and Exact Algorithms

References

• Akers SB (1978) Binary decision diagrams. IEEE Trans. Comput. 27(6):509–516.Crossref, Google Scholar
• Atamtürk A, Gómez A (2020) Submodularity in conic quadratic mixed 0–1 optimization. Oper. Res. 68(2):609–630.Abstract, Google Scholar
• Atamtürk A, Narayanan V (2008) Polymatroids and mean-risk minimization in discrete optimization. Oper. Res. Lett. 36(5):618–622.Crossref, Google Scholar
• Baker KR, Trietsch D (2009) Principles of Sequencing and Scheduling (John Wiley & Sons, Hoboken, NJ).Crossref, Google Scholar
• Ben-Tal A, El Ghaoui L, Nemirovski A (2009) Robust Optimization (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Bergman D, Cire AA, van Hoeve WJ, Hooker JN (2016) Discrete optimization with decision diagrams. INFORMS J. Comput. 28(1):47–66.Link, Google Scholar
• Bertsimas D, Brown DB, Caramanis C (2011) Theory and applications of robust optimization. SIAM Rev. 53(3):464–501.Crossref, Google Scholar
• Bertsimas D, Doan XV, Natarajan K, Teo CP (2010) Models for minimax stochastic linear optimization problems with risk aversion. Math. Oper. Res. 35(3):580–602.Link, Google Scholar
• Bertsimas D, Pachamanova D, Sim M (2004) Robust linear optimization under general norms. Oper. Res. Lett. 32(6):510–516.Crossref, Google Scholar
• Bertsimas D, Sim M (2004) The price of robustness. Oper. Res. 52(1):35–53.Link, Google Scholar
• Bertsimas D, Thiele A (2006) A robust optimization approach to inventory theory. Oper. Res. 54(1):150–168.Link, Google Scholar
• Birge JR, Frenk JBG, Mittenthal J, Rinnooy Kan AHG (1990) Single-machine scheduling subject to stochastic breakdowns. Naval Res. Logist. 37(5):661–677.Crossref, Google Scholar
• Birge JR, Louveaux F (1997) Introduction to Stochastic Programming (Springer, New York).Google Scholar
• Bougeret M, Pessoa AA, Poss M (2019) Robust scheduling with budgeted uncertainty. Discrete Appl. Math. 261(May):93–107.Crossref, Google Scholar
• Chang Z, Ding JY, Song S (2019) Distributionally robust scheduling on parallel machines under moment uncertainty. Eur. J. Oper. Res. 272(3):832–846.Crossref, Google Scholar
• Chang Z, Song S, Zhang Y, Ding JY, Zhang R, Chiong R (2017) Distributionally robust single machine scheduling with risk aversion. Eur. J. Oper. Res. 256(1):261–274.Crossref, Google Scholar
• Chen W, Sim M, Sun J, Teo CP (2010) From CVaR to uncertainty set: Implications in joint chance-constrained optimization. Oper. Res. 58(2):470–485.Link, Google Scholar
• Cheng J, Delage E, Lisser A (2014) Distributionally robust stochastic knapsack problem. SIAM J. Optim. 24(3):1485–1506.Crossref, Google Scholar
• Cohen MC, Keller PW, Mirrokni V, Zadimoghaddam M (2019) Overcommitment in cloud services: Bin packing with chance constraints. Management Sci. 65(7):3255–3271.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
• Dell’Amico M, Martello S (1995) Optimal scheduling of tasks on identical parallel processors. ORSA J. Comput. 7(2):191–200.Link, Google Scholar
• Dell’Amico M, Martello S (2005) A note on exact algorithms for the identical parallel machine scheduling problem. Eur. J. Oper. Res. 160(2):576–578.Crossref, Google Scholar
• Dell’Amico M, Iori M, Martello S, Monaci M (2008) Heuristic and exact algorithms for the identical parallel machine scheduling problem. INFORMS J. Comput. 20(3):333–344.Link, Google Scholar
• Deng Y, Shen S (2016) Decomposition algorithms for optimizing multi-server appointment scheduling with chance constraints. Math. Programming 157(1):245–276.Crossref, Google Scholar
• Denton BT, Miller AJ, Balasubramanian HJ, Huschka TR (2010) Optimal allocation of surgery blocks to operating rooms under uncertainty. Oper. Res. 58(4, Part 1):802–816.Google Scholar
• Dinh T, Fukasawa R, Luedtke J (2018) Exact algorithms for the chance-constrained vehicle routing problem. Math. Programming 172(1–2):105–138.Crossref, Google Scholar
• Edmonds J (1970) Submodular functions, matroids and certain polyhedra. Guy R, Sauer N, Hanani H, Schonheim J, eds. Combinatorial Structures and Their Applications (Gordon and Breach, New York), 69–87.Google Scholar
• El Ghaoui L, Oks M, Oustry F (2003) Worst-case value-at-risk and robust portfolio optimization: A conic programming approach. Oper. Res. 51(4):543–556.Link, Google Scholar
• Garey MR, Johnson DS (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman and Company, New York).Google Scholar
• Ghosal S, Wiesemann W (2020) The distributionally robust chance-constrained vehicle routing problem. Oper. Res. 68(3):716–732.Link, Google Scholar
• Graham RL (1966) Bounds for certain multiprocessing anomalies. Bell Systems Tech. J. 45(9):1563–1581.Crossref, Google Scholar
• Graham RL (1969) Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17(2):416–429.Crossref, Google Scholar
• Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Discrete Math. 5:287–326.Crossref, Google Scholar
• Hanasusanto GA, Roitch V, Kuhn D, Wiesemann W (2017) Ambiguous joint chance constraints under mean and dispersion information. Oper. Res. 65(3):751–767.Link, Google Scholar
• Herroelen W, Leus R (2005) Project scheduling under uncertainty: Survey and research potentials. Eur. J. Oper. Res. 165(2):289–306.Crossref, Google Scholar
• Jans R (2009) Solving lot-sizing problems on parallel identical machines using symmetry-breaking constraints. INFORMS J. Comput. 21(1):123–136.Link, Google Scholar
• Jiang R, Guan Y (2016) Data-driven chance constrained stochastic program. Math. Programming 158(1–2):291–327.Crossref, Google Scholar
• Kouvelis P, Yu G (1997) Robust Discrete Optimization and Its Applications (Kluwer, Dordrecht, Netherlands).Crossref, Google Scholar
• Kowalczyk D, Leus R (2017) An exact algorithm for parallel machine scheduling with conflicts. J. Scheduling 20(4):355–372.Crossref, Google Scholar
• Kowalczyk D, Leus R (2018) A branch-and-price algorithm for parallel machine scheduling using ZDDs and generic branching. INFORMS J. Comput. 30(4):768–782.Link, Google Scholar
• Letsios D, Mistry M, Misener R (2021) Exact lexicographic scheduling and approximate rescheduling. Eur. J. Oper. Res. 290(2):469–478.Crossref, Google Scholar
• Lozano L, Smith JC (2022) A binary decision diagram based algorithm for solving a class of binary two-stage stochastic programs. Math. Programming 191(1):381–404.Crossref, Google Scholar
• Minato S (1993) Zero-suppressed BDDs for set manipulation in combinatorial problems. Proc. 30th Internat. Design Automation Conf. (ACM, New York), 272–277.Google Scholar
• Mokotoff E (2004) An exact algorithm for the identical parallel machine scheduling problem. Eur. J. Oper. Res. 152(3):758–769.Crossref, Google Scholar
• Monaci M, Pferschy U (2013) On the robust knapsack problem. SIAM J. Optim. 23(4):1956–1982.Crossref, Google Scholar
• Monaci M, Pferschy U, Serafini P (2013) Exact solution of the robust knapsack problem. Comput. Oper. Res. 40(11):2625–2631.Crossref, Google Scholar
• Morrison DR, Sewell EC, Jacobson SH (2016) Solving the pricing problem in a branch-and-price algorithm for graph coloring using zero-suppressed binary decision diagrams. INFORMS J. Comput. 28(1):67–82.Link, Google Scholar
• Mula J, Poler R, Garcia-Sabater J, Lario FC (2006) Models for production planning under uncertainty: A review. Internat. J. Production Econom. 103(1):271–285.Crossref, Google Scholar
• Niu S, Song S, Ding JY, Zhang Y, Chiong R (2019) Distributionally robust single machine scheduling with the total tardiness criterion. Comput. Oper. Res. 101(January):13–28.Crossref, Google Scholar
• Pinedo M (1983) Stochastic scheduling with release dates and due dates. Oper. Res. 31(3):559–572.Link, Google Scholar
• Pinedo M (2015) Scheduling: Theory, Algorithms, and Systems, 5th ed. (Springer, Cham, Switzerland).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
• Ryan DM, Foster BA (1981) An integer programming approach to scheduling. Wren A, ed. Computer Scheduling of Public Transport: Urban Passenger Vehicle and Crew Scheduling (North-Holland, Amsterdam), 269–280.Google Scholar
• Sherali HD, Smith JC (2001) Improving discrete model representations via symmetry considerations. Management Sci. 47(10):1396–1407.Link, Google Scholar
• Smith JE, Winkler RL (2006) The optimizer’s curse: Skepticism and postdecision surprise in decision analysis. Management Sci. 52(3):311–322.Link, Google Scholar
• Tjandraatmadja C, van Hoeve WJ (2019) Target cuts from relaxed decision diagrams. INFORMS J. Comput. 31(2):285–301.Link, Google Scholar
• van den Akker M, Hoogeveen H (2008) Minimizing the number of late jobs in a stochastic setting using a chance constraint. J. Scheduling 11(1):59–69.Crossref, Google Scholar
• Wei L, Luo Z, Baldacci R, Lim A (2020) A new branch-and-price-and-cut algorithm for one-dimensional bin-packing problems. INFORMS J. Comput. 32(2):428–443.Link, Google Scholar
• Wiesemann W, Kuhn D, Sim M (2014) Distributionally robust convex optimization. Oper. Res. 62(6):1358–1376.Link, Google Scholar
• Xie W, Ahmed S (2018) On deterministic reformulations of distributionally robust joint chance constrained optimization problems. SIAM J. Optim. 28(2):1151–1182.Crossref, Google Scholar
• Xu X, Lin J, Cui W (2014) Hedge against total flow time uncertainty of the uniform parallel machine scheduling problem with interval data. Internat. J. Production Res. 52(19):5611–5625.Crossref, Google Scholar
• Xu X, Cui W, Lin J, Qian Y (2013) Robust makespan minimisation in identical parallel machine scheduling problem with interval data. Internat. J. Production Res. 51(12):3532–3548.Crossref, Google Scholar
• Zhang Z, Denton BT, Xie X (2020) Branch and price for chance-constrained bin packing. INFORMS J. Comput. 32(3):547–564.Link, Google Scholar
• Zhang Y, Jiang R, Shen S (2018a) Ambiguous chance-constrained binary programs under mean-covariance information. SIAM J. Optim. 28(4):2922–2944.Crossref, Google Scholar
• Zhang Y, Shen ZJM, Song S (2018b) Exact algorithms for distributionally β-robust machine scheduling with uncertain processing times. INFORMS J. Comput. 30(4):662–676.Link, Google Scholar
• Zymler S, Kuhn D, Rustem B (2013) Distributionally robust joint chance constraints with second-order moment information. Math. Programming 137(1–2):167–198.Crossref, Google Scholar