# On batch scheduling of jobs with stochastic service times cost structures on a single server

J. Bruno, Edward-Grady Coffman, D.B Johnson

► To cite this version:

J. Bruno, Edward-Grady Coffman, D.B Johnson. On batch scheduling of jobs with stochastic service times cost structures on a single server. [Research Report] IRIA-RR-120, IRIA. 1975, pp.27. hal-04716078

HAL Id: hal-04716078

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

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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
RIA
laboria

ARCHIVES

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

laboratoire de recherche
en informatique
et automatique

On batch scheduling of jobs
with stochastic service times
cost structures
on a single server.

J. Bruno, E.G. Coffman,
D.B. Johnson

Rapport de Recherche n° 120

Mai 1975
ON BATCH SCHEDULING OF JOBS WITH STOCHASTIC SERVICE TIMES
COST STRUCTURES ON A SINGLE SERVER

J. Bruno,* E.G. Coffman,**D.B. Johnson*

ABSTRACT

Jobs are modeled as decision tress of tasks in this paper. With each task is associated a joint probability distribution governing the deferral cost of the task, the execution time of the task, and a pointer to the descendant task next to be executed in the job. For a collection of jobs, an efficient algorithm is found and analyzed for sequencing jobs so as to minimize the total expected cost.

RÉSUMÉ

Dans cet article, les travaux sont représentés comme des arbres de décision de tâches. A chaque tâche est associée une distribution de probabilité reliant le coût du report de la tâche, le temps d'exécution de la tâche et un pointeur à la tâche suivante du travail. Pour un ensemble de travaux, on trouve et on analyse un algorithme efficace de séquencement des travaux permettant de minimiser l'espérance du coût total.
ON BATCH SCHEDULING OF JOBS WITH STOCHASTIC
SERVICE TIMES AND COST STRUCTURES
ON A SINGLE SERVER.

J. Bruno

The Pennsylvania State University

E. G. Coffman

Institut de Recherche d'Informatique et d'Automatique

D. B. Johnson

The Pennsylvania State University

I. Introduction

We consider the general problem of minimizing the mean weighted
flow time of a collection of independent jobs executed on a single pro-
cessor, where the weights are interpreted as deferral costs. The present
work extends previous results on deterministic problems [Col, Sil,
Hol, Br1, Br2] by introducing a probability model governing execution
times, deferral costs, and the sequences of tasks which make up each job.
In particular, each job may be viewed as a decision tree whose vertices
correspond to tasks. For each task T there is an arbitrary but known
joint probability distribution governing the execution time, deferral
cost, and the decision as to the next task, if any, to be executed following
T. Thus, execution of a job consists of the execution of some chain of
tasks in the tree beginning with the initial (root) task and ending with
some descendant task in the tree.

It is only at task terminations that job executions can be interrupted
(preempted) in order to assign the processor to another job. Mean weighted
flow times for schedules of a collection of independent jobs are computed as
the weighted sums of task finishing times. The main result of our study is
a polynomial-time algorithm for deciding at each task termination the job
to be assigned to the processor in order that the expected value* of
the mean weighted flow time of the entire schedule be minimized.

The applications of our model are fairly evident. We may conceive
of any multiprogrammed system in which the structure underlying the
mechanism for deciding the nature (task sequence) of each job is a tree.
Such structures are certainly common, if not as a detailed model, then
as a gross model in which tasks are re-defined or enlarged so that a tree
structure applies to the decision process. We must assume that the jobs
have been analyzed or run sufficiently often so that joint probability
distributions describing execution times, deferral costs, and the "out-
comes" (next-task decisions) can be estimated reasonably closely. This
might, for example in a compiler, involve estimation of input-error prob-
abilities, as this would constitute a natural and frequent basis for the
next-task decision. Clearly, the context of applications extends also to
the general industrial job-shop environments discussed, for example, in
[Col].

In the remainder of the paper we first formally define the model to
be studied, after which results are presented for a "locally computable"
rank function (job sequencing criterion) used as the basis of a simple
scheduling policy. The optimality of the policy is proved, and finally,
questions regarding the polynomial-time computation of rank functions are
resolved.

<footnote>*In this paper the term "expected value" will be used to refer to the first moment of a probability distribution. The term "mean" will be reserved for indicating simply the arithmetic mean of a sequence of numbers.</footnote>
## II. The Model

A scheduling problem $\mathcal{P}$ consists of

i) a task system $(\mathcal{T}, <)$, where $\mathcal{T}$ is an indexed set of $n \ge 0$ tasks and $<<$ is a partial order on $\mathcal{T}$. The index set of $\mathcal{T}$ is denoted $I(\mathcal{P})$ and for each $j$ in $I(\mathcal{P})$, $T_j$ is an element in $\mathcal{T}$. The partial order is restricted to be an **initially rooted forest**; i.e. for each $i, j$, $k$ in $I(\mathcal{P})$ if $T_i < T_k$ and $T_j < T_k$ then either $T_i < T_j$ or $T_j < T_i$. A task $T_i$ is an **immediate successor** of $T_j$ if $T_j < T_i$ and for no $T_k$ do both $T_j < T_k$ and $T_k < T_i$ hold. A task $T_i$ is **initial** if, for no $T_k$, $T_k < T_i$.

ii) for each $j$ in $I(\mathcal{P})$, a random variable $S_j$ which takes on positive values and gives the service requirement (execution time) of $T_j$. Let $\tau_j$ denote the expected value of $S_j$.

iii) for each $j$ in $I(\mathcal{P})$, a random variable $C_j$ which gives the deferral cost of $T_j$. The range of $C_j$ is unrestricted. Let $w_j$ denote the expected value of $C_j$.

iv) for each $j$ in $I(\mathcal{P})$, a random variable $D_j$ which takes on values corresponding to the indices of the immediate successors of $T_j$ or zero, signifying that $T_j$ has no successors (zero is never a task index). We impose the restriction that if $T_i$ is an immediate successor of $T_j$ then $\text{Pr}\{D_j=i\} > 0$; i.e., there are no tasks whose probability of execution is zero.

v) for each $j$ in $I(\mathcal{P})$, a joint probability distribution function $F_j$ which governs the mutual behavior of $S_j$, $C_j$, and $D_j$. For all $i$ and $j$ the triples $(S_i, C_i, D_i)$ and $(S_j, C_j, D_j)$ are independent.

A scheduling problem with one initial task is called a **job**. If $\mathcal{P}$ is a non-empty scheduling problem, then $\mathcal{P}$ may be expressed as a collection of jobs $\mathcal{P} = \{J_1, \dots, J_r\}$. In the following we shall often need to re-
strict our attention to a subset of the tasks in a scheduling problem $\mathcal{P}$
or job $J$. Let $U \subseteq I(\mathcal{P})$ and define $\mathcal{T}/U$ and $\prec/U$ as

$$
\mathcal{T}/U = \{T_j \mid T_j \in \mathcal{T}, j \in U\}
$$

and

$$
\prec/U = \{(T_i, T_j) \mid (T_i, T_j) \in \prec, i \in U, j \in U\}.
$$

The scheduling problem $\mathcal{P}/U$ is obtained from $\mathcal{P}$ by restricting our atten-
tion to the task system $(\mathcal{T}/U, \prec/U)$. $\mathcal{J}/U$ is similarly defined with re-
spect to $\mathcal{J}$. Finally, for a given $\mathcal{P}$ let $K_i$ denote just that subset
of $I(\mathcal{P})$ consisting of $i$ and all indices $j$ such that $T_i \prec T_j$.

Now consider the scheduling of $\mathcal{P} = \{J_1, \dots, J_r\}$. Let $T_{j_1}, \dots, T_{j_r}$ be the initial tasks of $J_1, \dots, J_r$, respectively. The processor must be assigned to one of the tasks $T_{j_1}, \dots, T_{j_r}$. Assuming the processor is assigned at time $t \ge 0$ to task $T_{j_\ell}$, the initial task of $J_\ell$, the processor may not be reassigned until time $t+S_{j_\ell}$. When $T_{j_\ell}$ finishes, the contribution of $T_{j_\ell}$ to the mean weighted flow time is $(t+S_{j_\ell})C_{j_\ell}$. The value of $D_{j_\ell}$ determines the "subjob" of $J_\ell$ to replace $J_\ell$ in $\mathcal{P}$; viz. if $D_{j_\ell} = 0$ then $J_\ell$ is removed from $\mathcal{P}$; if $D_{j_\ell} = i \ne 0$ then $J_\ell/K_i$ replaces $J_\ell$ in $\mathcal{P}$. Given some policy for selecting from among initial tasks, a schedule and corresponding mean weighted flow time is obtained by applying the above procedure repeatedly until no job remains.
We shall defer a more formal specification of the procedure until after we have introduced and illustrated some notation convenient for this purpose.

We define a transition function $\delta$ which takes as arguments a sched-
uling problem $\mathcal{P}$, an initial task $T_j$ of $\mathcal{P}$, and a value $i$ where $i$ is
either zero or the index of an immediate successor of $T_j$. The value "re-
turned" by $\delta$ is a (possibly empty) scheduling problem $\delta(\mathcal{P}, T_j, i)$ determined by: if $i=0$ then $\delta(\mathcal{P}, T_j, i) = \mathcal{P}/(I(\mathcal{P}) - K_j)$; if $i \neq 0$ then $\delta(\mathcal{P}, T_j, i) = \mathcal{P}/(I(\mathcal{P}) - (K_j - K_i))$.

In Figure 1 we give a scheduling problem consisting of two jobs $J_1$ and $J_2$. The initial task $T_1$ of $J_1$ has two possible "outcomes" $D_1=2$ or $D_1=3$. The random variables $S_1, C_1$ and $D_1$ are governed by

$$ \Pr\{S_1 = 1 \text{ and } C_1 = \frac{1}{2} \text{ and } D_1 = 2\} = p, \quad 0 < p < 1 $$

and

$$ \Pr\{S_1 = 2 \text{ and } C_1 = 1 \text{ and } D_1 = 3\} = 1 - p. $$

The remaining variables are governed by

$$ \Pr\{D_1 = 0\} = 1 \quad \text{for } i = 2,3,4, $$

$$ \Pr\{S_1 = 1\} = 1 \quad \text{for } i = 2,3,4, $$

$$ \Pr\{C_1 = 1\} = 1 \quad \text{for } i = 2,4, $$

and

$$ \Pr\{C_3 = 5\} = 1. $$

Therefore job $J_1$ has two possible realizations, namely, $T_1/1/\frac{1}{2}$ followed by $T_2/1/1$, or $T_1/2/1$ followed by $T_3/1/5$, where the notation corresponds to *task/execution time/deferral cost*. The former realization occurs with probability $p$ and the latter with probability $1-p$. Job $J_2$ has exactly one realization, $T_4/1/1$ and hence $\mathcal{P} = \{J_1, J_2\}$ has exactly six realizations.

For example, if we assign the processor to task $T_1$ at $t=0$ there are only two possibilities:
<figure><img src="image_2.png" /><figcaption>Figure 1 A Scheduling Problem</figcaption></figure>
(1) $T_1$ finishes at $t=1$ contributing $\frac{1}{2}$ to the mean weighted flow time, and results in the scheduling problem $\delta(P, T_1, 2) = P/\{2,4\}$, or

(2) $T_1$ finishes at $t=2$ contributing 2 to the mean weighted flow time, and results in the scheduling problem $\delta(P, T_1, 3) = P/\{3,4\}$.

A scheduling policy or simply policy $\xi$ is a mapping which associates with each non-empty scheduling problem $P$ an initial task $\xi(P)$ of $P$.

The mean weighted-flow-time criterion for policy $\xi$ applied to problem $P$ at time $t \ge 0$ is determined by procedure mwft applied to $\xi, P$ and $t$.

**Algorithm 1**

Input: a policy $\xi$, a scheduling problem $P$, and a nonnegative number $t$.

Output: the mean-weighted-flow-time criterion of $\xi$ applied to $P$ assuming the processor is unavailable until $t \ge 0$.

Method:

procedure mwft($\xi$, $P$, $t$)

begin

if $P$ is empty then return 0

else

begin

let $j$ be such that $T_j = \xi(P)$;

$(\tau, w, i) := (S_j, C_j, D_j);$

return $(t+\tau)w + \text{mwft}(\xi, \delta(P, T_j, i), t+\tau)$

end

end mwft
The assignment statement $(\tau,w,i) := (S_j, C_j, D_j)$ is executed by generating samples for the random variables $S_j$, $C_j$, and $D_j$ according to the distribution $F_j$ and assigning these values to $\tau$, $w$, and $i$, respectively. Thus, $\text{mwft}(\xi, \mathcal{P}, t)$ is a random variable taking on values depending on the outcomes of the experiments carried out during the execution of Algorithm 1.

Let $\overline{\text{mwft}}(\cdot, \cdot, \cdot, \cdot)$ denote the expected value of the random variable $\text{mwft}(\cdot, \cdot, \cdot, \cdot)$. We say that a policy $\xi$ is **optimal** if for all policies $\xi'$ and problems $\mathcal{P}$

$$ \overline{\text{mwft}}(\xi, \mathcal{P}, 0) \le \overline{\text{mwft}}(\xi', \mathcal{P}, 0) $$

Let $\mathcal{P}$ be the scheduling problem in Figure 1 and let $\xi$ be a policy such that $\xi(\mathcal{P}) = T_1$, $\xi(\mathcal{P}/\{2,4\}) = T_4$ and $\xi(\mathcal{P}/\{3,4\}) = T_3$. It is easy to see that $\text{mwft}(\xi, \mathcal{P}, 0)$ takes on two possible values depending on the outcome of $D_1$. These two values are $\frac{1}{2} + 2 + 3 = \frac{11}{2}$ and $2 + 15 + 4 = 21$, the former occurring with probability $p$ and the latter with probability $1-p$. Therefore $\overline{\text{mwft}}(\xi, \mathcal{P}, 0) = 21 - \frac{31}{2}p$.

With our notion of optimality it may appear that a general formulation of a sequential decision policy must be structured so that the decision as to which task to execute after, say, j tasks have been executed must be a function of $\mathcal{P}$, the exact sequence of the first j tasks, and the execution, deferral cost, and next-task parameters in this sequence. In fact, however, there would be no gain in generality over the class of policies we are considering, for we have stated that the triples $(S_i, C_i, D_i)$ and $(S_j, C_j, D_j)$ are statistically independent for all $i \ne j$, and by implication the functions $F_j$ depend neither on sequence nor the times at which tasks are assigned. In short, we need consider only those policies which decide on
the (j+1)st task selection based solely on the information contained in
the scheduling problem remaining after executing the first j tasks
selected in the sequence.
### III. A Rank Function

Our aim in this section is to define a rank function $\rho$ which as-sociates with each job $J$ a number $\rho(J)$ called the rank of $J$. This rank function will have the property that optimal schedules are obtained by assigning the processor to the initial vertex of a job with maximal rank. In the next section we prove that scheduling according to a largest-rank-first policy is optimal and, conversely, that any optimal schedule corresponds to such a policy.

A set $U \subseteq I(\mathcal{P})$ is called an **initial set** with respect to $\mathcal{P}$ if
i) $U \neq \emptyset$

ii) if $T_j < T_{j'}$, then $j \notin U$ implies $j' \notin U$.

For example, the sets $\{1\}$, $\{1,2,3\}$, and $\{1,2,4\}$ are some of the initial sets for the example in Figure 1.

Let $J$ be a job, $T_j$ the initial task of $J$, and $U$ a subset of the task indices of $J$. We define the random variables $s(J,U)$ and $c(J,U)$ as

$$s(J,U) = \begin{cases} 0 & \text{if } j \notin U \\ S_j + s(\delta(J, T_j, D_j), U) & \end{cases}$$

and

$$c(J,U) = \begin{cases} 0 & \text{if } j \notin U \\ C_j + c(\delta(J, T_j, D_j), U) & \end{cases}$$

If $U$ is an initial set we define $\tau(J,U)$ and $w(J,U)$ as the expected values of $s(J,U)$ and $c(J,U)$, respectively.
Let $T_j$ be a task in $J$ and $T_{i_1}, \dots, T_{i_k}$ be a sequence of tasks in $J$ such that $T_{i_{\ell+1}}$ is an immediate successor of $T_{i_\ell}$ for $\ell=1, \dots, k-1$, $T_{i_1}$ is the initial task of $J$ and $T_{i_k} = T_j$. We define the number $p_j$, the probability of "reaching" $T_j$, as

$$p_j = \prod_{\ell=1}^{k-1} \mathrm{Pr}\{D_{i_\ell} = i_{\ell+1}\}.$$

The empty product ($k-1=0$) is equal to 1. It follows from our definition of a scheduling problem that $p_j > 0$ for all $j \in I(J)$.

**Lemma 1** Let $J$ be a job and $U$ an initial set with respect to $J$. Then

$$\tau(J, U) = \sum_{j \in U} p_j \tau_j \quad (1)$$

and

$$w(J, U) = \sum_{j \in U} p_j w_j. \quad (2)$$

**Proof:** The proof is by induction on the number of tasks in $U$. The basis $|U| = 1$ is easy since $\tau(J,U) = \tau_j$ and $w(J,U) = w_j$ where $T_j$ is the initial task of $J$.

Let $U$ be an initial set of $J$ such that $|U| \ge 2$ and assume the lemma holds for any job and any corresponding initial set with fewer than $|U|$ elements.

Let $T_i$ be the initial task of $J$ and $T_{i_1}, \dots, T_{i_k}$ the immediate successors of $T_i$. Let $U_{i_\ell} = K_i \cap U$ for $\ell=1, \dots, k$. The set $U_{i_\ell}$ is either empty or an initial set of $J/K_{i_\ell}$ for $\ell=1, \dots, k$. We can write $\tau(J,U)$ as

$$\tau(J, U) = \tau_i + \sum_{\ell=1}^{k} \mathrm{Pr}\{D_i = i_\ell\} \tau(J/K_{i_\ell}, U_{i_\ell}) .$$

By applying the induction hypothesis to $\tau(J/K_{i_\ell}, U_{i_\ell})$ and using the
definition of the $p_j$'s it is not too difficult to see that

$$ \tau(J, U) = \sum_{j \in U} p_j \tau_j $$

A similar argument applies to $w(J, U)$. $\square$

In the case where $U$ is not an initial set of $J$ we shall define the quantities $\tau(J, U)$, and $w(J, U)$ to be given as in (1) and (2), respectively.

For any set $U \subseteq I(\mathcal{P})$ we define

$$ \rho(J, U) = \frac{w(J, U)}{\tau(J, U)} $$

and $\rho(J)$, the rank of job $J$, as $\rho(J) = \max\{\rho(J, U) | U$ is an initial set with respect to $J\}$.

We say a set $U \subseteq I(J)$ is $\rho$-maximal with respect to $J$ if
(i) $U$ is an initial set with respect to $J$,

$$ (ii) \quad \rho(J, U) = \rho(J), $$

$$ (iii) \quad \text{if } V \text{ is an initial set with respect to } J, V \subseteq U \text{ and } \rho(J, V) = \rho(J) \text{ then } V = U. $$

In the remainder of this section we develop some of the properties of the rank function $\rho$.

**Lemma 2** Let $J$ be a job and $U, U_1$, and $U_2$ be subsets of $I(J)$ such that $U = U_1 \cup U_2$, $U_1 \cap U_2 = \emptyset$, $U_1 \neq \emptyset$, and $U_2 \neq \emptyset$. Then

$$ \rho(J, U) = \eta \rho(J, U_1) + (1-\eta) \rho(J, U_2) $$

where

$$ \eta = \frac{\tau(J, U_1)}{\tau(J, U)} = 1 - \frac{\tau(J, U_2)}{\tau(J, U)} $$

**Proof:** Straightforward calculation. $\square$
The next lemma relates the rank of certain "subjobs" of a given
job to the rank of the job. We use this result in the next section.

**Lemma 3** Let $U$ be a $\rho$-maximal set with respect to job $J$ and $\ell$ an
index in $U$. Then $\rho(J/K_\ell) \ge \rho(J)$.

**Proof:** If $K_\ell \cap U = U$ then we are done. Otherwise let $U_1 = U - K_\ell$ and $U_2 = K_\ell \cap U$. Applying Lemma 2 we have

$$
\rho(J, U) = \rho(J) = \eta\rho(J, U_1) + (1-\eta)\rho(J, U_2)
$$

where $0 < \eta < 1$. Since $U_1$ is an initial set of $J$ we have $\rho(J, U_1) < \rho(J)$
and therefore $\rho(J, U_2) > \rho(J)$.

Since $\rho(J/K_\ell) \ge \rho(J/U_2, U_2)$, we will be done if we can show that
$\rho(J/U_2, U_2) = \rho(J, U_2)$. But $T_\ell$ is the initial task of $U_2$ and hence

$$
\rho(J/U_2, U_2) = \frac{\sum_{j \in U_2} p_j^I w_j}{\sum_{j \in U_2} p_j^I \tau_j} = \frac{\frac{1}{p_\ell} \sum_{j \in U_2} p_j w_j}{\frac{1}{p_\ell} \sum_{j \in U_2} p_j \tau_j} = \frac{\sum_{j \in U_2} p_j w_j}{\sum_{j \in U_2} p_j \tau_j} = \rho(J, U_2)
$$

where $p_j' = p_j / p_\ell$ is the probability of reaching $T_j$ with respect to
the job $J/U_2$. $\square$
#### IV. Optimal Schedules

Let $\xi$ be a policy and $P = \{J_1, \dots, J_r\}$ be a non-empty scheduling problem. Let $\xi(P)$ choose the initial task of job $J_1$.

We say that $\xi(P)$ is a **Largest Rank assignment** if $\rho(J_1) \ge \rho(J_r)$ for $i=1, \dots, r$. A policy $\xi$ is called an **LR policy** if, for all scheduling problems $P$, $\xi(P)$ is an LR assignment. Schedules produced by the LR policy are called **LR schedules**. We have the following basic result.

**Theorem 1** A policy $\xi$ is optimal if and only if $\xi$ is an LR policy.

*Proof:* A policy $\xi$ is called **n-optimal** if for all policies $\xi'$ and all problems $P$, if $|I(P)| \le n$ then $\overline{mwft}(\xi, P, 0) \le \overline{mwft}(\xi', P, 0)$. A policy $\xi$ is called **n-LR** if, for all problems $P$, if $|I(P)| \le n$ then $\xi(P)$ is an LR assignment. To prove the theorem we show for each $n \ge 1$ that $\xi$ is n-optimal if and only if it is n-LR. The proof is by induction on $n$. The case $n=1$ is obvious.

Let $n \ge 2$ and assume there exists an n-optimal $\xi$ and a scheduling problem $P = \{J_1, \dots, J_r\}$ such that $|I(P)| = n$ and $\xi(P)$ is not an LR assignment. Let $T_1 = \xi(P)$ be the initial task of job $J_1$. By assumption, $r \ge 2$ and there exists an initial task $T_{j_2}$ of job $J_{j_2}$ such that $T_{j_2}$ is an LR assignment with respect to $P$ and $\rho(J_{j_2}) > \rho(J_1)$. Our goal is to obtain a contradiction by constructing $\xi'$ such that $\overline{mwft}(\xi', P, 0) < \overline{mwft}(\xi, P, 0)$.

We describe $\xi$ applied to $P$ by a labeled tree $E$. Each vertex $v$ of $E$ has two labels $T(v)$, a task, and $P(v)$, a nonempty scheduling problem, satisfying $T(v) = \xi(P(v))$. The root of $E$ is $v_0$ and $P(v_0) = P$. Each vertex $v$ in $E$ has one subtree for each nonempty scheduling problem which may result from $P(v)$, given the assignment of the processor to $T(v)$.
In Figure 2 we give a tree which describes a policy as applied to the problem given in Figure 1. This policy we analyzed in a previous section.

If V is a subset of the vertices of E then

$$T(V) = \{T(v) | v \in V\}$$

and

$$I(V) = \{i | v \in V \text{ and } T(v) = T_i\}.$$

Let A be a maximal subset of the vertices of E such that

(i) $v_0$ is in A.

(ii) if $v \in A$, $v \neq v_0$, then the immediate predecessor of v is in A.

(iii) if $v \in A$, then $T(v)$ belongs to $J_{v_1}$.

Clearly, the set A is unique and $I(A)$ is an initial set of $J_{v_1}$.

A vertex v is said to be an immediate successor of a subset V of vertices if v does not belong to V and the immediate predecessor of v is contained in V.

Let $v_1, \dots, v_a$ be the immediate successors of A. And $P_i = P(v_i)$ for $i=1, \dots, a$. Since $|I(P_i)| \le n-1$, we may employ the inductive hypothesis to conclude that the assignments made by $\xi$ in $P_i$ are LR assignments and moreover, we may alter these assignments, as long as they remain LR, without changing the expected mean weighted flow time.

Let $E_i$ be the subtree of E corresponding to $P_i$; the root of $E_i$ is $v_i$ for $i=1, \dots, a$ (see Figure 3). Since all assignments in A are in $J_{v_1}, \rho(J_{v_2})$ has largest rank among all jobs in $P_i$ (there may be ties) for $i=1, \dots, a$. Let U be the $\rho$-maximal set for $J_{v_2}$. Using the inductive hypothesis and Lemma 3, we may take $E_i$ to be of the form shown in Figure 4, where $I(B) = U$. We show no dependency of B on i since, by hypothesis,
<figure><img src="image_3.png" /><figcaption>Figure 2 A Policy Depicted as a Tree</figcaption></figure>
<figure><img src="image_4.png" /><figcaption>Figure 3 ξ Depicted as the Tree E</figcaption></figure>
<figure><img src="image_5.png" /><figcaption>Figure 4 The Structure of Eᵢ</figcaption></figure>
assignments to tasks in $J_{l_2}$ with indices in $U$ are LR assignments.
Therefore, the initial "structure" of $E_i$ can be taken to be $E_B$ for
$i=1,...,a$.

In Figure 5 we show the structure of E and the structure of E' ob-
tained from E by an "interchange". The tree E' describes the policy
ξ' as applied to P. This "interchange" is such that it is easy to cal-
culate the change in the expected mean weighted flow time in going from
ξ to ξ':

$$
\overline{\text{mwft}}(\xi', \underline{P}, 0) = \overline{\text{mwft}}(\xi, \underline{P}, 0) + E\left(s(J_{\underline{l}_2}, I(B))c(J_{\underline{l}_1}, I(A)) - s(J_{\underline{l}_1}, I(A))c(J_{\underline{l}_2}, I(B))\right).
$$

Using the independence of $s(J_{\underline{l}_2}, I(B))$ and $c(J_{\underline{l}_1}, I(A))$ and the indepen-
dence of $s(J_{\underline{l}_1}, I(A))$ and $c(J_{\underline{l}_2}, I(B))$ we obtain

$$
\begin{align*}
\overline{\text{mwft}}(\xi', \underline{P}, 0) &= \overline{\text{mwft}}(\xi, \underline{P}, 0) + \tau(J_{\underline{l}_2}, I(B))w(J_{\underline{l}_1}, I(A)) - \tau(J_{\underline{l}_1}, I(A))w(J_{\underline{l}_2}, I(B)) \\
&= \overline{\text{mwft}}(\xi, \underline{P}, 0) + \gamma(J_{\underline{l}_2}, I(A)) - \rho(J_{\underline{l}_1})
\end{align*}
$$

where $\gamma > 0$.

Since $\rho(J_{\underline{l}_2}) > \rho(J_{\underline{l}_1}) \ge \rho(J_{\underline{l}_1}, I(A))$ we obtain a contradiction.

To finish the proof we must show that if $I(\underline{P}) = n$ then all n-LR
policies for $\underline{P}$ produce the same cost. The above "interchange" argument
can be used to reduce n-LR policies to one another without increasing the
expected value of the mean weighted flow time. We omit the details. $\square$
<figure><img src="image_6.png" /><figcaption>Figure 5 An Interchange</figcaption></figure>
## V. Algorithms

In this section we consider the computational questions which arise when we implement the LR scheduling rule. Algorithm 2 is an LR scheduling algorithm which takes a scheduling problem $P$ as input and determines a sequence of LR assignments and the resultant mean weighted flow time. This algorithm is similar in structure to Algorithm 1; however, here we insure that all assignments are LR.

### Algorithm 2

Input: $P = \{J_1, \dots, J_r\}$

Output: sequence of LR assignments and the mean weighted flow time of the resultant schedule.

Method:

1. **procedure** LR($P$)

2. **begin**

3. $t:=0$;

4. $mwft:=0$;

5. $\ell[i]:=\text{index of the initial task of } J_i$ for $i=1, \dots, r$;

6. **while** not $\ell[i]=0$ for $i=1, \dots, r$ **do**

7. **begin**

8. let $j$ be such that $\ell[j] \neq 0$ and
   $\rho(J_j/K_{\ell[j]}) \ge \rho(J_i/K_{\ell[i]})$ for all $1 \le i \le r$
   and $\ell[i] \ne 0$;

9. $U:= \rho$-maximal set with respect to $J_j/K_{\ell[j]}$;

10. **while** $\ell[j] \in U$ **do**

11. **begin**

12. $(\tau, w, d) := (S_{\ell[j]}, C_{\ell[j]}, D_{\ell[j]});
13. `mwft := mwft + (t+τ)·w;`

14. `t := t+τ;`

15. `l[j] := d`

16. `end`

17. `end;`

18. `return mwft`

19. `end LR`

As in Algorithm 1, $LR(P)$ is a random variable whose outcome is dependent on the choice of $j$ in line 8 and the outcome of the assignment statement in line 12. This random variable is seen to be equal to the mean weighted flow time of the resultant schedule as a comparison of lines 13 and 14 of $LR(P)$ with the "return" statement in procedure `mwft` will show. We let $\overline{LR}(P)$ denote the expected value of $LR(P)$.

**Theorem 2** Let $P$ be a scheduling problem and $\xi$ a policy. Then
$$ \overline{LR}(P) \le \overline{mwft}(\xi, P, 0) $$

*Proof:* This result is an immediate consequence of Theorem 1 and Lemma 3. $\square$

Line 8, in procedure LR, determines a job with largest rank and can be computationally burdensome if no precautions are taken. A similar remark applies to the determination of the $\rho$-maximal set $U$ in line 9. In what follows we give a preprocessing algorithm which, applied to a given job, provides information which may be used to obtain an efficient implementation of lines 8 and 9 in procedure LR.

Let $J$ be a job. We say that a partition $B_1, \dots, B_q$ of $I(J)$ is complete with respect to $J$ if for each $i$ in $\{1, \dots, q\}$ we have
1. $B_i$ contains a unique element, say $\ell$, such that if $T_j$ is a predecessor of $T_\ell$ in $J$ then $j$ is not a member of $B_i$. The index $\ell$ is called the **initial index** of $B_i$,

2. if $j$ is an index in $B_i$ and $j$ is not the initial index of $B_i$ then $j'$ is in $B_i$ where $T_j'$ is the immediate predecessor of $T_j$,

3. if $\ell$ is the initial index of $B_i$ then $B_i$ is a $\rho$-maximal set with respect to $J/K_\ell$.

Since for each $\ell \in \{1,2,...,n\}$ there exists a unique $\rho$-maximal set with respect to $J/K_\ell$, a complete partition with respect to $J$ exists and is unique. The algorithm which follows computes the complete partition of a job.

**Algorithm 3**

Input: $J$ a job

Output: $B_1,...,B_q$ the complete partition with respect to $J$ and numbers $R_1,...,R_q$ such that $R_i = \rho(J/K_\ell)$, where $\ell_i$ is the initial index of $B_i$ for $i=1,...,q$.

Method:

1. **procedure** RANK

2. **begin**

3. $q:=0$;

4. $U:=I(J)$;

5. let $\ell$ be an index in $U$ such that $\rho(K_\ell) \le \rho(K_i)$ for all $i$ in $U$ and $\rho(K_\ell) < \rho(K_j)$ for all $j$ in $K_\ell$ and $j \ne \ell$;

6. $q:=q+1$;

7. $B_q := K_\ell$;

8. $R_q := \rho(K_\ell)$;

9. **while** $U \ne K_\ell$ **do**
10. *begin*

11. $U := U - K_\ell$;

12. let $\ell$ be an index in $U$ such that $\rho(K_\ell \cap U) \le \rho(K_i \cap U)$ for all $i$ in $U$ and $\rho(K_\ell \cap U) < \rho(K_j \cap U)$ for all $j$ in $K_\ell \cap U$ and $j \ne \ell$;

13. $q := q+1$;

14. $B_q := K_\ell \cap U$;

15. $R_q := \rho(K_\ell \cap U)$

16. *end*

17. *end* RANK

**Lemma 4** Let $J$ be a job and $B_1, \dots, B_q$ and $R_1, \dots, R_q$ be the index sets and the numbers, respectively, determined by procedure RANK applied to $J$. Then $B_1, \dots, B_q$ is a complete partition of $J$ and if $\ell$ is the initial index of $B_i$ then $\rho(J/K_{\ell i}) = R_i$.

*Proof:* The details of a proof by induction are routine. We leave them to the reader. $\square$

**Theorem 3** Assume that for each task $T_j$ in $J$ we have the numbers $\tau_j, w_j$, and $\text{Pr}\{D_j=i\}$ for each $i$ such that $T_i$ is an immediate successor of $T_j$. Then an implementation of Algorithm 3 exists which will have an $O(n^2)$ worst-case time complexity, where $n = |I(J)|$.

*Proof:* The idea is to calculate for each $j$ in $I(J)$ the numbers $\tau'_j = p_j \tau_j$ and $w'_j = p_j w_j$. This can be accomplished by a single traversal of the precedence graph of $J$ and takes $O(n)$ time. The minimizations in lines 5 and 12 may also be done using a "bottom-up" traversal of the
precedence graph of $J$; viz.: If $T_j$ is a task with immediate successors $T_{i_1}, \dots, T_{i_k}$, and $\tau(K_{i_\ell})$ and $w(K_{i_\ell})$ are known for $T_{i_\ell}$ for $\ell=1, \dots, k$, then

$$ \rho(K_j) = \frac{w(K_j)}{\tau(K_j)} = \frac{\sum_{\ell=1}^{k} w(K_{i_\ell})}{\tau'_{j} + \sum_{\ell=1}^{k} \tau(K_{i_\ell})} $$

Therefore, if we "visit" tasks $T_{i_1}, \dots, T_{i_k}$ before we visit task $T_j$ we will have accumulated enough information to calculate $\rho(K_j)$ from this (local) information.

Since line 12 is executed $O(n)$ times we obtain a worst-case time complexity of $O(n^2)$ for Algorithm 3. □

The initial computation of the products $p_j w_j$ and $p_j \tau_j$ may be eliminated by recognizing that a cancellation takes place when we compute the ratios $w(K_j)/\tau(K_j)$. The exact cancellation is given by Lemma 3. Thus, if instead of computing $w(K_j)$ and $\tau(K_j)$, we compute $\tilde{w}(K_j) = \frac{1}{p_j} w(K_j)$ and $\tilde{\tau}(K_j) = \frac{1}{p_j} \tau(K_j)$, the ratios would be unaffected, i.e.,

$$ \rho(K_j) = \frac{w(K_j)}{\tau(K_j)} = \frac{\tilde{w}(K_j)}{\tilde{\tau}(K_j)} $$

The point is that $\tilde{w}$ and $\tilde{\tau}$ may be obtained without having to perform the initial computation of $w'_j$ and $\tau'_j$ for each task $T_j$, viz.:

$$ \tilde{w}(K_j) = w_j + \sum_{\ell=1}^{k} \Pr\{D_j = i_\ell\} \tilde{w}(K_{i_\ell}) $$

and

$$ \tilde{\tau}(K_j) = \tau_j + \sum_{\ell=1}^{k} \Pr\{D_j = i_\ell\} \tilde{\tau}(K_{i_\ell}) . $$
We return now to procedure LR and the use of complete partitions in obtaining efficient realizations of the LR scheduling rule. Let $\mathcal{J}$ be a job and $B(\mathcal{J}) = \{(B_1, R_1), \dots, (B_q, R_q)\}$, where $B_1, \dots, B_q$ is a complete partition of $\mathcal{J}$ and $R_i = \rho(\mathcal{J}/K_{\ell_i}) = \rho(B_i)$ where $\ell_i$ is the initial index of $B_i$ for $i=1, \dots, q$.

**Lemma 5** Let $\mathcal{P} = \{\mathcal{J}_1, \dots, \mathcal{J}_r\}$ be a scheduling problem and $\ell_1, \dots, \ell_r$ be the values of the program variables $\ell[1], \dots, \ell[r]$, respectively, just prior to some execution of line 6 in procedure LR applied to $\mathcal{P}$. If $\ell_i \neq 0$ then there exists a $(B, R) \in B(\mathcal{J}_i)$ such that $\ell_i$ is the initial index in $B$ and $\rho(\mathcal{J}_i / K_{\ell_i}) = R$.

**Proof:** The result follows immediately from the uniqueness of complete partitions. $\square$

Lemma 5 guarantees that the information in $B(\mathcal{J}_1), \dots, B(\mathcal{J}_r)$ is relevant; i.e., that it can be used to efficiently implement steps 8 and 9 in procedure LR. In effect, we have precomputed all the ranks and the $\rho$-maximal sets we will ever need during procedure LR($\mathcal{P}$). Clearly, the determination of $j$ in line 8 may be accomplished in constant time if the ranks of the jobs are stored in a priority queue. The management of the priority queue itself can be done in $O(\log_2 r)$ steps per access to the queue [Ah 1]. Therefore, we have

**Theorem 4** Assuming we have $B(\mathcal{J}_1), \dots, B(\mathcal{J}_r)$, the LR scheduling algorithm may be implemented in $O(n \log_2 r)$ time, where $n = |I(\mathcal{P})|$ and $r$ is the number of jobs in $\mathcal{P}$.
The problem of scheduling chains of tasks for which service is
interruptable at task-specific sets of points is considered by Bruno and
Hofri [Br 3]. They show that a "rank" function exists and that optimal
scheduling rules are Shortest Rank rules. It is possible in our model
to represent a task which is interruptable at a finite number of points,
and thus the algorithms developed here can be used to efficiently deter-
mine the "rank" of a chain [Br 3]. For example, suppose task T may be
interrupted after one or two units of service. We represent T in our
model as

<figure><img src="image_7.png" /></figure>
REFERENCES

[Br 1] J. Bruno, E. G. Coffman Jr. and R. Sethi, "Scheduling independent tasks to reduce mean finishing time," *Comm. ACM* 17 (July 1974) 382-387.

[Br 2] J. Bruno, E. G. Coffman Jr. and R. Sethi, "Algorithms for minimizing mean flow time," IFIP Congress 1974, Stockholm, Sweden.

[Br 3] J. Bruno and M. Hofri, "On scheduling chains of jobs on one processor with limited preemptions," submitted for publication *SIAM J. Comput.*

[Co 1] R. W. Conway, W. L. Maxwell, and L. W. Miller, *Theory of Scheduling* Addison-Wesley, Reading, Mass., 1967.

[Ho 1] W. A. Horn, "Single-machine job sequencing with treelike precedence ordering and linear delay penalties," *SIAM J. Appl. Math.* 23, 2 (September 1972) 189-202.

[Si 1] J. E. Sidney, *One-machine sequencing with precedence relations and deferral costs - Parts I and II*, Working paper Nos. 124 and 125, Faculty of Commerce and Business Administration, Univ. of British Columbia (April 1972).