Strategy-Proof Mechanism for Online Time-Varying Resource Allocation with Restart

• Published in: Journal of grid computing 2021-09, Vol.19 (3), Article 25
• Main Authors: Zhang, Jixian, Xie, Ning, Zhang, Xuejie, Li, Weidong
• Format: Article
• Language: English
• Subjects: Algorithms; Cloud computing; Computer Science; Integer programming; Management of Computing and Information Systems; Preempting; Processor Architectures; Resource allocation; Resource scheduling; Resource utilization; User Interfaces and Human Computer Interaction
• ISSN: 1570-7873; 1572-9184
• DOI: 10.1007/s10723-021-09563-1

Time-varying resource allocation in which the resource requirements of a job can vary over time is a new challenge in cloud computing. Time-varying resource allocation can be combined with an auction mechanism to improve the social welfare of resource providers. However, existing research results are based on fixed resource requirements and consequently cannot be used in time-varying resource allocation. This paper proposes a creative integer programming model for time-varying resource allocation problems and designs a strategy-proof online auction mechanism that allows jobs to be scheduled in a preemptive-restart mode. The advantage of this approach is that it can respond to high-priority jobs in a timely manner while still executing low-priority jobs with the restart mode. For the resource allocation and scheduling algorithm, we propose dynamic priority based on the dominant resource proportion and valid active time to improve social welfare and resource utilization. Furthermore, we present a payment pricing algorithm based on critical value theory. Finally, we prove that our proposed mechanism is strategy-proof. Our approach is experimentally compared with existing algorithms in terms of execution time, social welfare, resource utilization and job completion ratio.