Exact reoptimisation under gradual look-ahead for operational control in production and logistics

References

• Albers, S. (1997). On the influence of lookahead in competitive paging algorithms. Algorithmica, 18(3), 283–305. https://doi.org/10.1007/PL00009158
   Web of Science ®Google Scholar
• Albers, S. (1998). A competitive analysis of the list update problem with lookahead. Theoretical Computer Science, 197(1–2), 95–109. https://doi.org/10.1016/S0304-3975(97)00026-1
   Web of Science ®Google Scholar
• Albers, S. (1999). Better bounds for online scheduling. SIAM Journal on Computing, 29(2), 459–473. https://doi.org/10.1137/S0097539797324874
   Web of Science ®Google Scholar
• Albers, S. (2003). Online algorithms: A survey. Mathematical Programming, 97(1), 3–26. https://doi.org/10.1007/s10107-003-0436-0
   Web of Science ®Google Scholar
• Allulli, L., Ausiello, G., Bonifaci, V., & Laura, L. (2008). On the power of lookahead in on-line server routing problems. Theoretical Computer Science, 408(2–3), 116–128. https://doi.org/10.1016/j.tcs.2008.08.003
   Web of Science ®Google Scholar
• Allulli, L., Ausiello, G., & Laura, L. (2005). On the power of lookahead in on-line vehicle routing problems. In Lecture notes in computer science 3595: Proceedings of the 11th annual international conference on computing and combinatorics (pp. 728–736). Springer.
   Google Scholar
• Ausiello, G., Allulli, L., Bonifaci, V., & Laura, L. (2006). On-line algorithms, real time, the virtue of laziness, and the power of clairvoyance. In Lecture notes in computer science 3959: Proceedings of the 3rd international conference on theory and applications of models of computation (pp. 1–20). Springer.
   Google Scholar
• Ben-Tal, A., Goryashko, A., Guslitzer, E., & Nemirovski, A. (2004). Adjustable robust solutions of uncertain linear programs. Mathematical Programming, 99(2), 351–376. https://doi.org/10.1007/s10107-003-0454-y
   Web of Science ®Google Scholar
• Ben-Tal, A., & Nemirovski, A. (1999). Robust solutions of uncertain linear programs. Operations Research Letters, 25(1), 1–13. https://doi.org/10.1016/S0167-6377(99)00016-4
   Web of Science ®Google Scholar
• Ben-Tal, A., Nemirovski, A. S., & El Ghaoui, L. (2009). Robust optimization, Princeton series in applied mathematics, Princeton University Press.
   Google Scholar
• Bent, R., & Van Hentenryck, P. (2004a). Regrets only! Online stochastic optimization under time constraints. In Proceedings of the national conference on artificial intelligence (pp. 501–506). AAAI Press.
   Google Scholar
• Bent, R., & Van Hentenryck, P. (2004b). The value of consensus in online stochastic scheduling. In Proceedings of the 14th international conference on automated planning and scheduling, ICAPS 2004 (pp. 219–226). AAAI Press.
   Google Scholar
• Bertsimas, D., & Dunning, I. (2016). Multistage robust mixed-integer optimization with adaptive partitions. Operations Research, 64(4), 980–998. https://doi.org/10.1287/opre.2016.1515
   Web of Science ®Google Scholar
• Birge, J. (1997). State-of-the-art-survey-stochastic programming: Computation and applications. INFORMS Journal on Computing, 9(2), 111–133. https://doi.org/10.1287/ijoc.9.2.111
   Google Scholar
• Borodin, A., & El-Yaniv, R. (2005). Online computation and competitive analysis (2nd ed.). Cambridge University Press.
   Google Scholar
• Boyar, J., Favrholdt, L., Kudahl, C., Larsen, K., & Mikkelsen, J. (2017). Online algorithms with advice: A survey. ACM Computing Surveys, 50(2), 1–34. https://doi.org/10.1145/3056461
   Web of Science ®Google Scholar
• Boyar, J., Irani, S., & Larsen, K. (2015). A comparison of performance measures for online algorithms. Algorithmica, 72(4), 969–994. https://doi.org/10.1007/s00453-014-9884-6
   Web of Science ®Google Scholar
• Breslauer, D. (1998). On competitive on-line paging with lookahead. Theoretical Computer Science, 209(1–2), 365–375. https://doi.org/10.1016/S0304-3975(98)00118-2
   Web of Science ®Google Scholar
• Bron, C., & Kerbosch, J. (1973). Algorithm 457: Finding all cliques of an undirected graph. Communications of the ACM, 16(9), 575–577. https://doi.org/10.1145/362342.362367
   Web of Science ®Google Scholar
• Chand, S., & Sethi, S. (2014). Multi-period lot-sizing with stationary demand: Extension to forecast horizons. International Series in Operations Research and Management Science, 197, 23–42. https://doi.org/10.1007/978-1-4614-7639-9
   Google Scholar
• Chen, B., & Vestjens, A. (1997). Scheduling on identical machines: How good is LPT in an on-line setting?. Operations Research Letters, 21(4), 165–169. https://doi.org/10.1016/S0167-6377(97)00040-0
   Web of Science ®Google Scholar
• Chen, X., Kovalev, S., Liu, Y., Sterna, M., Chalamon, I., & Błażewicz, J. (2020). Semi-online scheduling on two identical machines with a common due date to maximize total early work. Discrete Applied Mathematics, 290, 71–78. https://doi.org/10.1016/j.dam.2020.05.023
   PubMed Web of Science ®Google Scholar
• Cicerone, S., D'Angelo, G., Di Stefano, G., Frigioni, D., & Navarra, A. (2008). Delay management problem: Complexity results and robust algorithms. In B. Yang, D. Du, & C. Wang (Eds.), Combinatorial optimization and applications (pp. 458–468). Springer.
   Google Scholar
• Cicerone, S., Di Stefano, G., Schachtebeck, M., & Schöbel, A. (2012). Multi-stage recovery robustness for optimization problems: A new concept for planning under disturbances. Information Sciences, 190, 107–126. https://doi.org/10.1016/j.ins.2011.12.010
   Web of Science ®Google Scholar
• Csirik, J., & Johnson, D. (2001). Bounded space on-line bin packing: Best is better than first. Algorithmica, 31(2), 115–138. https://doi.org/10.1007/s00453-001-0041-7
   Web of Science ®Google Scholar
• Csirik, J., & van Vliet, A. (1993). An on-line algorithm for multidimensional bin packing. Operations Research Letters, 13(3), 149–158. https://doi.org/10.1016/0167-6377(93)90004-Z
   Web of Science ®Google Scholar
• Curcio, E., Amorim, P., Zhang, Q., & Almada-Lobo, B. (2018). Adaptation and approximate strategies for solving the lot-sizing and scheduling problem under multistage demand uncertainty. International Journal of Production Economics, 202, 81–96. https://doi.org/10.1016/j.ijpe.2018.04.012
   Web of Science ®Google Scholar
• Dai, B., Li, J., & Li, W. (2018). Semi-online hierarchical scheduling for bag-of-tasks on two machines. In ACM international conference proceeding series (pp. 609–614). Association for Computing Machinery.
   Google Scholar
• Dorrigiv, R. (2010). Alternative measures for the analysis of online algorithms [Ph.D. thesis]. University of Waterloo.
   Google Scholar
• Dunke, F. (2014). Online optimization with lookahead [Ph.D. thesis]. Karlsruhe Institute of Technology.
   Google Scholar
• Dunke, F., & Nickel, S. (2016). A general modeling approach to online optimization with lookahead. Omega, 63, 134–153. https://doi.org/10.1016/j.omega.2015.10.009
   Web of Science ®Google Scholar
• Dunke, F., & Nickel, S. (2021). Online optimization with gradual look-ahead. Operational Research, 21(4), 2489–2523. https://doi.org/10.1007/s12351-019-00506-z
   Web of Science ®Google Scholar
• Bakker, H., Dunke, F., & Nickel, S. (2020). A structuring review on multi-stage optimization under uncertainty: Aligning concepts from theory and practice. Omega, 96, Article 102080. https://doi.org/10.1016/j.omega.2019.06.006
   Web of Science ®Google Scholar
• Epstein, L., & Favrholdt, L. (2002). Optimal preemptive semi-online scheduling to minimize makespan on two related machines. Operations Research Letters, 30(4), 269–275. https://doi.org/10.1016/S0167-6377(02)00179-7
   Web of Science ®Google Scholar
• Fiat, A., & Woeginger, G. (Eds.). (1998). Online algorithms: The state of the art, Lecture notes in computer science 1442, Springer.
   Google Scholar
• Ghiani, G., Laporte, G., & Musmanno, R. (2004). Introduction to logistics systems planning and control. Wiley.
   Google Scholar
• Graham, R. (1966). Bounds for certain multiprocessing anomalies. Bell System Technical Journal, 45(9), 1563–1581. https://doi.org/10.1002/bltj.1966.45.issue-9
   Google Scholar
• Grötschel, M., Krumke, S., Rambau, J., Winter, T., & Zimmermann, U. (2001). Combinatorial online optimization in real time. In M. Grötschel, S. Krumke, & J. Rambau (Eds.), Online optimization of large scale systems (pp. 679–704). Springer.
   Google Scholar
• Grove, E. (1995). Online bin packing with lookahead. In Proceedings of the 6th annual ACM-SIAM symposium on discrete algorithms (pp. 430–436). Society for Industrial and Applied Mathematics.
   Google Scholar
• Helmberg, C., & Röhl, S. (2007). A case study of joint online truck scheduling and inventory management for multiple warehouses. Operations Research, 55(4), 733–752. https://doi.org/10.1287/opre.1060.0374
   Web of Science ®Google Scholar
• Hiller, B. (2009). Online optimization: Probabilistic analysis and algorithm engineering [Ph.D. thesis]. Technische Universität Berlin.
   Google Scholar
• Hiller, B., Klug, T., & Tuchscherer, A. (2014). An exact reoptimization algorithm for the scheduling of elevator groups. Flexible Services and Manufacturing Journal, 26(4), 585–608. https://doi.org/10.1007/s10696-013-9175-6
   Web of Science ®Google Scholar
• Hiller, B., Krumke, S. O., & Rambau, J. (2006). Reoptimization gaps versus model errors in online-dispatching of service units for ADAC. Discrete Applied Mathematics, 154(13), 1897–1907. https://doi.org/10.1016/j.dam.2006.03.033
   Web of Science ®Google Scholar
• T. Homem-de Mello, & Bayraksan, G. (2014). Monte Carlo sampling-based methods for stochastic optimization. Surveys in Operations Research and Management Science, 19(1), 56–85. https://doi.org/10.1016/j.sorms.2014.05.001
   Google Scholar
• Hoogeveen, H., Potts, C., & Woeginger, G. (2000). On-line scheduling on a single machine: Maximizing the number of early jobs. Operations Research Letters, 27(5), 193–197. https://doi.org/10.1016/S0167-6377(00)00061-4
   Web of Science ®Google Scholar
• Hopf, M., Thielen, C., & Wendt, O. (2017). Competitive algorithms for multistage online scheduling. European Journal of Operational Research, 260(2), 468–481. https://doi.org/10.1016/j.ejor.2016.12.047
   Web of Science ®Google Scholar
• Jaillet, P., & Lu, X. (2011). Online traveling salesman problems with service flexibility. Networks, 58(2), 137–146. https://doi.org/10.1002/net.v58.2
   Web of Science ®Google Scholar
• Jaillet, P., & Wagner, M. (2006). Online routing problems: Value of advanced information as improved competitive ratios. Transportation Science, 40(2), 200–210. https://doi.org/10.1287/trsc.1060.0147
   Web of Science ®Google Scholar
• Jaillet, P., & Wagner, M. (2008). Generalized online routing: New competitive ratios, resource augmentation, and asymptotic analyses. Operations Research, 56(3), 745–757. https://doi.org/10.1287/opre.1070.0450
   Web of Science ®Google Scholar
• Johnson, D. S. (1973). Near-optimal bin packing algorithms [Ph.D. thesis]. Massachusetts Institute of Technology.
   Google Scholar
• Kalyanasundaram, B., & Pruhs, K. (2000). Speed is as powerful as clairvoyance. Journal of the ACM, 47(4), 617–643. https://doi.org/10.1145/347476.347479
   Web of Science ®Google Scholar
• Kovalyov, M. Y., Ng, C., & Cheng, T. E. (2007). Fixed interval scheduling: Models, applications, computational complexity and algorithms. European Journal of Operational Research, 178(2), 331–342. https://doi.org/10.1016/j.ejor.2006.01.049
   Web of Science ®Google Scholar
• Kumar, R., Purohit, M., Schild, A., Svitkina, Z., & Vee, E. (2019). Semi-online bipartite matching. In Leibniz international proceedings in informatics, LIPIcs (Vol. 124, pp. 50:1–50:20). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik.
   Google Scholar
• Lawler, E., Lenstra, J., Rinnooy Kan, A., & Shmoys, D. (Eds.). (1985). The traveling salesman problem: A guided tour of combinatorial optimization. Wiley.
   Google Scholar
• Li, J. Q., Mirchandani, P., & Borenstein, D. (2009). Real-time vehicle rerouting problems with time windows. European Journal of Operational Research, 194(3), 711–727. https://doi.org/10.1016/j.ejor.2007.12.037
   Web of Science ®Google Scholar
• Li, Z., & Ierapetritou, M. G. (2010). Rolling horizon based planning and scheduling integration with production capacity consideration. Chemical Engineering Science, 65(22), 5887–5900. https://doi.org/10.1016/j.ces.2010.08.010
   Web of Science ®Google Scholar
• Liebchen, C., Lübbecke, M., Möhring, R., & Stiller, S. (2009). The concept of recoverable robustness, linear programming recovery, and railway applications. In R. Ahuja, R. Möhring, & C. Zaroliagis (Eds.), Robust and online large-scale optimization: Models and techniques for transportation systems (pp. 1–27). Springer.
   Google Scholar
• Máhr, T., Srour, J., de Weerdt, M., & Zuidwijk, R. (2010). Can agents measure up? A comparative study of an agent-based and on-line optimization approach for a drayage problem with uncertainty. Transportation Research Part C: Emerging Technologies, 18(1), 99–119. https://doi.org/10.1016/j.trc.2009.04.018
   Web of Science ®Google Scholar
• Mandelbaum, M., & Shabtay, D. (2011). Scheduling unit length jobs on parallel machines with lookahead information. Journal of Scheduling, 14(4), 335–350. https://doi.org/10.1007/s10951-010-0192-y
   Web of Science ®Google Scholar
• Megow, N., Uetz, M., & Vredeveld, T. (2006). Models and algorithms for stochastic online scheduling. Mathematics of Operations Research, 31(3), 513–525. https://doi.org/10.1287/moor.1060.0201
   Web of Science ®Google Scholar
• Mitrović-Minić, S., Krishnamurti, R., & Laporte, G. (2004). Double-horizon based heuristics for the dynamic pickup and delivery problem with time windows. Transportation Research Part B: Methodological, 38(8), 669–685. https://doi.org/10.1016/j.trb.2003.09.001
   Web of Science ®Google Scholar
• Park, H., Waddell, D., & Haghani, A. (2019). Online optimization with look-ahead for freeway emergency vehicle dispatching considering availability. Transportation Research Part C: Emerging Technologies, 109, 95–116. https://doi.org/10.1016/j.trc.2019.09.016
   Web of Science ®Google Scholar
• Powell, W. B., Jaillet, P., & Odoni, A. (1995). Stochastic and dynamic networks and routing. Handbooks in Operations Research and Management Science, 8(C), 141–295. https://doi.org/10.1016/S0927-0507(05)80107-0
   Google Scholar
• Risbeck, M., Maravelias, C., Rawlings, J., & Turney, R. (2020). Mixed-integer optimization methods for online scheduling in large-scale HVAC systems. Optimization Letters, 14(4), 889–924. https://doi.org/10.1007/s11590-018-01383-9
   Web of Science ®Google Scholar
• Ritzinger, U., Puchinger, J., & Hartl, R. F. (2016). A survey on dynamic and stochastic vehicle routing problems. International Journal of Production Research, 54(1), 215–231. https://doi.org/10.1080/00207543.2015.1043403
   Web of Science ®Google Scholar
• Sahin, F., Narayanan, A., & Robinson, E. P. (2013). Rolling horizon planning in supply chains: Review, implications and directions for future research. International Journal of Production Research, 51(18), 5413–5436. https://doi.org/10.1080/00207543.2013.775523
   Web of Science ®Google Scholar
• Sanders, P., Sivadasan, N., & Skutella, M. (2009). Online scheduling with bounded migration. Mathematics of Operations Research, 34(2), 481–498. https://doi.org/10.1287/moor.1090.0381
   Web of Science ®Google Scholar
• Schuh, G., Stich, V., Brosze, T., Fuchs, S., Pulz, C., Quick, J., Schürmeyer, M., & Bauhoff, F. (2011). High resolution supply chain management: Optimized processes based on self-optimizing control loops and real time data. Production Engineering, 5(4), 433–442. https://doi.org/10.1007/s11740-011-0320-3
   Google Scholar
• Seiden, S. S. (2002). On the online bin packing problem. Journal of the ACM, 49(5), 640–671. https://doi.org/10.1145/585265.585269
   Web of Science ®Google Scholar
• Shor, P. (1986). The average-case analysis of some on-line algorithms for bin packing. Combinatorica, 6(2), 179–200. https://doi.org/10.1007/BF02579171
   Web of Science ®Google Scholar
• Silver, E. A. (2004). An overview of heuristic solution methods. Journal of the Operational Research Society, 55(9), 936–956. https://doi.org/10.1057/palgrave.jors.2601758
   Web of Science ®Google Scholar
• Silver, E. A., & Meal, H. C. (1973). A heuristic for selecting lot size quantities for the case of a deterministic time-varying demand rate and discrete opportunities for replenishment. Production and Inventory Management, 14(2), 64–74.
   Google Scholar
• Silver, E. A., Pyke, D. F., & Peterson, R. (1998). Inventory management and production planning and scheduling (3rd ed.). Wiley.
   Google Scholar
• Sleator, D., & Tarjan, R. (1985). Amortized efficiency of list update and paging rules. Communications of the ACM, 28(2), 202–208. https://doi.org/10.1145/2786.2793
   Web of Science ®Google Scholar
• Stadtler, H., & Kilger, C. (Eds.). (2015). Supply chain management and advanced planning: concepts, models, software, and case studies (5th ed.). Springer.
   Google Scholar
• Tan, Z., & He, Y. (2005). Semi-online problems on identical machines with inexact partial information. In L. Wang (Ed.), Computing and combinatorics (pp. 297–307). Springer.
   Google Scholar
• Van den Heuvel, W., & Wagelmans, A. P. M. (2010). Worst-case analysis for a general class of online lot-sizing heuristics. Operations Research, 58(1), 59–67. https://doi.org/10.1287/opre.1080.0662
   Web of Science ®Google Scholar
• Van Hentenryck, P., & Bent, R. (2006). Online stochastic combinatorial optimization. MIT Press.
   Google Scholar
• Van Vliet, A. (1992). An improved lower bound for on-line bin packing algorithms. Information Processing Letters, 43(5), 277–284. https://doi.org/10.1016/0020-0190(92)90223-I
   Web of Science ®Google Scholar
• Wagner, H. M., & Whitin, T. M. (1958). Dynamic version of the economic lot size model. Management Science, 5(1), 89–96. https://doi.org/10.1287/mnsc.5.1.89
   Web of Science ®Google Scholar
• Woeginger, G. (1994). On-line scheduling of jobs with fixed start and end times. Theoretical Computer Science, 130(1), 5–16. https://doi.org/10.1016/0304-3975(94)90150-3
   Web of Science ®Google Scholar
• Yanıkoğlu, İ., & Gorissen, B. (2019). A survey of adjustable robust optimization. European Journal of Operational Research, 277(3), 799–813. https://doi.org/10.1016/j.ejor.2018.08.031
   Web of Science ®Google Scholar
• Zhang, G., Cai, X., & Wong, C. (2001). On-line algorithms for minimizing makespan on batch processing machines. Naval Research Logistics, 48(3), 241–258. https://doi.org/10.1002/(ISSN)1520-6750
   Web of Science ®Google Scholar