Online Resource Allocation with Limited Flexibility

References

• Acimovic J, Graves SC (2015) Making better fulfillment decisions on the fly in an online retail environment. Manufacturing Service Oper. Management 17(1):34–51.Link, Google Scholar
• Agrawal S, Wang Z, Ye Y (2014) A dynamic near-optimal algorithm for online linear programming. Oper. Res. 62(4):876–890.Link, Google Scholar
• Amazon.com, Inc. (2018) Form 10-K for 2017. U.S. Securities and Exchange Commission, Washington, DC. Accessed February 2, 2018, http://phx.corporate-ir.net/phoenix.zhtml?c=97664&p=irol-sec&control_selectgroup=Annual%20Filings.Google Scholar
• Aspnes J, Azar Y, Fiat A, Plotkin S, Waarts O (1997) On-line routing of virtual circuits with applications to load balancing and machine scheduling. J. ACM 44(3):486–504.Crossref, Google Scholar
• Azar Y, Broder AZ, Karlin AR, Upfal E (1999) Balanced allocations. SIAM J. Comput. 29(1):180–200.Crossref, Google Scholar
• Bank D, Truong V-A, Wang X (2016) Online advance admission scheduling for services, with customer preferences. Working paper, Alibaba's DAMO Academy, Hangzhou, China.Google Scholar
• Bassamboo A, Randhawa RS, Van Mieghem JA (2010) Optimal flexibility configurations in newsvendor networks: Going beyond chaining and pairing. Management Sci. 56(8):1285–1303.Link, Google Scholar
• Ben-Tal A, Nemirovski A (1999) Robust solutions of uncertain linear programs. Oper. Res. Lett. 25(1):1–13.Crossref, Google Scholar
• Berenbrink P, Czumaj A, Steger A, Vöcking B (2006) Balanced allocations: The heavily loaded case. SIAM J. Comput. 35(6):1350–1385.Crossref, Google Scholar
• Byers J, Considine J, Mitzenmacher M (2003) Simple load balancing for distributed hash tables. Kaashoek MF, Stoica I, eds. Peer-to-Peer Systems II—PTPS 2003, Lecture Notes in Computer Science, vol. 2735 (Springer, Berlin, Heidelberg), 80–87.Crossref, Google Scholar
• Chen F (2008) Substitution and variety: Group power in negotiation. Unpublished doctoral dissertation, University of Southern California, Los Angeles. Available at http://digitallibrary.usc.edu/cdm/ref/collection/p15799coll127/id/144742.Google Scholar
• Chen X, Zhang J, Zhou Y (2015) Optimal sparse designs for process flexibility via probabilistic expanders. Oper. Res. 63(5):1159–1176.Link, Google Scholar
• Chou MC, Chua GA, Zheng H (2014) On the performance of sparse process structures in partial postponement production systems. Oper. Res. 62(2):348–365.Link, Google Scholar
• Chou MC, Chua GA, Teo C-P, Zheng H (2010) Design for process flexibility: Efficiency of the long chain and sparse structure. Oper. Res. 58(1):43–58.Link, Google Scholar
• Chou MC, Chua GA, Teo C-P, Zheng H (2011) Process flexibility revisited: The graph expander and its applications. Oper. Res. 59(5):1090–1105.Link, Google Scholar
• Désir A, Goyal V, Wei Y, Zhang J. 2016. Sparse process flexibility designs: Is long chain really optimal? Oper. Res. 64(2):416–431.Link, Google Scholar
• Graves SC, Tomlin BT (2003) Process flexibility in supply chains. Management Sci. 49(7):907–919.Link, Google Scholar
• Gurumurthi S, Benjaafar S (2004) Modeling and analysis of flexible queueing systems. Naval Res. Logist. 51(5):755–782.Crossref, Google Scholar
• Iravani SMR, Kolfal B, Van Oyen MP (2007) Call-center labor cross-training: It’s a small world after all. Management Sci. 53(7):1102–1112.Link, Google Scholar
• Jasin S, Sinha A (2015) An LP-based correlated rounding scheme for multi-item ecommerce order fulfillment. Oper. Res. 63(6):1336–1351.Link, Google Scholar
• Jordan WC, Graves SC (1995) Principles on the benefits of manufacturing process flexibility. Management Sci. 41(4):577–594.Link, Google Scholar
• Kalyanasundaram B, Pruhs KR (2000) An optimal deterministic algorithm for online b-matching. Theoret. Comput. Sci. 233(1):319–325.Crossref, Google Scholar
• Lawrie DH (1975) Access and alignment of data in an array processor. IEEE Trans. Comput. C-24(12):1145–1155.Crossref, Google Scholar
• Leonardi E, Mellia M, Neri F, Ajmone Marsan M (2001) Bounds on average delays and queue size averages and variances in input-queued cell-based switches. Proc. IEEE INFOCOM 2001 Conf. Comput. Comm. 20th Annual Joint Conf., vol. 2 (Institute of Electrical and Electronics Engineers, New York), 1095–1103.Crossref, Google Scholar
• Marina MK, Das SR (2001) On-demand multipath distance vector routing in ad hoc networks. Proc. IEEE Internat. Conf. Network Protocols (ICNP) (Institute of Electrical and Electronics Engineers, New York), 14–23.Crossref, Google Scholar
• Mehta A (2013) Online matching and ad allocation. Foundations Trends Theoret. Comput. Sci. 8(4):265–368.Crossref, Google Scholar
• Mehta A, Saberi A, Vazirani U, Vazirani V (2007) Adwords and generalized online matching. J. ACM 54(5):22.1–22.19.Crossref, Google Scholar
• Mirrokni VS, Oveis Gharan S, Zadimoghaddam M (2012) Simultaneous approximations for adversarial and stochastic online budgeted allocation. Proc. 23rd Annual ACM-SIAM Sympos. Discrete Algorithms. SODA ’12, (Society for Industrial and Applied Mathematics, Philadelphia), 1690–1701.Crossref, Google Scholar
• Mitzenmacher M (2001) The power of two choices in randomized load balancing. IEEE Trans. Parallel Distributed Systems 12(10):1094–1104.Crossref, Google Scholar
• Neely MJ (2010) Stochastic network optimization with application to communication and queueing systems. Synthesis Lectures Comm. Networks 3(1):1–211.Crossref, Google Scholar
• Neely MJ, Modiano E, Rohrs CE (2005) Dynamic power allocation and routing for time-varying wireless networks. IEEE J. Selected Areas Comm. 23(1):89–103.Crossref, Google Scholar
• Pearlman MR, Haas ZJ, Sholander P, Tabrizi SS (2000) On the impact of alternate path routing for load balancing in mobile ad hoc networks. Proc. First ACM Internat. Sympos. Mobile Ad Hoc Networking & Comput. MobiHoc ’00 (Institute of Electrical and Electronics Engineers Press, New York), 3–10.Crossref, Google Scholar
• Peres Y, Talwar K, Wieder U (2015) Graphical balanced allocations and the (1 + β)-choice process. Random Structures Algorithms 47(4):760–775.Crossref, Google Scholar
• Shi C, Wei Y, Zhong Y (2019) Process flexibility for multi-period production systems. Oper. Res. Forthcoming.Link, Google Scholar
• Simchi-Levi D, Wei Y (2012) Understanding the performance of the long chain and sparse designs in process flexibility. Oper. Res. 60(5):1125–1141.Link, Google Scholar
• Sleator DD, Tarjan RE (1985) Amortized efficiency of list update and paging rules. Comm. ACM 28(2):202–208.Crossref, Google Scholar
• Stein C, Truong V-A, Wang X (2018) Advance service reservations with heterogeneous customers. Working paper, Columbia University, New York.Google Scholar
• Tassiulas L, Ephremides A (1992) Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Trans. Automatic Control 37(12):1936–1948.Crossref, Google Scholar
• Tassiulas L, Ephremides A (1993) Dynamic server allocation to parallel queues with randomly varying connectivity. IEEE Trans. Inform. Theory 39(2):466–478.Crossref, Google Scholar
• Tsitsiklis JN, Xu K (2013) Queueing system topologies with limited flexibility. Proc. ACM Sigmetrics (ACM, New York), 167–178.Google Scholar
• Van Roy B, Bertsekas DP, Lee Y, Tsitsiklis JN (1997) A neuro-dynamic programming approach to retailer inventory management. Proc. 36th IEEE Conf. Decision Control, vol. 4 (Institute of Electrical and Electronics Engineers, New York), 4052–4057.Crossref, Google Scholar
• Wallace RB, Whitt W (2005) A staffing algorithm for call centers with skill-based routing. Manufacturing Service Oper. Management 7(4):276–294.Link, Google Scholar
• Wang X, Zhang J (2015) Process flexibility: A distribution-free bound on the performance of k-chain. Oper. Res. 63(3):555–571.Link, Google Scholar