IRIA
laboria

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

ARCHIVES

# ORDON
A scheduling algorithm
for real time tasks
on non-preemptive resources
with deadline

A.Jorry

Rapport de Recherche n° 64

avril 1974
# ORDON
A SCHEDULING ALGORITHM FOR REAL TIME TASKS
ON NON-PREEMPTIVE RESOURCES WITH DEADLINE

A. Jorry

Présenté par M. Depeyrot

## Résumé :

Notre but est de définir des méthodes de génération de plannings pour les problèmes d'ordonnancement, telles qu'à tout instant de la génération, l'on puisse décider à la fois de l'heure d'exécution, et de la machine qui exécutera le travail.

Nous partons du cas général et d'un article de Linus Shrage [SHR 70], et montrons que pour le cas où les machines sont réparties en classes distinctes, (cas de la généralisation 2, dans l'article de Shrage) une telle méthode existe, (Smallest Hole Policy, ou SHP).

Cette démonstration se fait en deux temps :

1) Nous donnons la version des théorèmes 2,3,4 de Shrage, et de leurs preuves, qui correspond à la SHP.

2) Nous démontrons que tout planning optimal (active schedule) est généré une fois et une seule.

Ensuite, nous donnons une méthode de résolution pour un autre cas du problème d'ordonnancement.

## Abstract :

Considering the Job-shop scheduling problem, our aim, is to define schedule generation methods,such that at each step of the generation, we may decide of the start time of a task, and of the unit that will execute it.
Starting from the general case, and from a paper by Linus Shrage
[SHR 70], we show that, when units are classified into mutually exclusive
sets, (treated as generalization 2 by Shrage) such a method exists (Smallest
Hole Policy or SHP).

The proof is done in two steps :

1) We first give the SHP version of theorems 2,3,4 of Shrage, and their proof.

2) We prove we generate once, and only once all active schedules.

We then give a resolution method for another case of the scheduling
problem.
CONTENTS

<table><tr><td>List of figures</td><td>iv</td></tr><tr><td>List of theorems</td><td>v</td></tr><tr><td>I. INTRODUCTION.</td><td>1</td></tr><tr><td>II. THE PROBLEM.</td><td>4</td></tr><tr><td>III. PRELIMINARY DEFINITIONS.</td><td>8</td></tr><tr><td>IV. THE SCHEDULING ALGORITHM.</td><td>8</td></tr><tr><td>IV.1. The study.</td><td>8</td></tr><tr><td>IV.2. The aim.</td><td>8</td></tr><tr><td>IV.3. The algorithm.</td><td>12</td></tr><tr><td>IV.3.1. Notations.</td><td>13</td></tr><tr><td>IV.3.2. A primary version of ORDON.</td><td>15</td></tr><tr><td>IV.3.3. Two straight forward properties.</td><td>17</td></tr><tr><td>IV.3.4. Specification of the SCHEDULE and CHOOSE primitives.</td><td>17</td></tr><tr><td>IV.3.5. A first set of Theorems.</td><td>21</td></tr><tr><td>IV.4. The problem of delayed requests.</td><td>36</td></tr><tr><td>IV.4.1. Partitionning tasks.</td><td>36</td></tr><tr><td>IV.4.2. Deadlock problem.</td><td>39</td></tr><tr><td>IV.4.3. Back track.</td><td>40</td></tr><tr><td>V. CONCLUSION.</td><td>43</td></tr><tr><td>BIBLIOGRAPHY.</td><td>48</td></tr></table>

Key words : SCHEDULING, MANUFACTURING, PROCESS CONTROL, RESOURCE ALLOCATION, REAL-TIME, OPERATING SYSTEM, PLANT AUTOMATION.
LIST OF FIGURES.

<table><tr><td>Figure 1 : Gantt Chart.</td><td>4</td></tr><tr><td>Figure 2 : The two ways of generation.</td><td>10-11</td></tr><tr><td>Figure 3 : The Smallest Hole Policy (SHP).</td><td>18</td></tr><tr><td>Figure 4 : Occupation diagrams when using no delayed requests.</td><td>36</td></tr><tr><td>Figure 5 : Occupation diagrams when using delayed requests.</td><td>36</td></tr><tr><td>Figure 6 : The use of idle periods.</td><td>36</td></tr><tr><td>and 6 bis</td><td></td></tr><tr><td>Figure 7 : Partitionning tasks.</td><td>38</td></tr></table>
List of Theorems.

<table><tr><td>LEMMA 1.</td><td>Primary justification of the SHP.</td><td>19</td></tr><tr><td>LEMMA 2.</td><td>Redundance, part 1.</td><td>21</td></tr><tr><td>LEMMA 3.</td><td>Redundance, part 2.</td><td>22</td></tr><tr><td>LEMMA 4.</td><td>Uniqueness, part 1.</td><td>26</td></tr><tr><td>LEMMA 5.</td><td>Uniqueness part 2.</td><td>26</td></tr><tr><td>LEMMA 6.</td><td>Activity, part 1.</td><td>28</td></tr><tr><td>LEMMA 7.</td><td>Activity, part 2.</td><td>30</td></tr><tr><td>LEMMA 8.</td><td>Inserting idle periods, part 1.</td><td>37</td></tr><tr><td>LEMMA 9.</td><td>Inserting idle periods, part 2.</td><td>37</td></tr><tr><td>LEMMA 10.</td><td>Backtracking.</td><td>41</td></tr><tr><td>PROPERTY 1.</td><td>Discarding property.</td><td>25</td></tr><tr><td>PROPERTY 2.</td><td>Uniqueness property.</td><td>28</td></tr><tr><td>PROPERTY 3.</td><td>Activity property.</td><td>33</td></tr><tr><td>THEOREM 1.</td><td>Redundance.</td><td>25</td></tr><tr><td>THEOREM 2.</td><td>Uniqueness.</td><td>27</td></tr><tr><td>THEOREM 3.</td><td>Activity.</td><td>33</td></tr></table>
The problem of scheduling *m* completely independent tasks on *n* resources (known as the *m × n* sequencing problem) is a highly combinatorial one.

Depending on : whether some or all the resources are identical,

whether this identity holds for any task, or depends on the

kind of tasks ;

on : the number of resources a task may request,

on : the number of tasks that can be processed on the same resource
at the same time.

.....

the number of possible schedules can take any value between 1 and $(2^{m*n})^J$, i.e.

1 when $n \ge m$, and each task requires a different machine,

$(2^{m*n})^J$ when each task is processed on each machine, with a different order and speed, $J$ being the **number of time units** needed to execute sequentially all the tasks, in the worst case.

The number of schedules for non sharable, non preemptive machines,
with least idle time, with constant speed is equal to $P_\tau$ :

$$
\text{such that } P_{\tau} = \sum_{i=1}^{||\tau||} P_{\tau, i} \quad \text{if } ||\tau|| = 0, P_{\tau} = 1
$$

$$
P_{\tau,i} = \left\{ \prod_{j=1}^{||N/E_i||} \begin{cases} w(i,j) \\ ||c(i,j)|| \end{cases} \right\} \times P_{\tau-\{i\}}
$$

Where :

i : the i-th element of the set of tasks $\tilde{C}$.

$N/E_i$: the set of equivalence classes defined by $i$ on the set of machines,

(Machines *m* and *m'* are equivalent iff they can perform the
same task : $m \equiv_{E_i} m'$).
$C(i,j)$ : the $j^{th}$ equivalence class defined by i on the set of machines.

$W(i,j)$ : the number of machines of class j, requested by i.

Nota : if $\Pi[C] = 1$ then $P_C = ||C||$ !

This number is untractable which renders this result useless ; nevertheless, it shows
the kind of problem we are trying to tackle.

We can never compute any of the terms of this formula, which means we have to take for
each of them a higher bound, increasing like the number of schedules to be generated
by an enumeration-procedure.

In most of the cases, a large number of different schedules will give the same activation
time, moreover there exist machine and task constraints.

We do not actually know how to take advantage of these equivalences or constraints,
so that we have to generate all the possible schedules, and then choose the best one,
which leads to wasting twice as much time : generation of too many solutions and finally
choice among them.

An often used solution is random generation.

There is also a large amount of algorithms, working under severe constraints, that
give easily the best schedule, whatever the word best might mean.

It is often worthwhile, modifying the problem, to satisfy the constraints in order
to use these algorithms, especially when working with so called "mean" criteria :
"mean cost", "mean waiting-time", "mean residence-time".

But real-time problems cannot be solved with "mean" solutions. Each deadline must be
exactly satisfied. We need generating exact solutions without generating too many
parasitic ones.
In this paper, starting from papers by Heller and Logemann [HEL 62] and by Shrage [SHR 70], considering that machines are shared by distinct and permanent classes, each task i requesting $W(i,j)$ machines of class j, for any i, any j, we shall show:

- how not to generate parasitic solutions, and prove that none is generated. (parasitic : either redundant or useless).

- how to choose the machines to be allocated in order to suppress the term
  $$ \prod_j \binom{n(i,j)}{c(j)} \quad (\text{we have assumed that } C(j) \text{ was not depending on } i). $$

- what the possible schedules to be discarded are.

- how to take deadlocks into account.
## II. THE PROBLEM.

The scheduling problem, as encountered in real time systems, presents itself as a set of hypothesis :

* a set of *m* tasks, *C*, together with, for each of them, an activation time, a deadline, an activity time, a set of requests, a set of possible machines (we have assumed it to be whole classes).

* a set of *r* machines, named *M*, partitionned into classes.

* a set of constraints :

- Given by the user

task *a* must precede task *b*.

- Part of the problem

deadline, activation-time, activity-time.

- Set by the machines

no more than *k* tasks on the same machine at the same time (we assume *k* is one, otherwise the machine is equivalent to *k* ones that bear one user at a time). no preemption.

- Sharing ones

Synchronization, deadlocks.

- Other ones, that are added

Minimization of any cost function.

The searched solution must take the form of a schedule, i.e. a set of Gantt Charts, together with the way it was generated, such that each constraint is satisfied, where a Gantt Chart is :

an occupation diagram, showing for each time unit the task the machine is allocated to or whether the machine is idle.

<figure><img src="image_1.png" /><figcaption>Figure 1. A Gantt Chart.</figcaption></figure>
### III. PRELIMINARY DEFINITIONS.

#### Definition 1.

A real-time task, is the part of a real time process, taking place between two distinct resource requests.

In the first part of this paper we shall consider two requests to be distinct if the process releases all the units he requested first, before performing the second request.

In the second part we shall extend the results, considering two requests to be distinct if the process can be partially executed between the first and the second one. We shall see, it is useless to do further distinction.

#### Definition 2.

Real time process is taken as in [DON 74]; as a summary we shall state it is the execution of any thing that needs resources to be executed, and must be executed before a deadline.

#### Definition 3.

A unit is Non-preemptive, if it cannot be disallocated unless the task to which it belongs has released it, either because :

- disallocating would destroy the task, or else

- it would destroy the machine : (for instance a file), or

- the needed time to disallocate and reallocate the unit would be too large with respect to the activity time, or the max-residence-time (deadline - activation-time).

#### Definition 4.

A unit or machine or resource refers to [DON 74] it will be either programmable ones (P in PMS [BEL 71]) or passive ones (Memories,files,M in PMS [BEL 71]). It is a necessary and reusable unit required for performing some task.
Example : if someone wishes to be in New York on the 1st of April, the thing to be executed is a displacement :

The travel will be the process, the deadline will be April 1st

The resources will be a car to go to the airport
a plane
a crew

and perhaps some petrol for the car and plane.

The requests will be :

1st a car
2nd petrol for the car
3rd a plane
4th petrol for the plane
5th a crew.

The 1st and 2nd ones will not be distinct in the first part (he does not release the car before asking for petrol) but will be in the second part (he has to drive to the station before asking).

The 3rd, 4th, 5th shall never be distinct. You have to take the 3 resources at the same time (at least in a non stop flight).

The plane, crew, plane's petrol are non preemptive resources; if you take the plane the traveller can not stay alone in the air, with crew and petrol; if you take the crew, plane, traveller and crew, will be destroyed; if you take the petrol the same will happen.

One can suppose the car to be preemptive, but it may take too long, to go back to the station, give the car back, wait for a new one, refill it, start again. So we shall consider it is a non preemptive one.
Using the terminology of [DON 74].

resources are a "context",
the displacement is a "procedure",
displacement + resources is a "process body",
requests are "interrupts" or "break-points",
the plane a "privileged resource",
the travel agency a "monitor".

Definition 5.

A *static algorithm* is an algorithm which works once on a finite
and static set of Data. (for instance : Order this set of Data).

Definition 6.

A *dynamic algorithm* works on a changing set of Data
as many times as the set changes, or as many times as a subset changes.
(for instance : Insert the arriving data in this set, when arriving).

Definition 7.

A *Direct solution*, is a solution "y" given by a formula such as
y = f(x) where x is the problem, f is a function that leads to y. E. g :

$$
y = \frac{-b \pm \sqrt{\Delta}}{2a} \text{ is a direct solution for the problem } x :
$$

find y such that ay² + by + c = 0.

Definition 8.

A *combinatorial solution*, is a solution "y" that can be found only
by trying each value of a set E(x) depending on x, to discover one, such that
a predicate P holds for it. The problem :

find y = (a,b,c) such that a² + b² = c², with a,b,c ∈ N : has only such a solution.
# IV. THE SCHEDULING ALGORITHM.

## IV.1. The study.

ORDON is the first part of a study covering:

- Real Time Processes on non Preemptive Units (RTP on 1PU) study for a Real time monitor, done for the SPECTRE project (Present paper),

- Real Time Processes on Preemptive and non Preemptive Units (RTP on (P<sub>E</sub> | P)U) (to appear),

- Scheduling problems and solutions, a survey (to appear).

This study is paralleling the study by J.Labetoulle [LAB 74] (Real time processes on preemptive units).

Its aim is to set models for scheduling and synchronization problems, for the continuation of the SPECTRE project, or CETASI project, (Automatic Design, Operation and Test for Industrial Systems).

As, nowadays way of writing scheduling algorithms is a pragmatic one, (it is quite the same problem in proof techniques or structuring concepts), we had to cope with 2 different techniques [SHR 70], [RAN 66] to find a solution for (RTP on 1PU) and [RTP on (P<sub>E</sub> | P)U] in spite of the similarity of these problems So, we now try, through modeling [DON 74], [ROD 73], [CHA 74], to define automatic ways of writing systems, starting from a formal definition, and parametrization.

## IV.2. The aim of ORDON.

Obviously, no dynamic algorithm considering requests when they appear, may ensure a request will be satisfied before its deadline, (the unit may be allocated until that time).

So, we have to use static algorithms, considering past and future requests together with the present one.

We emphasize that such algorithms, have not been defined to solve realtime scheduling problems, but 2 others kinds of questions :

Deadlocks [HAB 69], and Min-makespan [CON 67]. In the real time case, the requests were granted, using over allocation, a process was given its resources for its whole life time, except for Central Units and Channels, which were used as sequencing units (Using RTP on PU algorithms).
We shall try to use these algorithms to solve real time scheduling problems.

A first remark acknowledge there are direct solutions that may solve Min-Makespan and Deadlock problems, but only combinatorial ones to solve real time sequencing.

A second remark is there are two ways of *generating schedules*.
- Considering time units, one runs as many tasks as possible during the same time unit, and generates a schedule time unit by time unit (or groups of).

-Considering tasks, one starts with an empty schedule, and fills it, task after task.
(See figure 2).

We chose the second way for ORDON.

In that case, we can notice that 2 different ways of generation may lead to the same schedule ; or to equivalent ones. (Same activation time, or useless idle time).

We shall have to detect such double or equivalent generations.

So we must define criteria such that we can detect *as soon as possible* double generations, equivalent generations, or generation of a useless schedule (a schedule which violates the constraints).

By as soon as possible, we mean as soon as a constraint is violated, or as soon as we can foresee one constraint will be violated, or as soon as a subgeneration leads to the same subschedule as another one.
<figure><img src="image_2.png" /><figcaption>Figure 2 : The two ways of generating.</figcaption></figure>

This schedule can be generated in two ways.

1) Time unit by time unit.

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

2) Task after task.

<figure><img src="image_5.png" /></figure>
### IV.3. The algorithm.

We extend the work done by Shrage, in order to know at each step which unit is allocated to the job. So we must first start from the general case.

We define a way of scheduling, and choosing tasks, to be able to discard the term $\prod_j C_j^{|W(i,j)|} ||c(j)||$ for any $j$.

We prove we have discarded as many schedules as possible.

### Contents of this chapter :

We first state 2 easy properties ; then define the words "choose" and "schedule" so as to turn them into programming PRIMITIVES.

We prove these definitions do not violate the generality of the problem, then prove they are useful to discard $\prod_j C_j^{|W(i,j)|} ||c(j)||$ and some other schedules.

We prove then that there is no more schedule to be discarded.

In the case of a release between 2 requests.

Then we consider the case where there is no release, and show how in that case too many schedules may have been discarded by the previous algorithm, how not to discard them by modifying the algorithm. We then state a method to take further detection into account, not to have to detect twice the same kind of deadlock situation.

### Definition 9.

The *arrival time* of a task is the instant when it is meaningful to consider starting its activation. For instance, several predecessor tasks might be required to have been all or a fraction successfully terminated, according to some combinatorial precedence function.
m: the total number of tasks.

h: the total number of resources types.

ha(i): arrival time of a task.

hdl(i): deadline of task i.

d(i): activity time of task i.

h(i): activation time of task i (the time it will really start).

W(i): Request matrix of i (1 row for each class of units, this row contains the number of units of this class the task requests).

$W = \{W(i) \mid i = 1, \dots, m\}: \text{Request Matrix.}$

Σ the set of tasks, $\Delta = [1, \dots, m]$, labelled from 1 to m).

Mach (i): Allocation matrix of i ' for each type, the list of the machines allocated to i'.

mach(i) : one of the elements of Mach (i).

Mach (i) : Allocation matrix given by the allocation law X.

X

mach(i) : one of the elements of Mach (i).

X

X

lib(Mach(i)) : a matrix, containing the times at which the machines allocated to i are released by the tasks they are allocated to, before being allocated to i'.

lib(mach(i)) : one of the elements of lib(Mach(i)).

av(j) : the list of all tasks that have not been scheduled yet after (j-1) scheduling steps, but all their predecessors have been.

σ(j,k,y) : earliest start time for task j, if (k-1) other tasks are decided upon to be the (k-1) first elements of permutation y.

σ(j,k) : the same as σ(j,k,y) when y is the permutation being generated.

χ: the problem defined by hdl, ha, d, W, m, n and constraints.

S(χ) : the set of solutions for the problem χ.

E(χ) : the set of possible schedules, $E(\chi) \supset S(\chi)$.

y : One permutation of the m first natural numbers.

y(i) : i-th number of the permutation y (equivalent to the task numbered y(i)).
Remarks :

1). Let

$I(a,b) \triangleq$ the $b^{th}$ earliest liberation time of a machine
of type "a",
(if $b = 0$ then $I(a,b) = 0$).
i.e.the $b^{th}$ lib(mach) | mach $\in$ type "a".

Recall

$y \triangleq$ one permutation of the m first natural numbers.

$\sigma(i,k) \triangleq$ the earliest start time for i if $y(1) \dots y(k-1)$
are scheduled in this order.

Given some $y$,
we have $\sigma(i,k) = \text{Sup} \left\{ \text{ha}(i), \text{Sup} \ (I(j,W(i,j))) \right\}$
$j = (1, \dots, n)$

$j = 1, \dots, n \text{ i.e. all resources types.}$

This is not the definition given by Shrage, but we shall see
(LEMMA 7), using further results, we can take this definition.

2)A schedule is given by:

$$
\begin{cases}
y \\
\{h(y(i)), i \in [1, m]\} \\
\{\text{Mach}(y(i)), i \in [1, m]\}
\end{cases}
$$
IV.3.2.A primary version of Ordon.

The algorithm is used to generate all schedules counted by $P_{\mathcal{C}}$
(formula of the introduction):

$$
P_{\mathcal{C}} = \sum_{i=1}^{m} P_{\mathcal{C},i} \quad \text{with} \quad m = \|\mathcal{C}\|.
$$

by computing recursively $P_{\mathcal{C}}$-{a subset of $\mathcal{C}$} and generating all corresponding schedules.

Let us first put the mathematical formula into algorithmic form.

$\mathcal{A}\mathcal{V}(i)$ is $\mathcal{C}$ - { a subset of $\mathcal{C}$ }
while $\mathcal{A}\mathcal{V}(i) \neq \emptyset$ CHOOSE $j, j \in \mathcal{A}\mathcal{V}(i)$ replaces $\sum_{i=1}^{\|\mathcal{C}\|}$

For all possible selections takes care of
$$ \prod_{j=1}^{||N/\mathbb{E}_i||} \int_{||C(i,j)||}^{w(i,j)} $$ so that,
Call scheduler (i+1) provides us with
$P_{\mathcal{C}}^{\mathcal{C}}\{i\}.$

We use the fact, proved by Heller and Logemann [HEL 62], it is useless
generating schedules where a task is placed before one of its predecessors. So, we
only place in $\mathcal{A}\mathcal{V}(i)$ tasks belonging to $\mathcal{C}_{-}\{\text{subset of } \mathcal{C}\}$, which predecessors belong to
"subset of $\mathcal{C}$", that is which predecessors are already scheduled.
SCHEDULER (i) recursive procedure.

$Av(i) = \begin{cases} \text{if } i=1 & \text{then all tasks with no predecessors.} \\ \text{if } i \neq 1 & \text{then all tasks that have not been scheduled} \end{cases}$
and either with no predecessors or which predecessors have been scheduled.

```pascal
While Av(i) ≠ Ø <<comment Σ P >>
    C6,j
        CHOOSE (j) j ∈ Av(i)
        y(i) = j
        For all possible selections
            between all units
                select machines for j, and allocate
                    them
                if i=m then if optimal (Schedule)
                    then print ;
                else call scheduler (i+1) ;
                <<comment : xPc-j ; >>
        Suppress j from Av(i)
```

End Scheduler.

$\text{optimal (Schedule)} = \begin{cases} 1 & \text{if schedule fulfills the constraints} \\ 0 & \text{otherwise} \end{cases}$
### IV.3.3. Two straight forward properties.

1) if by step i, there exists j, such that $j \in Av(i)$

$$ \sigma(j,i) > hdl(j) - d(j) $$

it would be useless to keep on generating such a schedule.

Since this job j is already late, scheduling other ones before scheduling it would only delay it more. So job j must be scheduled before step i: we have to go back at least to step i-1.

If $i=1$ there is no solution to the problem.

2) if by step i, there exist 1, j such that $1, j \in Av(i)$

$$ \sigma(1,i) + d(1) \le \sigma(j,i) $$

then j can be discarded from $Av(i)$.

The proof is given in [SHR 70].

Scheduling j at step i would either change nothing for 1 or delay 1 unduly as 1 can be scheduled before j without delaying j.

### IV.3.4. Specification of the SCHEDULE and CHOOSE Primitives.

#### CHOOSE.

We might use a random choice law, but we shall see that using a defined choice law will reduce the problem.

Having no results about the numerous possible laws, we shall use the natural ordering.

#### SCHEDULE.

Once $\sigma(i,j,y)$ has been computed and i has been chosen to be the $j^{th}$ element of y:

i will be granted units such that $h(i) = \sigma(i,j)$, that is the Earliest Start Time Policy used by Shrage (ESTP).

But we may have to choose among many available units, fulfilling this condition.

In such a case if machines are really equivalent, i will be given the $W(i,1)$ machines k of type 1 such that:

$$ \sigma(i,j) \ge \text{lib} (\text{mach } k) $$

$\text{lib} (\text{mach } k) \ge \text{lib} (\text{mach } k')$ for any available k and k', machine k being allocated, $k'$ being not.

That will be the Smallest Hole Policy or SHP because it leads to creating the smallest idle time on a unit.
<figure><img src="image_6.png" /></figure>

Units 1,2,3,4 ε 5 being equivalent, if task i requests two machines, it will be given machine 1 and 4;

unit five does not fit : lib (5) > σ(i,j),

unit 2 and 3 do not fit : lib (2) < lib (4) lib (3) < lib (4)

lib (2) < lib (1) lib (3) < lib (1). Hence

if only one unit is requested, it will be unit 4;

if 3 it will be 4,1,3.

Figure 3 : The SHP.
No job j would be delayed using the SHP to allocate units to a
job i, with i preceding j in the permutation y; in spite of the ESTP. Where delaying
means, there is no way of allocating units to i, such that i being considered
before j, j starts earlier than when allocating to i using the SHP, i starting as
soon as possible.

Proof.

*1:h(i) start time of i will not change ESTP implies h(i) = σ(i,k) ·
SHP implies it too

$$
\sigma(i,k) = \sup [\text{ha}(i), \sup_{\ell=1,\dots,n} (\text{I}(\ell, \mathcal{W}(i, \ell)))]
$$

If σ(i,k) = ha(i), there exist at least W(i,l) machines for each type l such that
their liberation time is less than or equal to σ(i,k) :

- so from all these units we may choose the w(i,l) machines having the
latest liberation time

- so they can be allocated to i and $h(i) = ha(i)$,
otherwise $\sigma(i,k) = I(l,w(i,l))$ for at least one $l$;
but for this $l$ there exist $w(i,l)_-^1$ machines such that $\text{lib}(\text{mach}) \le \sigma(i,k)$ and one
more such that $\text{lib} = \sigma$,

- so they can be given to task i; for it to be started as soon as possible.
i will be given one machine of type P such that $\text{lib}(\text{mach}_i) = \sigma(i,k)$; for all other
types, it is the same as seen above, so i can be granted enough machines such
that $h(i) = \sigma(i,k)$; so i is not delayed.

*2:for any other job j there are three possible cases :

1) j must follow i (User constraint) as h(i) did not change, h(j) did not either.

2) j must run on at least one machine of the same type as a machine allocated to i.
There exist two cases to be considered :

either
$$ \text{lib (mach (j))} \le \text{lib (mach (i))} $$
SHP
SHP

for any machine allocated to i, for any machine allocated to j.

So j would not start earlier using the machines allocated to i.

or
there exist two machines such that :

$\text{lib (mach (j))} > \text{lib (mach (i))}$ and
SHP
SHP

either $ha(j) \ge \text{lib (mach (j))}$ and j would not start earlier
SHP

or $ha(j) < \text{lib(mach (j))}$;
SHP

this implies $\text{lib (mach (j))} > \sigma(i,k)$
SHP

(or i would be executed on this machine when using the SHP)

but i would not be executed on this machine either when using the ESTP.

So j is not delayed, using the SHP in spite of the ESTP.

3) Finally $h(j)$ does not depend on i at all, even if depending on a successor of i.

The way of scheduling i does not change anything for the units to be allocated to j.

j is not delayed.
IV.3.5.A first set of theorems.

**LEMMA 2.** Once the (k-2) first elements of y are decided upon.

If $\sigma(j,k) < \sigma(i,k-1)$, then any sequence y such that $y(k) = j, y(k-1) = i$ is useless, as leading to the same schedule than the sequence with $y(k) = i, y(k-1) = j$.

**Proof.**

$\sigma(j,k) < \sigma(i,k-1)$ means

$\text{Mach } (j) \cap \text{Mach } (i) = \emptyset$

otherwise it would exist a machine processing i and j, and as i is scheduled before j, i precedes j on this machine but as

$\sigma(j,k) = h(j) \quad \text{implies } j \text{ is executed before } i,$
$\sigma(i,k-1) = h(i)$

this is a contradiction

So, if $\sigma(j,k) < \sigma(i,k-1)$, there exist enough units to serve j and i at the same time.

So considering j before i, or i before j, leads to the same schedule or schedules with the same starting times for all tasks. (The machines allocated will be free at the same time in both cases, or at least one equivalent machine will be free at the same time).

-if i and j need not any machine of the same type. In both cases, they will be given the same units.

-if i and j need machines of the same type. There are enough of these units for both tasks. Let us assume 2 units, (each task requesting one), noted a and b.

perhaps in the first case i will get a and j, b.

while in the second one i, b and j, a.

but a or b will be free at $h(i) + d(i)$

b or a will be free at $h(j) + d(j)$

So in both cases, both units will be free at $\text{Max}(h(i) + d(i), h(j) + d(j))$ and one at $\text{Min}(h(i) + d(i), h(j) + d(j))$

**Nota.** If i and j are given a and b in one case, they can only be given a and b, or units with the same liberation time, in the other case, according to the SHP (the 2 machines must have the largest liberation time). This completes the proof.
Let $i>j$ mean that $j$ is chosen first according to the choice law,
if the choice law is the natural ordering, $>j$ has its natural meaning.

We assumed we use this law, but any other one would yield the same result
provided it is a static one. (Not depending on time).

LEMMA 3. Once the (k-2) first elements of y have been decided upon,
if i>j and $\sigma(j,k) = \sigma(i,k-1)$, any y such that $y(k) = j$, $y(k-1) = i$ is
useless, as leading to the same schedule than y with $y(k) = i, y(k-1) = j$.

Proof.

Let us express y as the 4-tuple $(X, i, j, Y)$

X a list of k-2 elements

Y, m-k elements.

Any element belonging to the set X does not depend on the relative position
of i and j.

Any element belonging to y does depend on the releasing time of the machines
allocated to i and j, or on the ending time of i or j.

Let us consider the different cases :

$$
\sigma(j,k) = \sigma(i,k-1) \Rightarrow \text{Mach } (i) \cap \text{Mach } (j) = \emptyset
$$

(there cannot be 2 tasks at the same time on the same unit).

1st Case. :If i and j do not request machines of the same type. In both
cases (i before j, or j before i), they will be given the same units. So i before j,
or j before i leads to the same schedule. We only need to consider one permutation.
When using a static choice rule, we know which permutation will be considered first,
so when considering the second, knowing it leads to the same schedule as a previously
considered one, we can discard it.
2<sup>nd</sup> Case Contains four possibilities.
(i and j requesting units of the same type)

$$
\text{II.1} \quad \begin{cases} \sigma(i,k-1) = ha(i) \\ \sigma(j,k) = ha(j) \end{cases}
$$

$$
\text{II.2} \quad \begin{cases} \sigma(i,k-1) = ha(i) \\ \sigma(j,k) = \text{lib}(\text{mach-m}), \text{mach-m} \text{ one of the } \text{Mach}(j) \end{cases} \quad \text{SHP}
$$

$$
\text{II.3} \quad \begin{cases} \sigma(i,k-1) = \text{lib}(\text{mach-}\ell), \text{ mach-}\ell \text{ one of the } \text{Mach}(i) \\ \sigma(j,k) = ha(j) \end{cases} \quad \text{SHP}
$$

$$
\text{II.4} \quad \begin{cases} \sigma(i,k-1) = \text{lib}(\text{mach-p}) & \text{mach-p one of the Mach } (i) \\ \sigma(j,k) = \text{lib}(\text{mach-m}) & \text{mach-m one of the Mach } (j) \end{cases} \quad \begin{array}{l} \text{SHP} \\ \text{SHP.} \end{array}
$$

II.1. Considering i before j (or reverse) leads to the same schedule, both cannot start earlier, and as in lemma 2, machines will be released at the same time, or an equivalent one will be.

II.2. Perhaps would j start earlier, using a machine allocated to i, let us say mach *l*.
This would imply :

lib (mach-*l*) < lib (mach-*m*) = σ(j,k) = σ(i,k-1)

*l* and *m* being of the same type.

Using the SHP this cannot be (i must be given mach *m*)

So neither i or j can start earlier, it is, the same as in II.1.

II.3. j. cannot start earlier.

i cannot start earlier using units allocated to j, or they would have been
given to i.
Would i or j start earlier or later, scheduling j before i?

- j would not start earlier, $\sigma(ha(j))$ would be the same in both cases.

- i would not either, allocating units to j before allocating others to i
would not make other tasks release their units earlier.

$$ \text{So} \quad \begin{cases} \sigma(j,k-1) \ge \sigma(j,k) \\ \sigma(i,k) \ge \sigma(i,k-1) \end{cases}. $$

- But j would not start later, if there were enough units available for him
to start by $ha(j)$ in the first case, the same units being available, plus all these
that were allocated to i, j can start as soon as when considered after i. This implies :

$$ \sigma(j,k-1) = \sigma(j,k) $$

- And i would not either start later :

- All the units belonging to unit-types not requested by j
are still available as in the first case.

- For the types requested by i and j. There were enough units
to start i and j at the same time, there are still enough.

$$ \sigma(i,k) = \sigma(i,k-1). $$

- we can prove, as in lemma 2, the same units will be allocated,
or equivalent ones will be.

- This leads to the same conclusion as in II.1 or II.2.

## II.4. Scheduling j before i :

- j would not start later as when scheduled after i. The same units as in
case i-before-j are available, plus all those that were allocated to i. In the worst
case, j is given the same units and starts at the same time.

- j would not start earlier.

- if scheduled on the same units he cannot.

- if scheduled on a unit previously allocated to i, let us
say $l$ in place of being scheduled as is the previous case on a unit m.
This would imply $\underline{\underline{\text{lib}}}(\text{mach } \ell) < \underline{\underline{\text{lib}}}(\text{mach } m) \le \sigma(j,k) = \sigma(i,k-1)$;
but using SHP,m would be allocated to i in the previous case, not $\ell$.

So there is no way for j to start earlier.

- i cannot start earlier, less units are early available than in the
  previous case, some of them being allocated to j.

_i_ would not start later. There were enough units to serve i and j at the
same time . As the same are available with the same liberation time, we still can
schedule i and j at the same time as before.

-Using the same way as in lemma 2, we prove the same units or equivalent
ones are used, leading to the same conclusion as in II.1,II.2,II.3.

Leammas 2 and 3 lead to Theorem 1.

THEOREM 1.

Once the (k-2) first elements of y are decided upon :

if $[\sigma(j,k) < \sigma(i,k-1)]$

or

$[\sigma(j,k) = \sigma(i,k-1)]$ and $[i>j]$

any sequence y such that $y(k) = j, y(k-1) = i$ is useless.

Proof.

The proof is straight forward by lemma 2 and 3.

Property 1.

We may stop the generation of any schedule such that :

$\sigma(y(k),k) < \sigma(y(k-1), k-1)$

or

$\sigma(y(k),k) = \sigma(y(k-1), k-1)$ and $y(k) < (k-1)$

Theorem 1 proves this schedule is useless. We will not keep on generating
it.
LEMMA 4.

There cannot exist $y$ such that there exist $k$ and $\ell$ such that :

$$ \sigma(y(k),k,y) < \sigma(y(k-\ell), k-\ell,y) $$

Proof.

using property one, any generated $y$ is such that :

$$ \sigma(y(k),k,y) \geq \sigma(y(k-1), k-1,y) \text{ for any } k. $$

so

$$ \sigma(y(k-\ell), k-\ell,y) \leq \sigma(y(k-\ell+1), k-\ell + 1,y) \dots $$

$$ \leq \sigma(y(k-1), k-1,y) \leq \sigma(y(k),k,y). $$

$$ \text{for any generated } y : \quad \sigma(y(k-\ell),k-\ell,y) \leq \sigma(y(k),k,y) $$

$$ \text{for any } k, \text{ any } \ell. $$

LEMMA 5.

It cannot exist $y$ such that there exist $k$ and $\ell$ such that :

$$ \sigma(y,(k), k,y) = \sigma(y(k-\ell),k-\ell,y) $$

$$ y(k) < y(k-\ell) $$

Proof.

1) if there exists $b, k-\ell < b < k$, such that :

$$ \begin{cases} \sigma(y(b),b,y) > \sigma(y(k),k,y), & \text{this implies :} \\ y \text{ has to be discarded (LEMMA 4).} & \end{cases} $$

2) if there exists $b, k-\ell < b < k$ such that :

$$ \sigma(y(b),b,y) < \sigma(y(k),k,y) = \sigma(y(k-\ell),k-\ell,y), \text{ this implies :} \\ \text{y has to be discarded (LEMMA 4).} $$
3) if for any $b, k \ge b \ge k-l$ :

$\sigma(y(b), b, y) = \sigma(y(k), k, y) = \sigma(y(k-l), k-l, y)$ then.

Theorem 1 implies:

$y(k-l) < y(k-l+1)$ otherwise $y$ would be discarded.

$y(k-l+1) < y(k-l+2)$

...

$y(k-1) < y(k)$

this implies:

$y(k-l) < y(k)$

this completes the proof.

## THEOREM 2.

It cannot exist $y, y'$ such that:

$$ egin{cases} \sigma(x, \text{pos}(x) \text{ in } y, y) = \sigma(x, \text{pos}(x) \text{ in } y', y') \text{ for any } x. \\ y \neq y'. \\ (\text{pos}(x) \text{ in } y \text{ means the position element } x \text{ has in permutation } y). \end{cases} $$

## Proof.

$y \neq y'$ implies there exist $i$ and $j$, $i$ is before $j$ in $y$, $j$ is before $i$ in $y'$,

That is: if $\text{pos}(j)$ in $y$ is $k$, $\text{pos}(i)$ in $y$ is $k-l$.

if $\text{pos}(i)$ in $y'$ is $k'$, $\text{pos}(j)$ in $y'$ is $k'-l'$.

So we can ensure:

-if $\sigma(i, k-l, y) > \sigma(j, k, y)$ : $y$ has been discarded (according to LEMMA 4)

-if $\sigma(i, k-l, y) < \sigma(j, k, y)$ this implies:

$\sigma(i, k', y') < \sigma(j, k'-l', y')$ : $y'$ has been discarded (according to LEMMA 4)
-if $\sigma(i,k-l,y) = \sigma(j,k,y)$ then 2 cases are to be considered :

-i<j then y' has been discarded (according to LEMMA 5)

-i>j then y has been discarded (according to LEMMA 5)

## Property 2.

Using Property 1, and SHP, no set of Gantt Charts will be generated twice.

## Proof.

A set of Gantt Charts is generated twice, if generated by two different permutations leading to the same start time $h(i)$ for any $i$.

Using SHP, $h(i) = \sigma(i,\text{pos}(i) \text{ in y, y})$.

THEOREM 2 proves there cannot exist 2 permutations giving the same $\sigma$ for any $i$.

## LEMMA 6.

There is no generated schedule containing idle periods large enough to execute a task $t$ during some of these idle periods sooner than scheduled, without delaying an other task or starting one of its predecessors earlier.

## Proof.

If there is no task scheduled on the units after the idle periods, whatever $\text{pos}(t)$ in $y$ could have been, the units were available for executing $t$ on them. If $t$ has not been scheduled on them according to the SHP, this implies $t$ would not have started earlier scheduled on them.
-if there are tasks scheduled on the units after the idle periods. Let these tasks be called $U_1...U_n$. Let u be the first of these tasks to be scheduled.

*If $t$ was belonging to $Av(pos(u)in y)$, ($t$ was belonging to the set of tasks that could have been scheduled by step $pos(u)$ in $y$, in place of $u$),

then asserting that $t$ can be scheduled on the unit allocated to $u$, without delaying $u$, implies $\sigma(t, pos(u) \text{ in } y, y) + d(t) \le \sigma(u, pos(u) \text{ in } y, y)$.

This implies, using the second straight-forward property $u$ can not be scheduled at this step.

This is a contradiction.

*If $t$ was not belonging to $Av(pos(u)in y)$, then either $t$ was already scheduled, then, when scheduled, $t$ could have been scheduled before $u$ on this unit.

If $t$ has not been, scheduled on it according to SHP, it implies $t$ would not start earlier if scheduled on it.

Or $t$ was not scheduled, then this implies one of its predecessor was not scheduled yet, and has been scheduled after $u$. The start time of this predecessor must be greater than the start time of $u$ (or $y$ would be discarded according to THEOREM 1) then as $t$ can not start before one of its predecessors $t$ cannot start before $u$. $t$ cannot be scheduled during the idle period.

So anyway, either $t$ cannot start earlier, or $y$ is not generated.
There is no way of rearranging tasks on the units, in order to start a task t earlier, without delaying an other task.

Proof.

Let the schedule given by the SHP be modified by an allocation policy that gives better results than the SHP.

Let us consider now :

Y = {$y(1)...y(n)$} the task-names, ordered according to the start times given by the SHP.

H = {$h(1)...h(n)$} the start times of tasks y(i) according to the permutation y, and the SHP.

M = {$m(1)...m(n)$} the units allocated to tasks y(i) according to the SHP.

Pos' = {$p'(1)...p'(n)$} the new position of tasks y(i) once they have been ordered according to the new start times.

H' = {$h'(1)...h'(n)$} the new start time of tasks y(i) according to the new allocation policy.

M' = {$m'(1)...m'(n)$} the new units of tasks y(i) according to the new allocation policy.

Let i be the first integer such that :

$$ \begin{cases} \text{either } m(i) \neq m'(i) \\ \text{or } h(i) \neq h'(i) \end{cases} $$

the results being the same with both policies for $k = 1, \dots, i-1$.

If $h(i) \neq h'(i)$ (implies $h(i) > h'(i)$, or $y(i)$ would have been delayed using the second policy).
Then if for any k, $1 \le k < i, p'(k) < p'(i)$ that is, if all the tasks scheduled before $y(i)$ in the first case still have smaller start times than $y(i)$ in the second case, then the SHP implies $y(i)$ cannot start earlier, as

$y(1) ... y(i-1)$ being placed, $y(i)$ is scheduled with the smallest start time.

Else, if $y(i)$ is placed before one $y(k)$ in the second case, this implies there were enough idle periods in the first case, left by $y(1) ... y(i-1)$ to start $y(i)$ earlier. This cannot be, according to lemma 6. (Nota if a predecessor of $y(i)$ had been scheduled earlier, i would not be the first integer).

$$ \text{So } h(i) = h'(i). $$

$$ \text{If } m(i) \neq m'(i). $$

Two cases are to be considered, for each pair of units, $m, m'$; $m, m'$ allocated to $y(i)$ by SHP the other unit of the pair, being allocated by the other policy.

Let us first consider the two corresponding Gantt Charts

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

The status of both units after having scheduled $y(1) ... y(i-1)$ (according to any of the both policies) ($t_{0}$ may be equal to $t_{1}$ but not larger according to the SHP).

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

The status of both units after having scheduled all tasks according to the SHP.

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

The status of both units, after having scheduled all tasks according to the other policy.
THEOREM 3.

There is no way of rearranging a generated schedule to start a task t earlier without delaying an other task u.

Proof.

Rearranging would imply exchanging the units of task t, either with some
other tasks, or with no other task (idle period)
LEMMA 5 ∈ 7 prove this cannot be done without delaying another task.

Q.E.D.

Property 3.

No two equivalent schedules are generated. Property 2 said there were
not two schedules with equal start times.

We have now proved that changing the start time of a task would
delay another one, perhaps leading to a non fulfillment of the deadline. So
all generated schedules must be considered.

We have now proved, we only generate usefull schedules, and minima
ones.

We will now prove, we generate all minima schedules. And generate an
equivalent schedule for all schedules.

Let any schedule be considered.

Rearrange tasks and units to get one minimum start time for all tasks,
without delaying any. This gives us a minima schedule.

Now, let us order the tasks, according to the start times given by the
minima schedule. (if 2 start times are equal, according to the natural ordering of
the name).

Now, let us generate a schedule, according to the SHP and this order.
(only using the second straight forward property, not property one).
-Using the same notations as before. (Note that $P' = \{1...n\}$, as we have the same ordering in both cases).

-Let $i$ be the first integer such that:
  $$ \begin{cases} h'(i) > k h(i) \\ \text{or} \\ h'(i) < h(i) \\ \text{or} \\ m(i) \neq m'(i) \\ \text{or} \\ \text{the generation is stopped.} \end{cases} $$

-If we only have $h'(i) > h(i)$:

this implies there is a useless idle period before $y(i)$ in the schedule said to be minima, this cannot be:

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

a useless idle period in the schedule said to be minima.

-If we only have $m(i) \neq m'(i)$:

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

let us exchange the use of $m$ and $m'$ for the part of the minima schedule contained between $t_0$ and $t_1$, ($t_1$ will not delay any task).

-If $h(i) > h'(i)$:

this would mean for the set $y(1) ... y(i)$ there is a better way of allocating than SHP this cannot be according to lemma 7.
-if $h'(i) < h'(i)$ and $m(i) \neq m'(i)$ :

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

let us first exchange the use of $m$ et $m'$ between $t_1$ and $t_\infty$. Then we
only have $h(i) < h'(i)$.

-if the generation is stopped according to the 2<sup>nd</sup> straight forward property, this
also implies, the minima is not a minima.

The use of property P1 by step i would be redundant with $h'(i) > h(i)$
or $h'(i-1) < h(i-1)$.

Property P3, and this, are justifications for the use of SHP. Lemma 1 was a primary
justification, but now we have some more results, we have proved the usefulness
of SHP.
# IV.4. The problem of delayed requests

## IV.4.1. Partitionning tasks

Until now, we considered all ressources were requested at the same time, and released the same way.

That gave such occupation diagrams:

units

<figure><img src="image_13.png" /><figcaption>Figure 4.</figcaption></figure>

No delayed request

We shall now consider another kind of requests, we call delayed requests.

<figure><img src="image_14.png" /><figcaption>Figure 5.</figcaption></figure>

Delayed requests

A first remark

We cannot schedule task 1 and 2 within less than 8 time units when left this way:

<figure><img src="image_15.png" /><figcaption>Figure 6.</figcaption></figure>

The use of idle periods.

But if we create one idle period on machine a, tasks 1 and 2 can be scheduled within 7 time units.
<figure><img src="image_16.png" /><figcaption>Figure 6 bis.
The use of idle periods</figcaption></figure>

Note that we did not disallocate unit a. No other task than 1 uses it during the 5 th time unit. We just stopped the activity of task 1 during the 5 th time unit.

Scheduling with idle periods imply that such idle periods will not disturb the activity of task 1.

Scheduling with idle periods imply we know where to place such periods. In the previous example, we could have placed such a period during 4 th or 6 th time unit as well as during the 5<sup>th</sup> one.

We shall manage with these 2 problems.

LEMMA 8

If the request times are all the alike, using idle periods can
only introduce undue delays.

Proof :

An idle period would only increase occupation time of all machines
without allowing the scheduling of an other task on one of them.

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

In this case
idle periods
would be useless.

Q.E.D.

LEMMA 9

If we can choose the place for an idle period, we should choose
the time unit during which the least number of units are requested.

Proof :

This is obvious considering idle periods are time-wasting.
- if we have to choose between 2 time units during which the same units are allocated, we can choose the latest one.

The aim of idle periods on a unit is to delay a request on another one, to be able to schedule an other task on the other unit.

As soon as the request is delayed, provided it does not delay a previous release of the same unit, the aim is reached.

So we now know where to place idle periods.

It must be before the considered task requests the unit on which we want to place another task before the considered one.

It must be after the latest previous release of this machine.

It must be when the task to be stopped has the smallest number of resources (provided it fulfills the first two constraints) : that is a relative minimum of the number of resources. That is before a request.

So whenever we must create and idle period, it must be done before a request.

As we do not know when to start scheduling whether an idle period will be needed, we shall first partition all tasks with delayed request into as many subtasks as requests. Giving a subtasks-string.

<figure><img src="image_18.png" /><figcaption>Figure 7.</figcaption></figure>

Partitioning tasks to obtain subtasks-strings.

And all subtasks will be considered as a task relatively to the scheduling algorithm, provided the fact we cannot allocate the units released by a subtask to any other task.
IV.4.2. Deadlock problem.

We did not provide a solution to the problem of non allocating units released by a subtask.

We still have not introduced the deadlock problem.

Deadlock.

In the first part, there was no deadlock problem, as any task released its units before requesting other ones.

If scheduling without partitionning tasks into subtasks, there would be no problem. All requests would be granted at the same time.

But this would demand many useless trials to place idle periods at the right place, if there exists any.

So we had better do this way, even if we must cope with deadlocks

Deadlock is commonly prevented in either of the following ways :

-No delayed requests, leading to large idle periods and lack of efficency.

-Bankers algorithm [HAB 69], which may lead to the previous result, or to undue delays [HOL 71].

The knowledge we have, and the benefit one may take out of a static algorithm, allow us, not to prevent deadlocks, but only detect them, as soon as possible, and choose the best resuming point.

We shall say, a non released unit has an undefined release-time, w such that inf (x,w) = x, sup (x,w) = w, x + w = w.

Justification of w = ∞ :

a task which wants to be executed on a non released unit, must wait
until all the tasks for which the unit is reserved are scheduled. So it
cannot belong to Av (Step at which such a subtask can be scheduled)
But it must belong to Av (Step when the last subtask is scheduled + 1)
Av (Step when the first subtask is scheduled).
It will belong to Av (last +1)

Perhaps it will not belong to Av (first), because this task or one of its
predecessor may be dominated unduly by the first subtask. So, we shall add
to Av (first) any task dominated by the first subtask, and not by one of
its successors.

A deadlock situation appears when a subtask owning a reserved unit
requests a reserved unit belonging to another subtask requesting the first
unit.

i.e. :

T₁ requests M₂ reserved for T₂ requesting M₁ reserved for T₁.

Or a larger loop.

To detect deadlocks, we shall use a (M+N) * (M+N) binary matrix,
or a M+N integer one, and the Marimont method [MAR 59].

IV.4.3. Backtrack.

To solve the deadlock situation, one of the reserved machine of
the deadlock-loop, must be released.

So we must backtrack to a step by which one of these units has
been allocated or any other generated sequence would lead to the same deadlock
situation. So we must at least resume at the last previous allocation of this
kind. Nothing allowing us to backtrack to a previous step we shall only
backtrack to this last allocation step.

But we can already assert it would be useless, reallocating this
unit to the same subtasks-string, unless one of the subtasks of the deadlock
loop has been scheduled (See LEMMA 10).

Until now, we have no information about the usefulness of detecting
whether a trial may lead to an already encountered deadlock situation. Storing
all encountered deadlock situations, and analysis of all generations, seems
more expensive than numerous detections and resumptions of the same deadlock
situation.
LEMMA 10

To solve a deadlock situation we must disallocate one of the machine
and not reallocate it until another one is released.

Proof :

Let us write the subtasks-strings encountered in the deadlock situa-
tion as :

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

where $B_i$'s are the tasks included in the deadlock loop, with $B_i$ wait for
machine i+1. Allocated to $B_{i+1}$... With $n+1 = 1$

if at one step of the algorithm, $\begin{cases} A_{1x_1} \\ A_{ix_i} \\ A_{nx_n} \end{cases}$ are scheduled,

what main happen in the further steps ?

We may schedule $A_{yx}$ tasks, until we encounter a $B_y$ that cannot be scheduled, waiting for $M_{y+1}$.

So as the number of task is a finite one, this will lead to have to schedule
all B's and only B's. But this is a deadlock situation.

So having scheduled $A_{1x_1} \dots A_{ix_i} \dots A_{nx_n}$ leads to a deadlock situation.

So we have to go back to the step we scheduled the last $A_{z1}$ and
stop the started generation.

Not going as far back, would left us in a $A_{1x_1} \dots$ situation that leads
to a deadlock.

And we cannot reschedule this $A_{z1}$ as long as a $C_{y1}$ has not been
scheduled.
As soon as a $C_{y1}$ is scheduled, we know we shall not encounter the same deadlock situation. We shall perhaps encounter another one, but not the same.

A way of preventing numerous detection of the same deadlock:

the way we are scheduling can lead us to encounter at several steps of the generation the same set of Axy.

So it may seem useful to design a prevention system.

A simple example can be :

Each time a $A_{x1}$ is scheduled add x to the stored x-list.

Each time a $C_{xk}$ is scheduled delete x from the stored X-list.

Each time a deadlock is encountered store the names of the subtasks-strings involved in the deadlock situation. Adding a new deadlock list.

Each time a subtask $A_{x1}$ is scheduled compare the stored x-list, with all deadlocks lists. If the x-list contains a deadlock list, further proceeding would lead to a deadlock. So we must stop the generation and backtrack to the previous step.
V. CONCLUSION

Starting from a highly combinatorial problem, (§ I, § II) with
a possible solution, we first proved *this solution could be a good one*,
(LEMMA 1). Then, we proved some results about this solution, leading to
the main result; *this solution was a good one* (§ III).

In the second part (§.IV) we give some indication and results
about an other kind of problem.

The restriction about idle periods, is not very important in
computers (a memory block may be idle for a long time without destroying
information). It may be important in factories (when a task must be done
exactly X mn after an other one).

But without this restriction, we must try all start-times between earliest
one, and deadline, and all unit allocation policies, and the earliest start
time is no more easy to compute.

This subject remains anyway open for further research, using the
second way of generation proceeding time-slice after time-slice.
i = 1

→ Start :

Call Built Av(i)

Call Sigma (Av(i), i, y)

Call Domination (Av(i), i, y), ⃗Av (i)

Call Deadlock (Av(i))

if ∃j ; σ(j,i,y) + d(j) > hd1(j) then i:= i-1

→ loop :

Do while Av(i) = ∅

L = i - 1

if i = 0 then stop ;

Select j from Av(i)

suppress j from Av(i)

y(i) = j

if ⃗ (σ(j, i, y) < σ(y(i-1), i-1, y))

Or

(σ(j, i, y) = σ(y(i-1), i-1, y))

And

j > y(i-1))

then

go to loop

else

if j = end of subtasks-string then, call Readd (j) :

Allocate units to j.

if i = N then print ;

i = i + 1

go to start
Built (K)

K = all subtasks, not yet scheduled, with no predecessors.

End Built

Sigma (K, L, M)

for all k k ∈ K.

compute σ(k, L, M) having regard to M(1) l = 1 - L

End Sigma

Domination (K, L, M, K̄)

D(*, L) = 0

- for all k, k ∈ K

for all k', k' ∈ K

if σ(k', L, M) + d(k') < σ(k, L, M)

then D(k, L) = D(k, L) + 1

for all k, k ∈ K

if D(k, L) > 0

then suppress k from K.

add k to K

End Domination
Deadlock (K)

Suppress from Av(i)

all heads of subtasks-string
which scheduling would lead to
a deadlock

Comment. "Only if using memorization of deadlocks".

Detect Deadlock.

if a deadlock is detected

Store list of subtasks-strings leading to this deadlock

Comment : "Only if using memorization of deadlocks"

i = sup

(pos (head of subtasks-string))

all subtasks-strings
encountered in the
deadlock

End Deadlock.
Readd (j)

```
Do
    l = pos (head of subtasks-string of j)
    by 1 until j-1

    if y(l) in subtasks-string of j.
        then
            for all k in Av(l)
                if σ(y(l),k) + d(y(l)) ≤ σ(k,l)
                and σ(j,i) + d(j) > σ(k,l)
                    then D(k,l) = D(k,l) - 1
                if D(k,l) = 0
                    then
                        add k to Av(l)
                        Suppress k from Av(l)
```
Bibliography

[BEL 71]
Bell C.G., Newell A.
Computer structures : Readings and examples
Mac Graw Hill (1971).

[CHA 74]
Challine J.F., Fischbach J.P.
Portability features in Bergson
SPECTRE internal report IA/106 (1974).

[CON 67]
Conway R.W., Maxwell W.L., Miller L.W.
Theory of scheduling
Addison Wesley (1967).

[DON 74]
Donzeau-Gouge V.
Thèse de 3e Cycle
Paris VI (1974).

[HAB 69]
Habermann A.N.
Prevention of system Deadlocks
Comm. A.C.M. Vol. 12, n° 7, pp. 373-385, (1969).

[HEL 62]
Heller J., Logemann G.
An algorithm for the construction and evaluation of
feasible schedules
Management and Science, Vol. 8, n° 2, pp. 168-183, (1962).

[HOL 71]
Holt R.C.
Comments on prevention of system Deadlocks.
Comm. A.C.M., Vol. 14, n° 1, pp. 36-38, (1971).

[LAB 74]
Labetoulle J.
Thèse de 3e Cycle.
Paris VI (1974).
Ordonnancement des processus temps reel sur une
ressource preemptive.
[MAR 59]
Marimont R.B.
A new method of checking the consistency of
précedence matrices.
Journal A.C.M., Vol. 6, n° 2, pp. 164-171, (1959).

[RAN 66]
Rand Corporation
Drezner S.M., Van Horn R.L.
Design considerations for CAMCOS
A computer assisted maintenance planning and control
system.
Rand Memorandum RM 5255 PR, (July 1967).

[ " ]
Geoffrion A.M.
Integer programming by implicit enumeration and Balas
method.
Rand Memorandum RM 4783 PR, (February 1966).

[ " ]
Geoffrion A.M.
Implicit enumeration using an imbedded linear program.
Rand Memorandum RM 5406 PR, (September 1967).

[ " ]
Geoffrion A.M.
An improved implicit enumeration approach for integer
programming.
Rand Memorandum RM 5644 PR, (June 1968).

[ " ]
Pritsker A.A.B., Watters L.J.
A 0/1 programming approach to scheduling with limited
ressources.
Rand Memorandum RM 5561 PR, (January 1968).

[ROD 73]
Rodriguez F.J., Challine J.F.
Structuration et communications dans un système d'exploi-
tation. SPECTRE internal report IA/109 .
To be published in
Journées IRIA : Structure résultant d'un groupement
de processeurs (Saint Pierre de Chartreuse FRANCE).
(22-23 Novembre 1973).
[SHR 70]

Shrage L.

Solving resource constrained network problems
by implicit enumeration. Non preemptive case.

Opns . Res., Vol. 18, pp. 263-278, (1970).

References.

[JOR 74]

Jorry A.

Version PL/1 d'ORDON.

IP/216. (May 74).