| T. Lang E. 6. Fernandez Improving the Computation of (2008) | |||||||||||||
Abstract | |||||||||||||
| Abstract: Ways of decreasing the.number of operations needed to compute the lower bounds of optimal schedules, by reducing the number of time intervals that must be considered, are presented. The bounds apply to a system of identical processors executing a partially ordered set of tasks, with known execution times, using a non-preemptive scheduling strategy. In one approach we find that the required number of intervals depends on the graph. In our other approach, which subsumes the first, the number of intervals is decreased to at most min[D2/2, n'], where D is the deadline to complete the tasks and n is the number of tasks. The actual number ofintervals for a particular graph can be considerably smaller than this worst case. introduction In a previous paper [ 11 we discussed efficient ways of computing lower bounds for the optimal schedules presented by FernCindez and Bussell [2]. The number of operations required is approximately D2/2, where D is the deadline to complete the tasks, because one operation is performed for each interval [t,, t,] for 05 t, and t,l D. Any reduction in this number of operations must result from a reduction in the number of intervals to be considered. | |||||||||||||
Details der Publikation | |||||||||||||
| |||||||||||||