Scheduling as a Graph Transformation
Scheduling as a Graph Transformation
复制标题
作为图转换的调度
DOI：
10.1147/rd.206.0551
复制
发表时间：
1976
期刊：
影响因子：
--
通讯作者：
T. Lang
中科院分区：
文献类型：
--
作者：
E. Fernández;T. Lang
调度的一组任务，优先约束和已知的执行时间，到一组相同的处理器。这些任务的最佳调度意味着使用最少数量的处理器来满足截止日期，或者使用固定数量的处理器在最短时间内完成。这个过程可以看作是一个转换的原始图到另一个图，其优先级不违反最优性约束，并有一个唯一的基本时间表。这种转换的分析提供了洞察调度过程中，也到确定的处理器的数量和时间的最佳时间表的下限。
The scheduling of a set of tasks, with precedence constraints and known execution times, into a set of identical processors is considered. Optimal scheduling of these tasks implies utilizing a minimum number of processors to satisfy a deadline, or finishing in minimal time using a fixed number of processors. This process can be seen as a transformation of the original graph into another graph, whose precedences do not violate the optimality constraints and has a unique basic schedule. Analysis of this transformation provides insight into the scheduling process and also into the determination of lower bounds on the number of processors and on time for optimal schedules.