Abstract: Jobs have arrival time, workload, budget and deadline parameters in economy-based grid computation and cloud computation environment. It is vital to differentiate jobs' importance and urgency for job scheduling system. Only some of these parameters have been considered in the existing algorithms. These four parameters were all taken into account here. A value density and relative deadline jointly based priority was defined. Based on this priority, a new scheduling algorithm was proposed, and EASY backfilling was used to improve the throughput of grid resources. The results of simulation show that the new defined priority can differentiate jobs' importance and urgency well, but EASY backfilling can improve resource throughput only for some priority strategies.

Key words: value density, deadline, priority, EASY backfilling, job scheduling, grid computing

摘要： 在商业网格和云计算环境中，作业有到达时间、计算量、预算、截止期等属性，区分作业的重要性和紧迫性是调度系统的关键问题之一。现有的作业优先级只考虑作业的单个或部分属性。综合考虑以上提及的四个属性，定义了基于价值密度和相对截止期的作业优先级，提出了基于价值密度和相对截止期的网格作业调度算法，并结合回填算法(EASY backfilling)来提高资源的利用率。仿真结果显示，基于价值密度和相对截止期的作业优先级很好地体现了作业的重要性和紧迫性；而回填算法在提高资源利用率上对某些优先级策略效果显著，有些则效果不明显。

关键词: 价值密度, 截止期, 优先级, 回填算法, 作业调度, 网格计算