关键词: 云计算, 多阶段工作, 多处理机调度, 近似算法, 算法分析

Abstract: With the increasing impact of big data on people's lives,the demand for data storage and computation continues to grow,and the emergence of cloud computing effectively meets this demand.In cloud computing systems with high real-time requirements,resource requests from clients are regarded as 2-stage jobs with deadlines and certain profits,while cloud servers are seen as 2-stage machines.The deadlines for different resource requests are usually different,and if the cloud center can complete the request before the deadline,it can obtain corresponding profits.Existing 2-stage jobs scheduling algorithms that aim to maximize revenue are conducted under a common deadline constraint,whereas in reality,different resource requests may have varying deadlines.Based on the demand in the research and applications in cloud computing and data centers,we build a mathematical model for job scheduling in cloud computing.We study the problem of scheduling 2-stage jobs with multiple deadlines on multiple 2-stage machines.Let k be the number of deadlines of the jobs.When k is a constant,a polynomial-time approximation algorithm with approximation ratio(3k＋∊) is provided.When the number of machines is a fixed constant,the approximation ratio is further improved to(k＋∊),where ∊ > 0 is an arbitrary constant.Therefore,when k is a constant,the problem has a constant ratio polynomial-time approximation algorithm.In the case where T-processing time is greater than R-processing time,a pseudo-polynomial time approximation algorithm with approximation ratio 2 is presented,further improving the approximation ratio.

Key words: Cloud computing, Multiple-stage jobs, Multiple machinescheduling, Approximation algorithms, Algorithm analysis