Online Resource Allocation with Limited Flexibility

• 成果类型: Article
• 署名作者: Asadpour, Arash; Wang, Xuan; Zhang, Jiawei
• 署名单位: New York University; Hong Kong University of Science & Technology
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.2018.3220
• 发表日期: 2020
• 页码: 642-666
• 关键词: flexibility; long-chain design; dynamic resource allocation; online decision making; worst-case bound

摘要

We consider a class of online resource-allocation problems in which there are n types of resources with limited initial inventory and n demand classes. The resources are flexible in that each type of resource can serve more than one demand class. In this paper, we focus on a special class of structures with limited flexibility, the long-chain design, which was proposed by Jordan and Graves [Jordan WC, Graves SC (1995) Principles on the benefits of manufacturing process flexibility. Management Sci. 41(4):577-594.] and has been an important concept in the design of sparse flexible processes. We study the long-chain design in an online stochastic environment in which the requests are drawn repeatedly and independently from a nonstationary probability distribution over the different demand classes. Also, the decision on how to address each request must be made immediately upon its arrival. We show the effectiveness of the long-chain design in mitigating supply-demand mismatch under a simple myopic online allocation policy. In particular, we provide an upper bound on the expected total number of lost sales that is irrespective of how large the market size is.