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

HAL
open science

# Scheduling of parallel machines with preemptions

Eugene Lawler, Jacques Labetoulle

► To cite this version:

Eugene Lawler, Jacques Labetoulle. Scheduling of parallel machines with preemptions. [Research Report] IRIA-RR-203, IRIA. 1976, pp.28. hal-04716374

HAL Id: hal-04716374

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

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

SCHEDULING
OF PARALLEL MACHINES
WITH PREEMPTIONS

Eugène LAWLER
Jacques LABETOULLE

Rapport de Recherche N° 203
Décembre 1976
SCHEDULLING OF PARALLEL MACHINES
WITH PREEMPTIONS

E.L. Lawler, J. Labetoulle

IRIA

Abstract :

The general problem considered is that of optimally scheduling n independent jobs on m parallel machines, where there is negligible cost associated with preemption or «job splitting». The problem of minimizing makespan (the completion time of the last job) has previously been solved for the cases of «identical» and «uniform» machines. In this paper, linear programming solution methods are presented for the problems of minimizing maximum lateness on «unrelated» machines, and for minimizing mean completion time on «uniform» machines. As a byproduct of the linear programming formulations of these problems, upper bounds are obtained on the number of preemptions required for optimal schedules. For example, it is shown that there always exists a minimum makespan schedule on unrelated machines with no more than O(m²) preemptions.

Résumé :

Nous étudions le problème de l'ordonnancement optimal de n travaux indépendants sur un ensemble de m processeurs quand le coût de la préemption est négligeable. Le problème de la minimisation de la longueur de l'ordonnancement (date d'achèvement de la dernière tâche) a déjà été résolu dans le cas de processus identiques ou à vitesse proportionnelles (uniform machines). Nous présentons ici une résolution par programmation linéaire des problèmes de minimisation de longueur d'ordonnancement et de minimisation du retard maximum (Maximum lateness) sur des processeurs indépendants ainsi que du problème de minimisation du temps moyen d'achèvement (mean completion time) pour des processus à vitesse proportionnelle. Nous donnons aussi des bornes supérieures sur le nombre de préemptions nécessaires pour réaliser les ordonnancements optimaux. Par exemple, nous montrons que le problème de la longueur de l'ordonnancement peut être résolu avec au plus O(m²) préemptions pour des processus indépendants.
SCHEDULING OF PARALLEL MACHINES

WITH PREEMPTIONS

E.L. Lawler and J. Labetoulle

IRIA

Rocquencourt 78150
France

Abstract :

The general problem considered is that of optimally scheduling n independent jobs on m parallel machines, where there is negligible cost associated with preemption or "job splitting". The problem of minimizing makespan (the completion time of the last job) has previously been solved for the cases of "identical" and "uniform" machines. In this paper, linear programming solution methods are presented for the problems of minimizing makespan and minimizing maximum lateness on "unrelated" machines, and for minimizing mean completion time on "uniform" machines. As a byproduct of the linear programming formulations of these problems, upper bounds are obtained on the number of preemptions required for optimal schedules. For example, it is shown that there always exists a minimum makespan schedule on unrelated machines with no more than O(m²) preemptions.

Résumé :

Nous étudions le problème de l'ordonnancement optimal de n travaux indépendants sur un ensemble de m processeurs quand le coût de la préemption est négligeable. Le problème de la minimisation de la longueur de l'ordonnancement (date d'achèvement de la dernière tâche) a déjà été résolu dans le cas de processus identiques ou à vitesse proportionnelles (uniform machines). Nous présentons ici une résolution par programmation linéaire des problèmes de minimisation de longueur d'ordonnancement et de minimisation du retard maximum (Maximum lateness) sur des processeurs indépendants ainsi que du problème de minimisation du temps moyen d'achèvement (mean completion time) pour des processus à vitesse proportionnelle. Nous donnons aussi des bornes supérieures sur le nombre de préemptions nécessaires pour réaliser les ordonnancements optimaux. Par exemple, nous montrons que le problème de la longueur de l'ordonnancement peut être résolu avec au plus O(m²) préemptions pour des processus indépendants.
# I - INTRODUCTION

The general problem considered in this paper is that of scheduling independent jobs on parallel machines, in an environment in which the cost associated with preemption ("job splitting") is negligible. Linear programming methods of solution are presented for several previously unsolved problems. As a byproduct of the linear programming formulations of these problems, upper bounds are obtained on the number of preemptions required for optimal schedules.

We begin with a few definitions. There are $m$ machines, indexed $i = 1, 2, ..., m$ and $n$ jobs, indexed $j = 1, 2, ..., n$. If job $j$ is processed exclusively by machine $i$, the total amount of time required to complete the job is $p_{ij}$. The processing of a job may be interrupted at any time and resumed at a later time, by the same machine or a different machine. The only restrictions are that a machine can work on only one job at a time, and a job can be worked on by only one machine at a time.

We distinguish three types of machines :

1. If for each $j$, $p_{ij} = p_{kj}$, for all $i, k$, we say that the machines are _identical_.

2. If each $p_{ij}$ can be expressed in the form $p_{ij} = q_i p_j$, where $q_i$ (a "speed factor") and $p_j$ are given parameters associated with machine $i$ and job $j$, we say that the machines are _uniform_.

3. If the $p_{ij}$ values are arbitrary, we say that the machines are _unrelated_.

Unless otherwise stated, we assume that processors are unrelated.

For a given feasible schedule, the last point in time at which job $j$ is processed is its completion time $C_j$. If a _due date_ $d_j$ has been assigned to the job, then its lateness is $L_j = C_j - d_j$.
There are various objectives we may seek to optimize. We may wish to minimize *makespan*, the maximum completion time,

$$C_{\max} = \max_{j} \{C_{j}\},$$

or, more generally, to minimize maximum lateness,

$$L_{\max} = \max_{j} \{L_{j}\}.$$

Or we may seek to minimize the mean completion time, which is equivalent to minimizing $\Sigma C_j$. Or, more generally, we may wish to minimize $\Sigma w_j C_j$, where $w_j$ is a "weight" assigned to job j.

The principal results of this paper are solution methods for the $C_{\max}$ and $L_{\max}$ criteria, and for $\Sigma C_j$, in the case of uniform processors.

## 2 -- KNOWN RESULTS

Let us summarize what is known about optimization with respect to the various objectives defined in the previous section.

The $C_{\max}$ problem can be solved for identical machines by a simple procedure [1] which has been extended to the case of uniform machines [2, 3, 7]. It appears that no solution method has been proposed for unrelated machines. This case is solved by linear programming in Sections 3 and 4.

The $L_{\max}$ problem for identical and uniform machines can be solved by a polynomial-bounded algorithm. Cf. [8]. The $L_{\max}$ problem for unrelated machines is solved by linear programming in Section 6.
Mc Naughton [6] proved that, in the case of identical machines, there is a schedule without preemptions with as small a value of $Σw_j C_j$ as any schedule with a finite number of preemptions. It follows, from Theorem 4 in Section 10 that there is a $Σw_j C_j$ - optimal schedule with no more than $O(m^2n)$ preemptions. Hence the finiteness restriction in Mc Naughton's theorem can be removed.

Two consequences follow from Mc Naughton's theorem :

1. The $ΣC_j$ problem for identical machines can be solved by nonpreemptive scheduling techniques. An optimal nonpreemptive schedule can be found in $O(nlogn)$ time [1].

2. The $Σw_j C_j$ problem is NP-complete, because the nonpreemptive problem is NP-complete, even for identical machines [5].

The nonpreemptive version of the $ΣC_j$ problem can be solved for uniform machines by an efficient polynomial bounded algorithm [1]. However, Mv Naughton's theorem does not apply in this case, as a simple example shows.

Let there be two machines and two jobs, with $q_1 = 1$, $q_2 = 2$, $p_1 = p_2 = 1$. An optimal nonpreemptive schedule is :

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

with $C_1 + C_2 = 3$. An optimal preemptive schedule is :

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

with $C_1 + C_2 = 8/3$.
Our contribution is to provide a linear programming solution for the $\sum C_j$ problem with uniform machines. We leave open the problem of unrelated machines.

We should note that the existence of linear programming solution methods does not resolve the question of NP-completeness for the problems involved. It is possible that better, polynomial-bounded algorithms may be found for the problems, or that the general linear programming problem is itself polynomial bounded. On the other hand, it is possible that the problems may be shown to be NP-complete, which would imply that the general linear programming problems is NP-complete as well. These questions remain open.

## 3 - LINEAR PROGRAMMING FORMULATION OF C_max PROBLEM

Consider any feasible schedule of n jobs on m unrelated machines, where

$\chi_{ij}$ = the total amount of time that machine i works on job j.

It is evident that the values of $C_{max}$ and $\chi_{ij}$ for the schedule constitute a feasible solution to the following linear programming problem :

minimize $C_{max}$

subject to

$$ \sum_{i} \frac{\chi_{ij}}{p_{ij}} = 1, \quad \text{all } j, (1) $$

$$ \sum_{i} \chi_{ij} \le C_{max}, \quad \text{all } j, (2) $$

$$ \sum_{j} \chi_{ij} \le C_{max}, \quad \text{all } i, (3) $$

$$ \chi_{ij} \ge 0. $$
Constraints (1) are satisfied because each job is completed.
Constraints (2) are satisfied because each job is completed by time $C_{max}$. (No job can be worked on by more than one machine at a time.)
Constraints (3) are satisfied because each machine completes its work by time $C_{max}$. (No machine can work on more than one job at a time.)

We assert that the converse is also true. That is, for any feasible solution to the linear programming problem it is possible to construct a feasible schedule with the given values of $C_{max}$ and $x_{ij}$. In the next section we shall describe an algorithm which carries out this construction in a polynomial-bounded number of steps.

It follows that the $C_{max}$ problem for unrelated machines can be solved by obtaining an optimal solution to the linear programming problem. The structure of this latter problem suggests specialized computational techniques. For example, the problem can be reduced to a relatively simple network flow problem by assigning Lagrange multipliers to the constraints (1). Or, if it can be verified that the optimal value of $C_{max}$ is at least as great as the maximum of the $p_{ij}$ values, the constraints (2) can be dispensed with, thereby obtaining a transportation problem with "gains" in the arcs. However, for our purposes it is sufficient to observe that the linear programming problem can be solved, at least in principle, by the simplex method.

## 4 - CONSTRUCTION OF FEASIBLE SOLUTION

We shall now demonstrate that it is possible to construct a feasible schedule from any feasible solution to the linear programming problem posed in the previous section.

Suppose $C_{max}$, $X = (x_{ij}) \ge 0$ satisfy constraints (2) and (3). Call row i (column j) of matrix X *tight* if $\sum_{j} x_{ij} = C_{max}$ ($\sum_{i} x_{ij} = C_{max}$), and *slack* otherwise.
Now suppose we can find a subset of strictly positive elements of X, with exactly one element of the subset in each tight row and in each tight column, and no more than one element in each slack row and in each slack column. We shall call such a subset of elements a _decrementing set_, and use it to construct a _partial schedule_ of length $δ$, for some $δ > 0$.

For example, suppose $C_{max} = 11$ and

$$X = \begin{pmatrix} 3 & \textcircled{4} & 0 & 4 & 11 \\ \textcircled{4} & 0 & 6 & 0 & 10 \\ 4 & 0 & 0 & \textcircled{6} & 10 \\ 11 & 4 & 6 & 10 \end{pmatrix}$$

with row and column sums as indicated on the margins of the matrix. Note that row 1 and column 1 are tight. One possible decrementing set is indicated by the encircled elements.

We propose to construct a partial schedule in which processor i works on job j for $min\{\chi_{ij}, \delta\}$ units of time, for each element $\chi_{ij}$ in the decrementing set. We shall then replace $\chi_{ij}$ by $max\{0, \chi_{ij} - \delta\}$, for each element in the decrementing set, thereby obtaining a new matrix $X'$ which satisfies constraints (2) and (3) with respect to $C'_{max} = C_{max} - \delta$.

There are various constraints that must be satisfied by $δ$ in order for this strategy to be effective. If $\chi_{ij}$ is an element of the decrementing set in a tight row or column, then clearly it is necessary that $δ \le \chi_{ij}$, else there will be a row or column sum in the matrix $X'$ which is strictly greater than $C_{max} - \delta$. Similarly, if $\chi_{ij}$ is an element of the decrementing set in a slack row (slack column), then it is necessary that

$$\begin{aligned} \delta &\le \chi_{ij} + C_{max} - \sum_{k} \chi_{ik} \\ (\delta &\le \chi_{ij} + C_{max} - \sum_{k} \chi_{kj}) . \end{aligned}$$
And if row i (column j) contains no element of the decrementing set (and is therefore necessarily slack), it is necessary that

$$ \delta \leq C_{\max} - \sum_{j} \chi_{ij} $$

$$ (\delta \leq C_{\max} - \sum_{i} \chi_{ij}). $$

Thus, for the example, we have

$$ \delta \leq \chi_{12} = 4, $$

$$ \delta \leq \chi_{21} = 4, $$

$$ \delta \leq \chi_{34} + C_{\max} - \sum_{j} \chi_{3j} = 7, $$

$$ \delta \leq \chi_{34} + C_{\max} - \sum_{i} \chi_{i4} = 7, $$

$$ \delta \leq C_{\max} - \sum \chi_{i3} = 5 $$

Choosing $\delta = 4$, we obtain $C'_{\max} = 7$ and $X'$, as shown below, with the partial schedule indicated to the right :

$$ X' = \begin{pmatrix} \textcircled{2} \\ \textcircled{3} \\ \textcircled{0} \\ \textcircled{0} \\ \textcircled{0} \\ \textcircled{4} \\ \textcircled{0} \\ \textcircled{0} \\ \textcircled{6} \\ \textcircled{0} \\ \textcircled{2} \\ \textcircled{0} \\ \textcircled{6} \\ \textcircled{6} \\ \textcircled{6} \end{pmatrix} $$

A new decrementing set is indicated by the encircled entries in $X'$. Choosing $\delta = 3$, we obtain $C''_{\max} = 4$ and $X''$, as shown below :

$$ X'' = \begin{pmatrix} \textcircled{0} & \textcircled{0} & \textcircled{0} & \textcircled{4} \\ \textcircled{0} & \textcircled{0} & \textcircled{3} & \textcircled{0} \\ \textcircled{4} & \textcircled{0} & \textcircled{0} & \textcircled{0} \\ \textcircled{4} & \textcircled{0} & \textcircled{3} & \textcircled{4} \end{pmatrix} $$

A final decrementing set yields the complete schedule :
<table><tr><td>2</td><td>1</td><td>4</td></tr><tr><td>1</td><td>3</td><td>3</td></tr><tr><td>4</td><td>4</td><td>1</td></tr></table>

4 6 7 10 11

Note that the choice of $X_{34}$ in the second decrementing set and $X_{23}$ in the third and final decrementing sets resulted in the scheduling of idle time on processors 3 and 2 respectively.

For each decrementing set, $\delta$ can be chosen such that either one of the positive entries in the X matrix is reduced to zero, or else one more of the rows or columns becomes tight. Neither of these events can occur more than a finite number of times. Hence finite termination of the schedule construction procedure is assured, provided we can demonstrate the existence of a decrementing set for any feasible solution to the inequalities (2) and (3).

**Lemma 1** : There exists a decrementing set for any feasible solution to inequalities (2) and (3) for which $C_{max} > 0$.

**Proof** : From the $m \times n$ matrix X construct an $(m+n) \times (m+n)$ matrix Y, as indicated below :

$$ Y = \left( \begin{array}{c|c} X & D_m \\ \hline D_n & X^T \end{array} \right). $$

Here $D_m$ and $D_n$ are $m \times m$ and $n \times n$ diagonal matrices of nonnegative "slacks", determined in such a way that each row sum and column sum of Y is equal to $C_{max}$. It follows that $\frac{1}{C_{max}}$ Y is a
doubly stochastic matrix. The well-known Birkkoff-von Neumann theorem asserts that a doubly stochastic matrix is a convex combination of permutation matrices. It is easily verified that any one of the permutation matrices in such a convex combination is identified with a decrementing set of X. ■

There are several ways in which a decrementing set can be found. One way is to construct a flow network on $m + n$ nodes as shown in Figure 1. There is an arc from a "row" node i to a "column" node j if and only if $\chi_{ij} > 0$. A lower bound of unity is placed on the flow through all arcs from the source node to "tight" row nodes and on all arcs from "tight" column nodes to the sink. Lower bounds on flow are zero for all other arcs. Flow capacities are set to unity for all arcs. It is asserted that for every integral feasible flow in this network there is a corresponding decrementing set and conversely.

Feasible flows, and hence decrementing sets, can be determined in time polynomial in m and n. The number of decrementing sets required to construct a feasible schedule is also bounded by a polynomial in m and n. It follows that a schedule can be constructed in polynomial time from any feasible solution to the linear programming problem. However, there appears to be little prospect for finding a polynomial algorithm for solving the linear programming problem. (It is possible that there is a different method for solving the scheduling problem which is polynomial bounded.)

<figure><img src="image_6.png" /><figcaption>Figure 1</figcaption></figure>
5 - BOUNDS ON THE NUMBER OF PREEMPTIONS

In the case of identical processors, it is always possible
to construct a $C_{max}$ - optimal schedule with no more than m-1 preemptions.
Moreover, there is a class of problems for which m-1 preemptions are
necessary [7]. We now seek to establish similar results for unrelated
processors.

To be precise, let us say that a job is _preempted_ at time T if execution of the job is suspended on some processor at time T before its completion. If a job begins execution on processor i at time t and its processing is suspended at time t', then [t, t'] is called an _active period_ for the job on processor i. The total number of preemptions is equal to the total number of active periods in excess of n.

Now consider the linear programming problem posed in Section 3.
This problem has 2n + m linear constraints. It follows from elementary
linear programming theory that there exists an optimal basic feasible
solution with no more than 2n + m strictly positive variables. In fact,
there is an optimal basic feasible solution with no more than n + t₂ + t₃
strictly positive variables, where t₂ and t₃ are the number of inequality
constraints of type (2) and type (3) which are satisfied with strict
equality. But 1 ≤ t₃ ≤ m and, if n > m, 0 ≤ t₂ ≤ m-1. Hence there is
an optimal solution with no more than n + 2m-1 strictly positive variables,
one of which is $C_{max}$.

Thus, if $n > m$, there exists an optimal solution to the linear
program with no more than $n + 2m - 2$ strictly positive $\chi_{ij}$ values. If we
could construct a schedule (with the same value of $C_{max}$) in which each
of the positive $\chi_{ij}$ values was in one-to-one correspondence with an
active period, then we could establish an upper bound of $2m - 2$ on the
number of preemptions required for a $C_{max}$ - optimal schedule. However, the
schedule-construction generally introduces a number of additional
preemptions. We must now establish an upper bound on this number.
We shall propose a variation of the schedule construction procedure, with the objective of reducing the number of preemptions in the resulting schedule. (This variation also happens to admit a better polynomial bound on its running time, but this is not our principal concern here.) What we shall do is to replace all of the jobs which are represented by a single positive $\chi_{ij}$ value by m dummy jobs. We shall then apply the schedule construction procedure to find a feasible schedule with these dummy jobs. Finally, we shall create a schedule for the original set of jobs by reassigning the active periods for the dummy jobs to the jobs which they replaced.

Consider the example from the previous section where $C_{max} = 11$ and

$$X = \begin{pmatrix} 3 & 4 & 0 & 4 \\ 4 & 0 & 6 & 0 \\ 4 & 0 & 0 & 6 \\ 11 & 4 & 6 & 10 \end{pmatrix} \quad 11, 10, 10$$

(This is actually not a basic feasible solution to the linear program, but this is of no consequence). Let us remove the columns containing one strictly positive $\chi_{ij}$ value and add dummy columns, to obtain the matrix $X'$:

$$X' = \begin{pmatrix} 3 & 4 & 4 & 0 & 0 \\ 4 & 0 & 0 & 7 & 0 \\ 4 & 6 & 0 & 0 & 1 \\ 11 & 10 & 4 & 7 & 1 \end{pmatrix} \quad 11, 11, 11$$

The indices of the jobs identified with the first two columns of $X'$ are 1 and 4. Let us assign indices 1', 2', 3' to the dummy jobs.
Note that we have given the dummy jobs $X_{ij}$ values so that all rows of $X'$ are tight.

The schedule construction procedure applied to $X'$ yields as a schedule :

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

We now fill in the active periods for the dummy jobs with active periods for the jobs which they replaced, plus idle time, obtaining the same schedule as we happened to obtain by the original procedure :

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

In the case of this example, a schedule was constructed for the matrix $X'$ in which there were no preemptions of the dummy jobs. Hence it was possible to create a schedule for the original set of jobs in which there were no preemptions of any of the jobs which the dummy jobs replaced. In general, the number of preemptions required for the original set of jobs is bounded by the number of preemptions in the schedule constructed for the matrix $X'$.
The matrix X' has $t+m$ columns, where $t$ is the number of columns identified with nondummy jobs, and at most $t+t_2+t_3+m-1$ strictly positive elements. The number of preemptions required is bounded by the number of active periods in a schedule constructed for $X'$ in excess of $t+m$. Each iteration of the schedule construction procedure introduces at most $m$ active periods. Hence we may obtain a bound on the number of active periods by bounding the number of iterations.

Each iteration of the schedule construction procedure either reduces an element of the $X'$ matrix to zero, or causes an additional column to become tight. Exactly $m$ elements become zero at the last iteration. Hence there are at most $t+t_2+t_3$ iterations of the first kind. There are $m-t_2$ iterations of the second kind, and hence no more and hence no more than $t+t_3+m$ iterations in all.

We can reduce the upper bound on the number of iterations by $m$, by the following observations. We may assume that no column identified with a dummy job is tight. If such a column exists, the problem can be reduced to one involving $m-1$ processors. Before the last iteration, there are exactly $m$ tight columns. For each of these columns, either it was tight at the beginning (corresponding then to a nondummy job which must be executed on at least two processors) or it became tight at the end of a previous iteration.

If a column becomes tight and there exists exactly one positive element in the $X'$ matrix in that column, then at least one element of the $X'$ matrix was reduced to zero at that iteration. If that is not the case, then there exists a stage at which the column is tight and there are at least two positive elements in the column. At some later iteration, when the number of positive elements in the column is reduced to one, at least two positive elements are reduced to zero simultaneously. This indicates that we have overestimated the total number of iterations by at least $m$.

It follows that the total number of preemptions is bounded by $m(t+t_3)-(t+m)$. But $t \le t_2+t_3-1$, $t_2 \le m$, $t_3 \le m-1$. Hence we have proved the following theorem.
**Theorem 2** : An upper bound on the number of preemptions required for a $C_{max}$ - optimal schedule on unrelated processors is $3m^2 - 5m + 2$, if $n > m$.

This result contrasts with that of Gonzalez and Sahni [ 2 ] who showed that $2(m-1)$ is a tight upper bound for the case of *uniform* processors. We have not been able to establish the tightness of our upper bound, or even to show that $O(m^2)$ preemptions are necessary for an optimal schedule.

## 6 - THE $L_{max}$ PROBLEM

Assume that the jobs are numbered in nondecreasing due date order, i.e. $d_1 \le d_2 \le \dots \le d_n$. Let

$\chi_{ij}^{(1)}$ = the total amount of time that machine i works on job j in the time period $[0, d_1 + L_{max}]$,

and, for $k = 2, 3, \dots, n$, let

$\chi_{ij}^{(k)}$ = the total amount of time that machine i works on job j in the time period $[d_{k-1} + L_{max}, d_k + L_{max}]$.

We may now pose the following linear programming problem for the $L_{max}$ problem on unrelated machines :

minimize $L_{max}$

subject to

$$ \sum_{i} \sum_{k=1}^{j} \frac{\chi_{ij}^{(k)}}{p_{ij}} = 1, \quad \text{all } j, $$
$$ \sum_{i} \chi_{ij}^{(1)} \le d_1 + L_{\max}, \quad \text{all } j, $$

$$ \sum_{j} \chi_{ij}^{(1)} \le d_1 + L_{\max}, \quad \text{all } i, $$

$$ \sum_{i} \chi_{ij}^{(k)} \le d_k - d_{k-1}, \quad k = 2, 3, \dots, m; \quad j \ge k, $$

$$ \sum_{j} \chi_{ij}^{(k)} \le d_k - d_{k-1}, \quad k = 2, 3, \dots, m; \quad \text{all } i, $$

$$ \chi_{ij}^{(k)} \ge 0. $$

Given an optimal solution to this linear programming problem, an $L_{\max}$-optimal schedule can be constructed by applying the schedule construction procedure of Section 4 to matrix $X^{(k)} = (\chi_{ij}^{(k)}),$ for each $k = 1, 2, \dots, m$. An upper bound on the number of preemptions is given in Section 10.

## 7 - GENERALIZATIONS OF $L_{\max}$ PROBLEM

We shall now consider more general minmax objectives than $L_{\max}$, and also the question of release dates.

Suppose, instead of lateness, we wish to minimize

$$ f_{\max} = \max_{j} \{f_{j}(c_{j})\}, $$

where each $f_j$ is a monotone nondecreasing, but otherwise arbitrary, cost function associated with job j. We can solve this more general scheduling problem by carrying out a binary search on the optimal value of $f_{\max}$. For each trial value, deadlines are induced for the jobs in an obvious way. That is, for a trial value of y, the deadline assigned to job j is

$$ d_j = \sup\{t | f_j(t) \le y\}. $$
One then solves the linear programming problem of the previous section with respect to the $d_j$ values. If $L_{max} = 0$, then the trial value is optimal. If $L_{max} < 0$, the trial value is too small, and if $L_{max} > 0$ the trial value is too large.

The binary search can be organized in such a way that the number of trial values for $f_{max}$, and hence the number of linear programming problems which must be solved, is proportional to the number of significant digits of accuracy desired in the optimum value of $f_{max}$.

Suppose that job j cannot be processed prior to its release date $r_j \ge 0$. (Until now, we have assumed that each job is available for processing at time $t=0$). The $f_{max}$ problem with release dates can be solved by a binary search procedure similar to that described above. There are $2n$ distinct time periods defined by the union of the release dates and the deadlines imputed to the jobs for each trial value of $f_{max}$. Hence there is a set of variables $\chi_{ij}^{(k)}$ for each of these time periods, with $k = 1, 2, ..., 2n$. The variable $\chi_{ij}^{(k)}$ is permitted to the nonzero only if job j can be processed during time period k.

## 8 - THE $\sum C_j$ PROBLEM

In order to obtain a linear programming formulation for the $\sum C_j$ problem with uniform processors, we wish to establish that there exists an optimal schedule in which completion times are in processing time order, i.e. $p_i < p_j$ implies $C_i \le C_j$. Since we are able to obtain the desired result for the $\sum w_j C_j$ problem in the special case of "agreeable" weighting, i.e. $p_i < p_j$ implies $w_i \ge w_j$, we shall do so.

**Theorem 3** : If the weighting of jobs is agreeable, there exists a schedule minimizing $\sum w_j C_j$ on uniform processors for which $p_i < p_j$ implies $C_i \le C_j$.
**Proof** : Suppose there is an optimal schedule for which $C_i < C_j$, but $p_i > p_j$. A schematic representation of such a schedule is :

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

We propose to systematically interchange some fraction of the processing of i and j before $C_i$, so as to obtain the following schedule :

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

Let $X_i, X_j$ denote the total amount of time i and j are processed before $C_i$ in the original schedule, with effective (mean) processing rates $R_i$ and $R_j$. Let $Y_j$ denote the total amount of time j is processed between $C_i$ and $C_j$, with effective rate $S_j$. Then we have :

$$ (4) \quad R_j X_j + S_j Y_j = p_j < p_i = R_i X_i. $$

After modification of the schedule we must have :

$$ R_j(1-\lambda)X_j + R_i\lambda X_i = p_j $$

$$ R_i(1-\lambda)X_i + R_j\lambda X_j + S_j Y_j = p_i. $$

Solving for $\lambda$, we find

$$ \lambda = \frac{S_j Y_j}{R_i X_i - R_j X_j} $$
From (4), $R_i X_i - R_j X_j > S_j Y_j \ge 0$. Hence $0 \le \lambda < 1$, and such a modification of the schedule is possible.

Because the weighting of jobs is agreeable, the modification of the schedule does not increase the value of $\sum w_j C_j$. A finite number of such modifications yields an optimal schedule satisfying the conditions of the theorem. ■

It is now easy to formulate a linear program for the problem of minimizing $\sum w_j C_j$ on uniform processors, in the case that the weighting of jobs is agreeable. Let us assume that the jobs are numbered in processing time order, i.e. $p_1 \le p_2 \le \dots \le p_n$ and that also $w_1 \le w_2 \le \dots \le w_n$. Then we seek to

$$ \text{minimize} \quad \sum_{j=1}^{n} w_j C_j $$

subject to

$$ \sum_{i=1}^{m} \sum_{K=1}^{j} \frac{\chi_{ij}^{(k)}}{q_i p_j} = 1, \quad \text{all } j, $$

$$ \sum_{i=1}^{m} \chi_{ij}^{(k)} \le C_k - C_{k-1}, \quad \text{all } k, j \le k, $$

$$ \sum_{j=1}^{K} \chi_{ij}^{(k)} \le C_k - C_{k-1}, \quad \text{all } i, k $$

$$ \chi_{ij}^{(k)} \ge 0, $$

where $C_0 = 0$, by definition.
An optimal schedule can be constructed from an optimal solution to this linear programming problem by the previously described techniques.

## 9 - THE COST OF PROCESSING

The linear programming formulations we have obtained suggest that we might include a "cost of processing" in the objective functions for these problems. Let

$c_{ij}$ = the cost of processing job j on processor i for one unit of time.

Then, for example, rather than only minimizing $L_{max}$, we may choose to minimize

$$L_{max} + \sum_{i} \sum_{j} c_{ij} x_{ij}.$$

It is a well-known fact that the convex combination of any two feasible solutions to a linear programming problem is also a feasible solution. Thus, if $L_{max}$, $X^{(1)}$ and $L_{max}$, $X^{(2)}$, are feasible solutions, then so is $\lambda L_{max}^{(1)} + (1-\lambda)L_{max}^{(2)}$, $\lambda X^{(1)} + (1-\lambda)X^{(2)}$, for any $\lambda$, $0 \le \lambda \le 1$.

Let us say that $(C, L)$ is a *feasible pair* of values if there exists a feasible schedule for which

$$\sum_{i} \sum_{j} c_{ij} x_{ij} \le C$$

$$L_{max} \le L.$$

The preceding remarks about convexity indicate that the feasible points $(C, L)$ form a convex region in the plane, as indicated in Figure 2.
Let $L(C)$ denote the minimum altainable value of $L_{max}$, over all schedules with cost of processing not exceeding $C$. Then it follows from the preceding observations that $L$ is a convex function of $C$.

<figure><img src="image_11.png" /><figcaption>Figure 2</figcaption></figure>
However, these convexity results do not hold for many other problems. For example, it is not hard to construct counterexamples for the $L_{max}$ problem with release dates, the general $f_{max}$ problem without release dates, and even for the $\sum C_j$ problem.

It will be recalled that the $L_{max}$ problem with release dates and the $f_{max}$ problem were solved with a sequence of linear programming problems. The lack of convexity properties for these problems suggests that there is no single linear programming problem which can be formulated for these scheduling problems - at least there is no such problem with only $L_{max}$ of $f_{max}$ and $\chi_{ij}$ (or $\chi_{ij}^{(k)}$) as variables.

The $\sum C_j$ problem for uniform processors was solved with a single linear programming problem. But here it was shown to be possible to number the jobs so that $C_1 \le C_2 \le \dots \le C_n$. It is possible to devise a simple example with $m=2$ and $n=2$, such that a schedule with minimum total completion time requires $C_1 < C_2$, but a schedule with minimum cost of processing requires $C_1 > C_2$. (This is left to the reader.) Such an example can be made to yield the desired nonconvexity result. This suggests that there is no way to formulate the $\sum C_j$ problem as a linear programming problem -with only $C_j$ and $\chi_{ij}$ as variables- without fixing an order on the completion times, as we have done in Theorem 3.

## 10 - A GENERAL BOUND ON THE NUMBER OF PREEMPTIONS

We shall now obtain an upper bound on the number of preemptions required for an optimal schedule, with respect to a very broad class of optimization criteria. Specifically, we suppose that we wish to find a schedule which minimizes

$$f(C_1, C_2, \dots, C_n) + \sum_i \sum_j c_{ij} \chi_{ij}$$

where $f$ is a monotone nondecreasing, but otherwise arbitrary, function of the completion times of the jobs, and $c_{ij}$ is defined as in the previous section.
Suppose there is an optimal schedule with completion times $C_1^*, C_2^*, \dots, C_n^*$. We can let these completion times assume the roles of deadlines and solve a linear programming problem of the form described in Section 7. The schedule-construction procedure can then be applied to obtain an optimal schedule for which we can bound the number of preemptions as follows.

The number of strictly positive elements in the maxtrix $X^{(k)} = (\chi_{ij}^{(k)})$ can be bounded by $t_1^{(k)} + t_2^{(k)} + t_3^{(k)}$, where $t_1^{(k)}$ is the number of positive variables attributable to the inequality constraints of the form

$$ \sum_k \sum_i \frac{\chi_{ij}^{(k)}}{p_{ij}} = 1, $$

$t_2^{(k)}$ is the number of tight constraints of the form

$$ \sum_i \chi_{ij}^{(k)} \le d_k - d_{k-1}, $$

and $t_3^{(k)}$ is the number of tight constraints of the form

$$ \sum_j \chi_{ij}^{(k)} \le d_k - d_{k-1}. $$

The total number of active periods resulting from $X^{(k)}$ is bounded by

$$ m t_1^{(k)} + 2m^2. $$

But $\sum_k t_1^{(k)} = n$. Hence the total number of active periods in the resulting schedule is bounded by $2m^2n + mn$, and the number of preemptions is bounded by $(2m^2 + m-1)n$. Hence we have proved the following theorem.
<figure><img src="image_12.png" /></figure>
**Theorem 4** : For any monotone nondecreasing function f and coefficients $c_{i,j}$, there exists an optimal schedule with no more than $(2m^2 + m-1)n$ preemptions.

This result is in contrast with Theorem 2, which asserts that the number of preemptions required for a $C_{max}$ - optimal schedule is independent of n. We can show that at least $O(n)$ preemptions are required in this more general case, as indicated by the following theorem.

**Theorem 5** : At least $(m-1)n/m+1$ preemptions are required for an $L_{max}$ - optimal schedule on identical processors.

*Proof* : It is well-known that at least $m-1$ preemptions are required for $C_{max}$ - optimal schedule on identical processors, for $m+1$ jobs, each with processing time $m$ [7]. The optimal value of $C_{max}$ in this case is $m+1$.

This suggests that we construct an $L_{max}$ problem with $n = k(m+1)$ jobs, each with processing time $m$. The first $m+1$ jobs are given deadline $m+1$, the second $m+1$ jobs are given deadline $2(m+1)$, and so on. It is not hard to see that an $L_{max}$ - optimal schedule (with $L_{max} = 0$), requires at least $k(m-1)$ preemptions. ■

Theorem 5 can easily be generalized to the case in which we seek to minimize

$$f(S_1, S_2, \dots, S_n, C_1, C_2, \dots, C_n) + \sum_i \sum_j c_{ij}x_{ij}$$

where f is monotone nonincreasing in the starting times $S_1, S_2, \dots, S_n$ and monotone nondecreasing in the completion times $C_1, C_2, \dots, C_n$. We leave details to the reader.
REFERENCES

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

[2] T. Gonzalez and S. Sahni, "Preemptive Scheduling of Uniform Processor Systems", Technical Report 76-5, Computer Science Dept., Univ. of Minn., May 1976.

[3] E.C. Horvath, S. Lam and R. Sethi, "A Level Algorithm for Preemptive Scheduling", Technical Report, Computer Science Dept., Penn. State Univ., 1976.

[4] J. Labetoulle, "Real Time Scheduling in a Multiprocessor Environment", submitted for publication.

[5] J.K. Lenstra, A.H.G. Rininooy Kan and P. Brucker, "Complexity of Machine Scheduling Problems", to appear in *Annals of Discrete Mathematics*.

[6] R. McNaughton, "Sequencing with Deadlines and Loss Functions", *Management Science*, 6 (1959), 1-12.

[7] R. Sethi, "Algorithms for Minimal-Length Schedules", Chap. 2 in *Computer and Job-Shop Scheduling Theory*, E.G. Coffman, ed., John Wiley N.Y., 1976.

[8] H.I. Stern, "Minimizing Makespan for Independent Jobs on Nonidentical Parallel Machines - An Optimal Procedure", Technical Report, Dept. of Industrial Eng. and Mgt., Ben-Gurion Univ. of the Negev, Beer-Sheva, Israel, March 1976.