Efficient Algorithm for Scheduling Precedence-Constrained Tasks on Pipelines
Original Publication Date: 1988-Jul-01
Included in the Prior Art Database: 2005-Feb-15
A technique is described whereby an algorithm optimally schedules tasks in a pipelined processing environment utilizing a rank labeling concept for optimally scheduling precedence-constrained tasks. The concept is an improvement over prior art in that scheduling optimization can take place with a minimum overall finishing time or minimum lateness. The concept can also be used to find valid schedules, even when precedence graphs and task lengths are arbitrary. (Image Omitted) The concept provides labeling for finding the optimum schedules on a single pipeline and operates in O(n2log n) steps, given a precedence graph with n tasks in the following two cases: 1) Arbitrary precedence graphs with tasks of length 1 and 2, and sinks of any length. (A sink task is one that has no successors.