一种独立任务调度问题的相对量化模型

在分布式处理领域,独立任务调度问题是一个NP难题.现有各种调度模型普遍采用基于运行时间的任务量化方式,这使得异构系统调度问题较同构系统更为复杂,因为异构系统中同一任务在不同节点上的运行时间不等.该文提出了一种独立任务调度问题的相对量化模型,该模型采用一种相对量化方案来量化任务的载荷量和计算节点的负载能力及负载状况.基于该模型,可用LPT、AI之类的同构调度算法解决异构调度问题,从而使异构调度问题的复杂度降到与同构调度问题相当.理论分析与实验研究证明了新模型的有效性和良好的工程实用性.

A relative quantitive model for independent task scheduling problem

In the field of distributed processing, the independent task scheduling problem is known to be NP-complete. Its complexity increases when task scheduling is to be done in a heterogeneous computing system, where the processors in the network may not be identical and the processing time for the same task is varied. In this paper a relative quantitative model for the independent task scheduling problem is presented based on a new method to quantize the workload of tasks and the capacity of computational nodes. Its characteristics are analyzed by comparing them with existing scheduling models. Based on the new model, heterogeneous scheduling problems may be worked out with homogeneous scheduling algorithms, such as LPT, AI, etc. , reducing the complexity of the heterogeneous scheduling problem to be similar to that of homogeneous scheduling problems. Theoretical analysis and computer simulations indicate that the new relative quantitive model is effective and superior to existing models.