共享平台任务分配过程中,经常会遇到如下的情形:在用户未来需求任务序列(到达时刻、开始时刻和持续时间等)未知的条件下,决策者需要决定如何将当前需求合理分配给现有服务器使得平台收益最大.平台上服务器具有数量限制,同时要求用户需求一旦被分配就不可更改.以往研究建立的模型一般都是针对静态任务分配而言的,但实际需要的是满足上述约束的动态任务分配模型.以最大化共享平台收益为目标建立了占线共享平台任务分配模型,其中收益不仅包含了抽成比例,而且包含了固定收益.利用Yao原则给出了问题的竞争比的下界结果,该下界不需要任何复杂性假设条件,因此,是结构性下界.
Abstract
In the process of task allocation on sharing platforms, the following situations are often encountered:The decision-makers need to decide how to reasonably allocate the current demand to the existing server to maximize the profit of the platform, when the future demand task sequence information (arrival time, start time, duration, etc.) is unknown. There is a limit on the number of servers on the platform, and at the same time, it cannot be re-allocated once a demand is allocated. The models and algorithms established previously mainly used for static task allocation environment, but here we need a dynamic task allocation model with above constraints. This paper establishes an online sharing platform task allocation model with a maximizing platform's profit objective, where the profit include not only variable proportion for the shares but also the fixed income. Applying the Yao principle, we give a lower bound of competitive ratio for this problem. This lower bound does not need any complexity assumption, so it is a structural lower bound.
关键词
占线策略 /
共享平台 /
任务分配 /
结构性下界 /
竞争比
{{custom_keyword}} /
Key words
online strategy /
sharing platform /
task allocation /
structural lower bound /
competitive ratio
{{custom_keyword}} /
中图分类号:
O221.7
{{custom_clc.code}}
({{custom_clc.text}})
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] Schlagwein D, Schoder D, Spindeldreher K. Consolidated, systemic conceptualization, and definition of the "sharing economy"[J]. Journal of the Association for Information Science and Technology, 2020, 71(7):817-838.
[2] Borodin A, El-Yaniv R. Online computation and competitive analysis[M]. Cambridge University Press, 1998.
[3] Albers S. Online algorithms:A survey[J]. Mathematical Programming, 2003, 97(1):3-26.
[4] 代文强, 蒋青竹, 冯毅. 原材料采购问题的占线竞争策略分析[J]. 系统工程理论与实践, 2016, 36(6):1490-1495. Dai W Q, Jiang Q Z, Feng Y. Online competitive strategy for raw materials procurement[J]. Systems Engineering-Theory & Practice, 2016, 36(6):1490-1495.
[5] 代文强. 占线顶点覆盖问题的结构性下界[J]. 系统工程理论与实践, 2012, 32(1):134-138. Dai W Q. Structural lower bound analysis for online vertex covering problem[J]. Systems Engineering-Theory & Practice, 2012, 32(1):134-138.
[6] 代文强. 具有建设成本的占线中心问题竞争算法设计[J]. 系统工程理论与实践, 2011, 31(12):3342-3347. Dai W Q. Online median problem with constructive cost and its competitive algorithm analysis[J]. Systems Engineering-Theory & Practice, 2011, 31(12):3342-3347.
[7] Arkin E M, Silverberg E B. Scheduling jobs with fixed start and end times[J]. Discrete Applied Mathematics, 1987, 18(1):1-8.
[8] Bouzina K I, Emmons H. Interval Scheduling on identical machines[J]. Journal of Global Optimization, 1996, 9(3-4):379-393.
[9] Fung S P Y, Poon C K, Zheng F. Online interval scheduling:Randomized and multiprocessor cases[J]. Journal of Combinatorial Optimization, 2008, 16(3):248-262.
[10] Boyar J, Larsen K S. The Seat Reservation Problem[J]. Algorithmica, 1999, 25(4):403-417.
[11] Gupta D, Li F. Reserve Driver Scheduling[J]. Iise Transactions, 2016, 48(3):193-204.
[12] Lipton R, Tomkins A. Online interval scheduling[C]//Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms(SODA), 1994:302-311.
[13] Faigle U, Garbe R, Kern W. Randomized online algorithms for maximizing busy time interval scheduling[J]. Computing, 1996, 56(2):95-104.
[14] Faigle U, Nawijn W M. Note on scheduling intervals on-line[J]. Discrete Applied Mathematics, 1995, 58(1):13-17.
[15] Kolen A W J, Lenstra J K, Papadimitriou C H, et al. Interval scheduling:A survey[J]. Naval Research Logistics, 2007, 54(5):530-543.
[16] Goyal S, Gupta D. The online reservation problem[J]. Available at SSRN 3137745, 2018. doi:10.2139/ssrn.3137745.
[17] Yao C C. Probabilistic computations:Toward a unified measure of complexity[C]//18th IEEE Annual Symposium on Foundations of Computer Science (FOCS'77), 1977:222-227.
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}
基金
国家自然科学基金(71871045);国家社会科学基金(17XGL011,18BGL108)
{{custom_fund}}