Single-Machine Job Sequencing with Treelike Precedence Ordering and Linear Delay Penalties

The problem treated is one of job sequencing on a single machine, where there is a precedence ordering between certain of the jobs, as given by a directed network which is a tree or a set of disjoint trees (a forest). The jobs form the nodes of the forest. The rule of precedence states that no job may be done before all those preceding it in its particular tree have been finished, and a job schedule is allowable if it obeys this rule. A penalty is assigned to each allowable schedule and is defined as the sum of delays for jobs, each multiplied by a number which represents the “value” or importance of that job. All delays are measured from time 0. Simple algorithms are given to find an allowable solution with minimum penalty in the two cases where all precedence relations in each tree go “inward,” toward the root, or “outward,” away from the root (where the root is a particular tip node of the tree).