<figure><img src="image_1.png" /></figure>

HAL
open science

# Sequencing jobs to minimize total weighted completion time subject to precedence constraints

Eugene Lawler

<figure><img src="image_2.png" /></figure>

## To cite this version:

Eugene Lawler. Sequencing jobs to minimize total weighted completion time subject to precedence constraints. [Research Report] IRIA-RR-205, IRIA. 1976, pp.27. hal-04716371

HAL Id: hal-04716371

https://inria.hal.science/hal-04716371v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
IRIA

laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

<figure><img src="image_4.png" /></figure>

SEQUENCING JOBS
TO MINIMIZE
TOTAL WEIGHTED
COMPLETION TIME
SUBJECT TO
PRECEDENCE CONSTRAINTS

Eugène LAWLER

Rapport de Recherche N° 205
Décembre 1976
SEQUENCING JOBS TO MINIMIZE TOTAL WEIGHTED COMPLETION TIME SUBJECT TO PRECEDENCE CONSTRAINTS

E.L. Lawler

IRIA - LABORIA
et

Computer Science Division*

## ABSTRACT

Suppose *n* jobs are to be sequenced for processing by a single machine, with the object of minimizing total weighted completion time. It is shown that the problem is NP-complete if there are arbitrary precedence constraints. However, if precedence constraints are "series parallel", the problem can be solved in O(n log n) time. This result generalizes previous results for the more special case of rooted trees. It is also shown how a decomposition procedure suggested by Sidney can be implemented in polynomial-bounded time. Equivalence of the sequencing problem with the optimal linear ordering problem for directed graphs is discussed.

## RÉSUMÉ

On veut ordonnancer *n* tâches sur une machine, avec pour but de minimiser la somme pondérée des dates de fin de tâches. On montre que le problème est NP complet dans le cas de relations d'ordre arbitraires. Mais si ces relations sont du type "series parallèle" le problème peut être résolu en un temps O(n log n). Ce résultat généralise des résultats précédents pour le cas plus spécifique des relations en arbre. On montre aussi qu'une procédure de décomposition suggérée par Sidney peut être implémentée en un temps polynomial.
# 1. INTRODUCTION

There are n jobs to be sequenced for processing by a single machine. The sequencing of the jobs is to be consistent with precedence constraints imposed by a given acyclic digraph G = (N,A). Each node j ∈ N is identified with a job. Job i is to precede job j if there is a directed path from i to j in G.

Each job j is assigned a positive processing time p<sub>j</sub> and a weight w<sub>j</sub>, Since the processing times of the jobs are known and fixed, the completion time C<sub>j</sub> of job j is well determined for any given sequence (assuming that the processing of the first job begins at time t = 0 and there is no idle time between consecutive jobs). The objective is to find a feasible sequence for which the weighted sum of the completion times, Σ w<sub>j</sub> C<sub>j</sub>, is minimized.

This problem has a history of slow progress from one special case to another. In 1956, Smith [14] showed that, in the absence of precedence constraints, an optimal solution could be found by sequencing the jobs in nondecreasing order of the ratios w_j/p_j. This can, of course, be done in O(n log n) running time.

Conway, Maxwell and Miller [5], in 1964, proposed a procedure for solving the problem in the case that G is in the form of "parallel chains", and all w_j = 1.

In 1971, 1972, Baker [3] and Horn [7] proposed algorithms for the case in which G is a rooted tree, and in 1973 Adolphson and Hu [1] showed that such an algorithm can be implemented in O(n log n) running time.

Finally, Sidney [13] contributed a number of theorems which apply to the problem with arbitrary precedence constraints. In particular, he showed that "job modules" can be identified and dealt with independently of the remainder of the problem. He also showed that structures we call "ρ-maximal initial sets" can be used for the purpose of decomposition. However, he indicated no efficient method for finding these ρ-maximal initial sets.
There are three principal contributions in this paper. First, we show that the problem is NP-complete [7] for arbitrary precedence constraints, even if all $w_j = 1$ or all $p_j = 1$. This means that there is very little likelihood of ever finding a polynomial-bounded algorithm for the general problem.

Second, we present an $O(n \log n)$ algorithm for the special case in which $G$ is a "series parallel" digraph. A rooted tree is a special type of series parallel digraph. Hence this result provides a proper generalization of the class of problems solved by Baker, Horn, and Adolphson and Hu.

Third, we present a polynomial-bounded algorithm for finding $p$-maximal initial sets. This algorithm can be used as part of a decomposition procedure for problems that are not series parallel. The running time of the algorithm is essentially $O(m^2 n \log n)$, where $m$ is the number of arcs and $n$ the number of nodes of $G$.

We also establish the equivalence of the sequencing problem with the so-called optimal linear ordering problem for directed graphs. Because of this equivalence, all of the results of this paper, including NP-completeness, apply with equal validity to that problem.

## 2. - NP-COMPLETENESS

The following problem, variously called "linear arrangement" or "(undirected) linear ordering", has been shown to the NP-complete by Garey, Johnson and Stockmeyer [6]. Given an arbitrary (undirected) graph $G = (N,A)$, assign the nodes of $G$ to integer points $1, 2, ..., n$ on the real line, in such a way that the sum of arc lengths is minimized.

We shall exhibit a reduction, in steps, from the linear arrangement problem to various versions of the sequencing problem defined in the previous section.

Given the undirected graph $G = (N,A)$, create a sequencing problem with a "node" job $j$ for each $j \in N$, and two "arc" jobs, $(i,j)^-$, $(i,j)^+$ for each arc $(i,j) \in A$.
Let

$$p_j = 1, \quad w_j = 0, \quad j \in N,$$

$$P(i,j)^- = 0, \quad w(i,j)^+ = -1, \quad (i,j) \in A,$$

$$P(i,j)^+ = 0, \quad w(i,j)^+ = +1, \quad (i,j) \in A.$$

Impose precedence constraints for the sequencing problem which force arc job $(i,j)^-$ to precede each of the node jobs i and j, and force arc job $(i,j)^+$ to follow each of the node jobs i and j.

It should be quite evident, without further explanation, that the sequencing problem is equivalent to the original linear arrangement problem.

We now wish to obtain a problem in which all processing times are strictly positive. It should be intuitively clear that if we let the processing time of each arc job be unity, and the processing time of each node job be "sufficiently large", then the sequencing problem remains essentially unchanged. In particular, let

$$P(i,j)^- = P(i,j)^+ = 1, \quad (i,j) \in A$$

$$p_j = n^4, \quad j \in N.$$

Suppose, for a given feasible sequence, $K_{(i,j)^-}$, $K_{(i,j)^+}$ denote the number of node jobs preceding arc jobs $(i,j)^-$, $(i,j)^+$, respectively. Then:

$$n^4 K_{(i,j)^-} + 1 \le C_{(i,j)^-} \le n^4 K_{(i,j)^-} + 2m - 1,$$

$$n^4 K_{(i,j)^+} + 2 \le C_{(i,j)^+} \le n^4 K_{(i,j)^+} + 2m,$$

where $m \le \frac{n(n-1)}{2}$ is the number of arcs in the original graph G.

The total weighted completion time for the sequence is bounded above and below as follows:
$$n^4 [\Sigma K_{(i,j)} + - \Sigma K_{(i,j)}] - 2m^2 + 3m \le \Sigma C_{(i,j)} + - \Sigma C_{(i,j)} \\ \le n^4 [\Sigma K_{(i,j)} + - \Sigma K_{(i,j)}] + 2m^2 - m$$

Since the term $[\Sigma K_{(i,j)} + - \Sigma K_{(i,j)}]$ is an integer, and $4m^2 < n^4$, it is clear that optimality depends only on the number of node jobs preceding the various arc jobs. Hence the new problem is equivalent to the previous problem.

We now wish to make each of the processing times unity. This is arranged quite simply by replacing each node job by a chain of $n^4$ jobs, each with unit processing time. The reader should have little difficulty in verifying that this does not change the problem.

Once we have obtained unit processing times for all jobs, we are free to add a constant to the weight of each job, without changing the problem. (This has the effect of adding a constant to the total weighted completion time, for any possible sequence.)

We have thus shown that the sequencing problem is NP-complete, even if all $p_j = 1$ and $w_j \in \{k, k+1, k+2\}$, for any integer $k$.

We now wish to show that the sequencing problem is NP-complete, even if all $w_j = 1$. To do this, we simply take the special case in which $p_j = 1$, $w_j \in \{1, 2, 3\}$, and do the following. Replace each job $j$ with $w_j = 1$ with a job with $p_j = 3$, $w_j = 1$. Replace each job $j$ with $w_j = 2$ by a chain consisting of a job $j_1$ with $p_{j_1} = 2$, $w_{j_1} = 1$, followed by a job $j_2$ with $p_{j_2} = 1$, $w_{j_2} = 1$. Replace each job with $w_j = 3$ by a chain of three jobs $j_1, j_2, j_3$, with $p_{j_1} = p_{j_2} = p_{j_3} = 1$, $w_{j_1} = w_{j_2} = w_{j_3} = 1$. The reader should be able to verify that this problem is equivalent to the previous problem.

We have thus shown that the sequencing problem is NP-complete, even if all $w_j = 1$ and $p_j \in \{1, 2, 3\}$.

The reader may be interested in showing that the case $w_j = 1$, $p_j \in \{0, 1\}$ is NP-complete as well.
### 3. - SERIES PARALLEL DIGRAPHS

The class of transitive series parallel digraphs is defined recursively as follows :

(3.1) A digraph consisting of a single node, e.g. $G = (\{i\}, \emptyset)$, is transitive series parallel.

(3.2) If $G_1 = (N_1, A_1)$ and $G_2 = (N_2, A_2)$, where $N_1 \cap N_2 = \emptyset$, are transitive series parallel, then

$$G = G_1 \times G_2 = (N_1 \cup N_2, A_1 \cup A_2 \cup N_1 \times N_2)$$

is also transitive series parallel. G is said to be formed by the *series composition* of $G_1$ and $G_2$.

(3.3) If $G_1 = (N_1, A_1)$ and $G_2 = (N_2, A_2)$, where $N_1 \cap N_2 = \emptyset$, are transitive series parallel, then

$$G = G_1 \cup G_2 = (N_1 \cup N_2, A_1 \cup A_2)$$

is also transitive series parallel. G is said to be formed by the *parallel composition* of $G_1$ and $G_2$.

(3.4) Only those digraphs which can be obtained by a finite number of applications of rules (3.1) - (3.3) are transitive series parallel.

A digraph G is said to be *series parallel* if and only if its transitive closure is transitive series parallel. Some examples of series parallel digraphs are shown in Figure 1. Note that every series parallel digraph is acyclic. The simplest acyclic digraph which is not series parallel is shown in Figure 2.

Given a series parallel digraph G, it is possible to repeatedly decompose G into series and parallel components, so as to show how G can be obtained by application of rules (3.1) - (3.3). The result is a rooted binary tree we call a *decomposition tree*. Each leaf of the decomposition tree is identified with a node of G. Each internal node
marked "S" indicates the series composition of the subgraphs identified with its sons, with the convention that the left son precedes the right son. Each internal node marked "P" indicates the parallel composition of the subgraphs identified with its sons. (Here the left-right ordering of sons is unimporant). Decomposition trees $T_1, T_2, T_3$ for the digraphs $G_1, G_2, G_3$ shown in figure 1 are given in figure 3. The "S's" and "P's" in the internal nodes of $T_3$ are given subscripts to facilitate reference in the next section.

In [9] it is shown how to test a given digraph to determine if it is a series parallel and, if it is, to obtain a decomposition tree. This task can be accomplished on $O(n^2)$ running time. In the sequel, we shall assume that a decomposition tree is already known for any given precedence constraints. Hence, when the claim of $O(n \log n)$ running time is made for the algorithm presented in this paper, this claim must be qualified to apply to a problem for which a decomposition tree is given.

## 4. - SIDNEY'S THEORY

Sidney's paper [13] contains a total of 25 lemmas and theorems. His most important results, and all that we shall need, are summarized in the three definitions and two theorems below. All definitions are with reference to a given digraph $G = (N,A)$, in which the nodes are identified with jobs.

### Definition 1

A nonempty subset $M \subseteq N$ is a **(job module)** if, for each job $j \in N - M$, exactly one of the following three conditions holds:

(4.1) $j$ must precede every job in $M$,

(4.2) $j$ must follow every job in $M$,

(4.3) $j$ is not constrained with respect to any job in $M$.

Every singleton subset of $N$ is a job module, as is $N$ itself. Thus
there are $n + 1$ trivial modules for every sequencing problem with $n \ge 2$ jobs. If $G$ contains no arcs (all jobs are independent), then all $2^n - 1$ nonempty subsets of $N$ are job modules.

The family of job modules of a given digraph $G$ seems to exhibit no interesting algebraic structure except that of a semilattice. Given two modules $M_1$ and $M_2$, there is a unique smallest module $M \supseteq M_1 \cup M_2$, and $M$ is not hard to determine.

What is important for our purposes is the module structure of a series parallel digraph. If $G$ is series parallel, the subtree rooted to any node of its decomposition tree is identified with a module.

For example, consider the subtree below the node $S_8$ in tree $T_3$ of Figure 3. The leaves of this tree correspond to jobs 2, 3, 5, 6, 9, 11 and $M = \{2, 3, 5, 6, 9, 11\}$ is a module. To verify that this is true, choose any job $j \in N - M$, and find the least common ancestor of $j$ and $S_8$. For example, the least common ancestor of $j = 8$ and $S_8$ is node $P_9$, which shows that 8 is unconstrained with respect to $M$. The least common ancestor of $S_8$ and $j = 13$ is $S_{11}$, which shows that 13 must follow each job in $M$.

**Theorem 1**

Let $M$ be a module of $G = (N,A)$ and $\sigma$ be an optimal sequence for $M$. Then there exists an optimal sequence for $N$ consistent with $\sigma$ (i.e. in which the jobs in $M$ appear in the same order as in $\sigma$).

**Proof :**

See Sidney [13], Lemma 23.□

A very important consequence of Theorem 1 is the following. When an optimal sequence $\sigma$ for $M$ has been determined, we can proceed as though the digraph $G$ were augmented by arcs forming a chain corresponding to $\sigma$. This means that any subsequence of consecutive elements in $\sigma$ can be dealt with as though they constituted a module of $G$. (As indeed they do with respect to the augmented graph).
The reader can probably already anticipate the outlines of a recursive algorithm for solving the series parallel sequencing problem. One starts at the bottom of the decomposition tree and works upward. To obtain an optimal sequence for the series composition of two modules, $M_1, M_2$, one simply joins together the chains $\sigma_1, \sigma_2$ already determined for $M_1, M_2$. To obtain an optimal sequence for the parallel composition of $M_1, M_2$, one somehow "merges" the chains $\sigma_1, \sigma_2$ to obtain a single chain,

### Definition 2

Let $M$ be a module. A subset $I \subseteq M$ is an initial set of $M$, if for each $j \in I$, all predecessors of $j$ in $M$ are also in $I$.

For any subset $I \subseteq N$, let

$$ \rho(I) = \frac{\sum_{j \in I} w_j}{\sum_{j \in I} p_j} $$

If each $p_j > 0$, these $\rho(I)$ is well-defined, for all $I \subseteq N$.

### Definition 3

Let $M$ be a module. An initial set $I^*$ of $M$ is said to be $\rho$-maximal if $\rho(I^*) \ge \rho(I)$, where $I$ is any initial set of $M$.

Every module $M$ admits at least one $\rho$-maximal initial set, possibly $M$ itself.

### Theroem 2

Let $M$ be a module of $G = (N,A)$ and $I$ be a $\rho$-maximal initial set of $M$. Then there exists an optimal sequence for $N$ in which the jobs in $I$ are a consecutive subsequence, preceding all other jobs in $M$.

### Proof:

See Sidney [13], Lemmas 3 and 5. These lemmas are stated in terms of a minimal $\rho$-maximal initial set of $N$, rather than an arbitrary $\rho$-maximal
initial set of an arbitrary module $M$. However, these differences do not affect the proof significantly. □

One consequence of Theorem 2 is that we can now state a rule for merging two chains $\sigma_1, \sigma_2$ to obtain a single chain for the parallel composition of $M_1, M_2$. Roughly speaking the procedure is to build up a single sequence $\sigma$ by adding to it $\rho$-maximal prefixes of the remaining portions of $\sigma_1, \sigma_2$ (If $M$ is a module consisting of two parallel chains, then there is a $\rho$-maximal initial set $I$ of $M$ which is an initial sub-sequence of just one of the chains. After $I$ is added to $\sigma$, $M-I$ is also a module consisting of two parallel chains). This is, in fact, Sidney's "parallel chain" algorithm, which is a generalization of the procedure of Conway, Maxwell and Miller [5]. However, we shall not use this approach, at least not explicitly, because we do not know how it can be implemented to yield the desired running time of $O(n \log n)$.

A more important consequence of Theorem 2, for our purposes, is that whenever a $\rho$-maximal initial set $I$ is identified in the course of our computations, the jobs in $I$ can be replaced by a single *composite job*, The weight and the processing time of the composite job are set equal to the sum of the weights and the sum of the processing times of the jobs in $I$. Thereafter, the composite job is treated as though it were a single job.

## 5. THE SERIES PARALLEL ALGORITHM

Recall that we are going to proceed from the bottom of the decomposition tree upward, finding an optimal sequence for a module $M$ from previously determined optimal sequences for its sons, $M_1$ and $M_2$. We already know one way in which this can be done; by joining chains of jobs for series composition, and merging chains (e.g. by Sidney's parallel chain algorithm) for parallel composition. However, as we have commented, we know of no way to do this within the time bound we have set for ourselves.

Instead, we propose to represent an optimal sequence for a module simply as a set of jobs, some of which may be composite, as described
in the previous section. For any such set of jobs, an optimal sequence can be found by simply placing them in nonincreasing order of the ratios, $\rho(j) = w_j/p_j$. (The precedence constraints will have been dealt with by the formation of composite jobs, so that such a sequence is necessarily feasible). Whereas in the previous paragraph we suggested a very simple rule for series composition and a more difficult one for parallele compositional, now just the opposite is the case.

For parallel composition of $M_1$ and $M_2$, all that is necessary is to form the union of the two sets $M_1$ and $M_2$. Nonincreasing ratio order is feasible and optimal for $M = M_1 \cup M_2$, assuming this is true for $M_1$, $M_2$ individually.

For series composition of $M_1$ and $M_2$, we first find a minimum-ratio job i in $M_1$ and a maximum-ratio job j in $M_2$. If $\rho(i) > \rho(j)$, all that is necessary is to form the union of the sets $M_1$ and $M_2$. Nonincreasing ratio order is feasible and optimal for $M = M_1 \cup M_2$, assuming this is true for $M_1$, $M_2$ individually.

Now suppose $\rho(i) \le \rho(j)$. In this case, $\{i, j\}$ can be treated as a module, consistent with our remarks following Theorem 1. (Job i is the last job in an optimal sequence for $M_1$ and j is the first job in an optimal sequence for $M_2$. If we imagine G to be augmented by a chain of arcs corresponding to these optimal sequences, then $\{i, j\}$ is a module with respect to the augmented digraph.) But since $\rho(i) \le \rho(j)$, it follows that $\{i, j\}$ is a $\rho$-maximal initial set of $\{i, j\}$. Hence, by Theorem 2, there exists an optimal sequence for N in which i and j are consecutive. What we do is to remove i from $M_1$, j from $M_2$ and form a composite job k = (i, j). (Note: either i and j, or both, may themselves be composite jobs. The job k represents a sequence formed by joining together the two sequences represented by i and j).

Now let us find the next minimal element i in $M_1$. If $\rho(i) \le \rho(k)$, we remove i from $M_1$ and form a new composite job k = (i, k). We continue in this way until either $M_1$ is empty or $\rho(i) > \rho(k)$. Then we find the next maximal element in $M_2$. If $\rho(k) > \rho(j)$, we can safely let $M = M_1 \cup M_2 \cup \{k\}$. But if $\rho(k) \le \rho(j)$, we remove j from $M_2$ and form a new composite job k = (k, j). At this point we start all over again with $M_1$, at the top of this paragraph.
The procedure for series decomposition is outlined below. In order to avoid tests for emptiness, we assume that $M_1$ contains a dummy element with ratio $+ \infty$ and $M_2$ a dummy element with ratio $- \infty$.

### Step 1

Find a minimal element $i$ in $M_1$ and a maximal element $j$ in $M_2$. If $\rho(i) > \rho(j)$, let $M = M_1 \cup M_2$ and halt. Otherwise, remove $i$ from $M_1$, $j$ from $M_2$ and form the composite job $k = (i, j)$.

### Step 2

2.1 Find a minimal element $i$ in $M_1$. If $\rho(i) > \rho(k)$, go to Step 3.1.

2.2 Remove $i$ from $M_1$ and form the composite job $k = (i, k)$. Return to Step 2.1.

### Step 3

3.1 Find a maximal element $j$ in $M_2$. If $\rho(k) > \rho(j)$, let $M = M_1 \cup M_2 \cup \{k\}$ and halt.

3.2 Remove $j$ from $M_2$ and form the composite job $k = (k, j)$. Go to Step 2.1.

It is apparent that this procedure requires various operations :

(1) form the union of two sets,

(2) find a minimal element in a set,

(3) find a maximal element in a set,

(4) remove an element from a set.

None of these operations is performed more than $O(n)$ times overall in determining an optimal sequence for $N$. For example, note that each time a maximal element is found, either the series composition of two sets is
completed or else that element is made part of a composite set, thereby reducing the number of elements by one. Neither of these events can occur more than $O(n)$ times. At follows that if we can insure that each of these operations requires no more than $O(\log n)$ time, we should be able to meet the target of $O(n \log n)$ running time.

There are a variety of data structures which enable us to meet the desired time bound, e.g. "mergeable heaps" [2] and "binomial trees" [15]. Our requirements are slightly novel, in that we require both min and max operations, whereas these data structures are intended to provide only one. Hence there may be some duplication required, e.g. one heap for "min" and a second for "max". However, this is quite feasible to do.

The record-keeping required to keep track of composite jobs is not difficult, and the reader may care to consider various possibilities. At the end of the computation, an optimal sequence is found by listing the jobs in the set $N$ in nonincreasing ratio order. At that point it is necessary to produce the sequence of jobs that has been built up for each composite job in $N$.

## 6. - EXAMPLE

As an example, consider the problem with precedence constraints given by digraph $G_3$ in Figure 1 and with weights and processing times as follows :

<table><thead><tr><th>j</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th><th>12</th><th>13</th></tr></thead><tbody><tr><th>w. j</th><td>1</td><td>1</td><td>3</td><td>2</td><td>7</td><td>2</td><td>10</td><td>3</td><td>1</td><td>3</td><td>4</td><td>9</td><td>1</td></tr><tr><th>p. j</th><td>1</td><td>4</td><td>1</td><td>3</td><td>2</td><td>8</td><td>1</td><td>5</td><td>10</td><td>7</td><td>8</td><td>2</td><td>6</td></tr></tbody></table>

Optimal solutions for the various subproblems, defined by the decomposition tree $T_3$ in figure 3, are as follows. We denote composite jobs by sequences, e.g. $M_8$ contains the elementary job 3 and composite jobs (2, 5) and (6, 9, 11). The reader should trace through the subalgorithm for series composition to verify the formation of composite jobs.
$$P_1 : M_1 = \{7,8\}$$

$$S_2 : M_2 = \{7,8,10\}$$

$$S_3 : M_3 = \{(4,7),8,10\}$$

$$P_4 : M_4 = \{3,2\}$$

$$S_5 : M_5 = \{5,9\}$$

$$P_6 : M_6 = \{5,6,9\}$$

$$S_7 : M_7 = \{5,(6,9,11)\}$$

$$S_8 : M_8 = \{3,(2,5),(6,9,11)\}$$

$$P_9 : M_9 = \{(4,7),3,(2,5),8,10,(6,9,11)\}$$

$$P_{10} : M_{10} = \{12,13\}$$

$$S_{11} : M_{11} = \{(4,7),3,(2,5),(8,10,6,9,11,12),13\}$$

$$S_{12} : M_{12} = \{(1,4,7,3),(2,5),(8,10,6,9,11,12),13\}$$

## 7. - FINDING ρ-MAXIMAL INITIAL SETS

Sidney [13] has suggested a decomposition procedure for dealing with precedence constraints imposed by an arbitrary acyclic digraph G = (N,A). First one finds a minimal ρ-maximal initial set I₁ of N. There exists an optimal sequence for N in which the jobs in I₁, optimally ordered, are followed by the jobs in N - I₁, also optimally ordered. Hence set aside the jobs in I₁ and continue, finding a minimal ρ-maximal initial set I₂ for N - I₁ in the subgraph induced on N - I₁, and then I₃, I₄, ..., until the jobs in N are exhausted.

This decomposition procedure, of course, does not tell one how to find an optimal sequence for any one of the ρ-maximal initial sets Iᵢ. However, if these sets are proper subsets of N, at least one has succeeded in decomposing the problem into disjoint smaller problems, each of which can be solved by dynamic programming, branch-and-bound or some other method. The difficulty is that no such decomposition may be possible. This occurs when the only ρ-maximal initial set of N is N itself.

We shall now develop a polynomial-bounded algorithm for finding a ρ-maximal initial set. The set I which is found is not necessarily (setwise) minimal. However, if minimality is desired, it should not be
difficult for the reader to see how this can be effected, at the expense
of a factor of n in the complexity of the algorithm.

The procedure can be used to find a ρ-maximal initial set of an
arbitrary module M, by simply applying it to the subgraph of G induced
on the nodes of M. For convenience, we shall assume that we wish to find
a ρ-maximal initial set of N, where G = (N,A) has m arcs and n nodes.

We shall need as a subroutine a procedure for finding an initial
set of maximum total weight, where the weights of the individual jobs
are permitted to be either positive or negative. This problem is a
slightly more general version of a problem solved by Rhys [12] (see also
[4],[11 chap. 4]), who considered only the case in which G is bipartite.
The method of solution is essentially the same as for the Rhys problem.

Let us form a flow network G* from G, by adding a source s and a
sink t, with an arc (s,j) from s and an arc (j,t) to t for each node j
of G. These arcs are assigned capacities $c_{sj} = \max(0, -w_j)$,
$c_{jt} = \max(0, w_j)$. Each arc (i,j), i ≠ s, j ≠ t, is assigned capacity
$c_{ij} = +\infty$. Note that G* has n + 2 nodes and m + 2n arcs.

We recall from network flow theory that a partition of the nodes
of G* into two sets S, T, s∈S, t∈T, determines an (s,t) cutset. The
capacity of such a cutset is :

$$c(S,T) = \sum_{i \in S} \sum_{j \in T} c_{ij}$$

i.e. the sum of the capacities of all arcs in the cutset directed from
S to T.

There is a one-to-one correspondence between initial sets of G and
finite-capacity cutsets of G*. For suppose (S,T) is such a cutset. Then
I = T - {t} is an initial set, because if i∈S, j∈T, where (i,j) is an
arc of G, then (i,j) would be in the cutset (S,T), where $c_{ij} = +\infty$,
contrary to the assumption that c(S,T) is finite. The converse is
equally easy to prove.
Let (S,T) be a cutset with c(S,T) finite, and let $I = T - \{t\}$. Then

$$
\begin{align*}
c(S,T) &= \sum_{j \in S} c_{jt} + \sum_{j \in S} c_{sj} \\
&= \sum_{j \in S} \max(0, +w_j) + \sum_{j \in T} \max(0, -w_j) \\
&= \sum_{j \in S \cup T} \max(0, +w_j) - \sum_{j \in T} w_j \\
&= \text{constant} - \sum_{j \in I} w_j
\end{align*}
$$

It follows that a minimum capacity (s,t) cutset yields a maximum
weight initial set I. A minimal capacity cutset can be found by standard
network flow techniques in O(m² n) running time [11, chap. 4].

We are now prepared to find a ρ-maximal initial set. We shall do
this by testing various trial values of the ratio ρ, until we find a
maximum feasible value.

In order to test a trial value ρ, the weight w_j of each node is
replaced by

$$
\bar{w}_j = w_j - \rho p_j
$$

A maximum weight initial set I is then found, with respect to the
weights $\overline{w}_j$. There are three possible outcomes :

Case 1 : The weight of I is strictly positive. Then

$$
\sum_{j \in I} w_j = \sum_{j \in I} w_j - \rho \sum_{j \in I} p_j > 0
$$

Since $\sum p_j > 0$, it follows immediately that the trial value $\rho$ is
too small; I itself yields a larger ratio.

Case 2 : The weight of I is strictly negative. It follows that the trial
value ρ is too large.
**Case 3**: The weight of I is zero. It follows that the trial value $\rho$ is optimal and I is a $\rho$-maximal initial set.

We propose to carry out a binary search on the optimal value of $\rho$, very similar to the search the author has proposed for the minimal cost-to-time ratio cycle problem in graphs [10] [11, chap. 3]. Our convergence argument is essentially the same as that employed for the ratio cycle problem.

Suppose each $w_j$, $p_j$ is an integer, with

$$- w^* \le w_j \le w^*,$$

$$1 \le p_j \le p^*.$$

Then surely the optimal value of $\rho$ is contained in the interval [-w*, w*]. Each trial value of $\rho$ halves the remaining interval in which the optimal value of $\rho$ can be contained. To reduce the remaining interval to length $\epsilon$, no more than

$$\log_2 w^* - \log_2 \epsilon + 1$$

trial values are required.

We now need to find a value $\epsilon$ which is no greater than the difference between any two distinct attainable ratios. Suppose $\rho, \rho'$, are attainable ratios, where $\rho \ne \rho'$ and

$$\rho = \frac{w}{p}, \quad \rho' = \frac{w'}{p'}.$$

Then

$$\left| \frac{w}{p} - \frac{w'}{p'} \right| = \left| \frac{wp' - w'p}{pp'} \right| < \left| \frac{1}{(np^*)^2} \right|.$$

It is sufficient to carry out a binary search to the point at which the optimal ratio is known to be in an interval of length not exceeding

$$\epsilon = \frac{1}{(np^*)^2}$$
At this point the smallest value in the interval is chosen for a trial value $\rho$. Either case 1 or Case 3 must result. In either case, the maximum weight initial set I which is determined is $\rho$-maximal.

It now follows that an upper bound on the total number of trial values required is :

$$2 \log_2 n + \log_2 w* + 2\log_2 p* + 1.$$

Each trial value requires an $O(m^2)$ network flow computation. Suppose that we are dealing with a population of problems over which $w*$, $p*$ are fixed, and only $m$ and $n$ vary. Then the overall running time required to find a $\rho$-maximal initial set is $O(m^2 n \log n)$. In any case, even without this supposition, the computation is bounded by a polynomial in the number of bits required to specify an instance of the problem.

## 8. THE DIRECTED LINEAR ORDERING PROBLEM

A problem closely related to the sequencing problem is that of optimally ordering the nodes of a weighted digraph. It was, in fact, this problem which Adolphson and Hu [1] dealt with. They established the equivalence of the two problems in the case that the digraph $G$ is a rooted tree. Our purpose here is to make clear the equivalence of the two problems for arbitrary acyclic digraphs.

Let $G = (N,A)$ be an acyclic digraph, with a "width" $p_j > 0$ assigned to each node $j \in N$ and a weight $q_{ij}$ assigned to each arc $(i,j) \in A$.

The nodes are to be placed on the real line in the interval $[0, \sum p_j]$, consistent with width restrictions, in such a way that all arcs are directed from "left-to-right". The object is to minimize the weighted sum of the arc lengths.

More precisely, let $x_j$ be the coordinate assigned to node $j$. If $(i,j) \in A$, then it is required that $x_i < x_j$. If $j$ is the left-most node, then $x_j = p_j$. If nodes $i$ and $j$ are placed at consecutive positions on the line, then $x_j = x_i + p_j$. The value of the objective function is
$$Z = \sum_{(i,j) \in A} q_{ij} (x_j - x_i)$$

Formally, let $q_{ij} = 0$, for all $(i,j) \notin A$. Then

$$ 
\begin{align*}
Z &= \frac{1}{2} \left[ \sum_{i} \sum_{j} q_{ij} (x_j - x_i) \right] \\
&= \frac{1}{2} \left[ \sum_{i} \sum_{j} q_{ij} x_j - \sum_{i} \sum_{j} q_{ij} x_i \right] \\
&= \frac{1}{2} \left[ \sum_{j} \sum_{i} q_{ij} x_j - \sum_{j} \sum_{i} q_{ji} x_i \right] \\
&= \sum_{j} w_j x_j
\end{align*}
$$

where

$$w_j = \frac{1}{2} \left[ \sum_{(i,j) \in A} q_{ij} - \sum_{(j,i) \in A} q_{ji} \right] \quad (8.1)$$

The $x_j$ values can now be interpreted as completion times of jobs in a corresponding sequencing problem with the same digraph G for precedence constraints. Hence it follows that equations (8.1) yield a simple means for reducing a directed linear ordering problem to an equivalent sequencing problem on the same digraph G, with the same $p_j$ values.

As a very simple example, consider the linear ordering problem on the digraph in Figure 4, with arc weights as indicated by numerical values on the arcs. Each $p_j = 1$. Consider the solution $x_j = j$, where

$$ 
\begin{align*}
Z &= 3(3 - 1) + 2(3 - 2) + 1(4 - 2) + 1(5 - 3) + 6(5 - 4) \\
&= 18.
\end{align*}
$$

By equations (8.1) the values of $w_j$ for the equivalent sequencing problem are $w_1 = w_2 = \frac{3}{2}$, $w_3 = 2$, $w_4 = -\frac{5}{2}$, $w_5 = \frac{7}{2}$. For the feasible solution $C_j = j$, we have:

$$ 
\begin{align*}
Z &= \frac{3}{2}(1) + \frac{3}{2}(2) + 2(3) - \frac{5}{2}(4) + \frac{7}{2}(5) \\
&= 18.
\end{align*}
$$
Equations (8.1) also provide the key for obtaining a converse reduction from the sequencing problem to the linear ordering problem. But whereas the $w_j$'s are uniquely determined by the $q_{ij}$'s as independent variables, the converse is not necessarily the case. The $q_{ij}$'s may not be uniquely determined. Or much worse, there may be no solution for the $q_{ij}$'s at all.

As a simple example of this difficulty, let $G = (N,A)$ contain a single arc $(1,2)$, with $w_1 = w_2 = 1$. Then

$$w_1 = -\frac{1}{2} q_{12} = 1,$$

$$w_2 = \frac{1}{2} q_{12} = 1,$$

an obvious contradiction.

One way to resolve this problem is to add an $(n+1)$st node to $G$, with arcs $(j, n+1)$, for all $j$. "Slack" weights $q_{j,n+1}$ can always be found to resolve any inconsistency. For our example, we now have

$$w_1 = -\frac{1}{2} [q_{12} + q_{13}] = 1$$

$$w_2 = \frac{1}{2} [q_{12} - q_{23}] = 1.$$

One solution is $q_{12} = 2, q_{13} = -4, q_{23} = 0$.

Since node $n+1$ must always be assigned a position at the extreme right, its position is fixed. The effect of the slack weights $q_{j,n+1}$ is to add a linear cost of the form

$$\sum_j q_{j,n+1} x_j$$

to the objective function $Z$. If the problem is redefined to include such a term in the objective function, then for every sequencing problem on a digraph $G$, there is an equivalent linear ordering problem on the identical digraph. Otherwise, it may be necessary to find an equivalent linear ordering problem on an $(n+1)$ node digraph.
Notice that when a reduction is made back from the $(n + 1)$-node
linear ordering problem to a sequencing problem, there is an$(n + 1)$st
job which must follow all the others. Since its completion time is fixed,
this job simply contributes a constant to the objective function.

It follows that all of the results in this paper apply with equal
validity to the directed linear ordering problem. In particular, this
problem is NP-complete, even if all node widths are unity. The directed
linear ordering problem can be solved in $O(n \log n)$ time, if the digraph
is series parallel. And Sidney's decomposition technique can be adapted
to the problem.
REFERENCES

[1] ADOLPHSON, D. & T.C. HU, "Optimal Linear Ordering", SIAM J. Appl. Math., 25 (1973) 403-423.

[2] AHO, A.V., J.E. HOPCROFT & J.D. ULLMAN, *The Design of Computer Algorithms*, Addison Wesley, Reading, Mass., 1974.

[3] BAKER, K.R., "Single Machine Sequencing with Weighting Factors and Precedence Constraints", unpublished paper, 1971.

[4] M.L. BALINSKI, "On a Selection Problem" Management Science 17 (1970) p. 230-231.

[5] CONWAY, R.W., W.L. MAXWELL & L.W. MILLER, *Theory of Scheduling* Addison-Wesley, Reading, Mass., 1967.

[6] M.R. GAREY, D.S. JOHNSON and L. STOCKMEYER, "Some Simple NP-Complete Problems", to appear in *Theoretical Computer Science*.

[7] HORN, W.A., "Single Machine Job Sequencing with Treelike Precedence Ordering and Linear Delay Penalties", SIAM J. Appl. Math., 23 (1972) 189-202.

[8] KARP, R.M., "On the Computational Complexity of Combinatorial Problems", Networks 5 (1975) 45-68.

[9] LAWLER, E.L. & R.E. TARJAN, "Analysis and Isomorphism of Series Parallel Digraphs", to appear.

[10] E.L. LAWLER, "Optimal Cycles in Doubly Weighted Directed Linear Graphs", Theory of Graphs, P. Rosenstiehl, ed., Dunod, Paris, and Gordon and Breach, New York, 1961, pp. 209-214.

[11] E.L. LAWLER, *Combinatorial Optimization: Networks and Matroids*, to be published by Holt, Rinehart, and Winston, New York, 1976.
[ 12 ] J. RHYS, "Shared Fixed Cost and Network Flows", Management Science, 17(1970) 200-207.

[ 13 ] SIDNEY, J.B., "Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs", Operations Research, 22 (1975) 283-298.

[ 14 ] SMITH, W.E., "Various Optimizers for Single-Stage Production", Naval Res. Log. Quart., 3 (1956) 59-66.

[ 15 ] J. VUILLEMIN, "A Data Structure for Manipulating Priority Queues", University of Paris XI, n° 182, 1976.
<figure><img src="image_5.png" /><figcaption>**Figure 1** : Series parallel digraphs</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>**Figure 2** : A Nonseries parallel digraph</figcaption></figure>
<figure><img src="image_7.png" /><figcaption>Figure 3 : Decomposition trees</figcaption></figure>
<figure><img src="image_8.png" /><figcaption>**Figure 4 :** Example linear ordering problem</figcaption></figure>