UET系统在m台处理机上的一种调度算法及其性能分析

本文介绍了一种UET系统中有效的调度算法,其时间复杂性函数为O(na(n)+e)。该算法对m=2台处理机的调度为最优,而对m≥3台处理机上的未确定调度子问题,其解与最优解之比的最小上界为2-2/m,它也是一个近似程度相当好的有效算法。

An Algorithm of Scheduling in UET System for m Processors and Its Performance Analysis

This paper introduces an effective scheduling algorithm in UET (Unit Execution Time) system, its time complexity function being O (na(n) + e). The scheduling list made by the algorithm for m = 2 processors is an optimal scheduling list; and for those open scheduling subproblems, the minimal upper bound of the ratio between its solution and optimal solution is g-2/m, a much better approximation.and hence, also showing the effec- tiveness of the algorithm.