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

HAL
open science

# Application of penalty technique to solve a scheduling problem and comparison with combinatorial methods

Pierre Nepomiastchy

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

## To cite this version:

Pierre Nepomiastchy. Application of penalty technique to solve a scheduling problem and comparison with combinatorial methods. [Research Report] IRIA-RR-007, IRIA. 1973, pp.32. hal-04715925

HAL Id: hal-04715925

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

Submitted on 1 Oct 2024

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
Env: 0 1966

RRA

RIA
laboria

laboratoire de recherche
en informatique
et automatique

ARCHIVES

Application
of Penalty Technique
to Solve
a Scheduling Problem
and Comparison
with
Combinatorial Methods

32p

Pierre Nepomiastchy

Institut de Recherche
d'Informatique
et d'Automatique

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

Rapport de Recherche n° 7
Janvier 1973
APPLICATION OF PENALTY TECHNIQUE TO SOLVE A SCHEDULING PROBLEM
AND COMPARISON WITH COMBINATORIAL METHODS

Pierre NEPOMIASTCHY

ABSTRACT

The problem studied here is the "general n/m job-shop problem" in the terminology of CONWAY [1]. It is well known that this problem cannot be solved exactly using combinatorial methods for a large number of tasks, even using a very large computer. Here, by application of the penalty technique ([2] to[8]), we transform the scheduling problem into the minimization without constraints of a function of A + 1 real variables, where A is the number of tasks to schedule. This function is not convex, but we give an algorithm which is able to find a near-optimal solution in a small computational time, and we prove the convergence of the approximate method. Then, we compare our numerical results with those we have obtained using the branch-and-bound algorithm (see, for exemple, SAID ASHOUR [9]) applied to the same exemple.

Our algorithm is very economical in storage utilization
and its computational time grows approximately as $A^3$ (and not as
$A$ ! as in combinatorial methods). Therefore our algorithm will
be useful to obtain near-optimal solutions for scheduling problems :

a) when the user requires a small computational time and
accepts near-optimal solutions,

b) when the problem is too large for combinatorial methods,

c) when the computer used is limited in memory space.
# INTRODUCTION

We call scheduling problem the research of the optimal order in which one executes a given set of tasks (of given execution times) in order to minimize the total execution time. One particular order (not necessarily feasible) will be called a sequence. The number of tasks to schedule is A.

This kind of problem is generally solved using combinatorial methods which are all algorithms of path searching (in a more or less heuristic manner) in the graph of possible sequences. But the number of possible sequences is equal to $A!$ (greater than 3 millions for $A = 10$). Of course, the different constraints to the execution of tasks and the law of pathing used reduce considerably the number of sequences effectively studied by the combinatorial algorithms but, in any case, the computational time of exact combinatorial algorithms grows so quickly with the number of tasks that for large scheduling problems the techniques generally used are:

1) entirely heuristic methods (see, for exemple, MOISEEV [10]).

2) specific algorithms for particular situations (see one exemple in SAID ASHOUR [9]).

3) research of near-optimal solutions without results of convergence, that is without the possibility of improvement (see SAID ASHOUR [11]).

For these reasons, we try here to use non-combinatorial techniques to avoid the exponential growth of computational time, using the penalty technique which is exposed in Section II. Because of the non-convexity of the minimization problem obtained, we have some technical difficulties to solve it, but the number of variables of this problem is only $A + 1$ so we can consider larger scheduling problems.

In Section III, we expose the variant of the branch-and-bound algorithm we used for comparison, and in Section IV we compare the numerical results for the same concrete exemple.
# I. DESCRIPTION OF THE MODEL

We have to execute n jobs, each of them being composed of a(i) elementary tasks noted $O_{ij}$. The total number of elementary tasks is $A = \sum_{i=1}^{n} a(i)$.

To simplify further notations, let $I$ be the set of double indexes defined by :

$$I = \{\lambda / \lambda = \{i,j\}, j = 1,...; a(i), i = 1, ... n\}$$

We shall note an elementary task indifferently by $O_{ij}$ or $O_{\lambda}$

These elementary tasks are to be executed on m all distinct machines and one has to observe four technological rules :

**rule 1 :** the elementary task $O_{ij}$ can begin only if the elementary task (of the same job) $O_{i,j-1}$ is finished (for all $i = 1,..., n$, for all $j = 2,..., a(i)$), i.e. elementary tasks of the same job are strictly ordered.

**rule 2 :** the elementary task $O_{\lambda}$ can be executed only on one particular machine $k(\lambda)$, when $k(\lambda)$ is given, this for all $\lambda \in I$.

**rule 3 :** preemptions in the execution of elementary tasks are not allowed. The execution time $p_{\lambda}$ of each elementary task $O_{\lambda}$ is given and supposed independent of the task executed just before on the same machine.

**rule 4 :** at a given moment of time, a machine can execute only one elementary task.

A solution (or sequence) is said to be *feasible* if its execution respects these four rules. The problem is to find among the feasible solutions the shortest in total execution time.
MATHEMATICAL FORMULATION OF THE PROBLEM

Since the execution times of the elementary tasks are given and since a task can be executed only on one given machine, everything is known if we know the times $t_λ$, $λ∈I$, of beginning of execution of each elementary task. Furthermore, knowing the $t_λ$, we know not only the schedule (that is the order of execution of tasks) but also the complete planning of the execution of our jobs.

So it is natural to choose the A real variables $t_λ$ (with still $λ = \{ i,j \}$) as the variables of our problem. Note that, since $t_λ$ is the time of beginning of execution of the task $O_λ$, this task will end at the time $t_λ + p_λ$ with respect to the rule 3.

Then, we can write our problem in the following way :

Minimize T, where T is the total execution time given by :

$$ (1) \quad T = \max_{1 \le i \le n} [t_{i,a(i)} + p_{i,a(i)}] $$

where, by definition, $λ = \{i,a(i)\}$ is the double index denoting the last task of the job (i), so the quantity $t_{i,a(i)} + p_{i,a(i)}$ is the time of the end of execution of job (i) ;
under the constraints :

$$ (2) \quad t_λ \ge 0, λ \in I, \\ \text{(Where O is taken as the origin of time),} $$

$$ (3) \quad t_{ij} \ge t_{ij-1} + p_{i,j-1}, \quad j=2, \dots, n, \\ \text{(with respect to the rule 1),} $$

$$ (4) \quad [t_s \ge t_r + p_r] \quad \text{or} \quad [t_r \ge t_s + p_s], \quad \{s,r\} \in \mathbb{R}, \\ \text{(with respect to the rule 4), where } \mathbb{R} \text{ is the set of all } \{s,r\} \text{ such} \\ \text{as } s \in I, r \in I, s<r, k(s) = k(r). \text{ Indeed, if } k(s) = k(r), \text{ that is } O_s \\ \text{and } O_r \text{ are to be executed on the same machine, then there execution} \\ \text{cannot be simultaneous (see rule 4) and we must have either } O_s \\ \text{precedes } O_r \text{ or } O_r \text{ precedes } O_s. \text{ Restriction } s<r \text{ is available} \\ \text{because constraint (4) is symmetrical in s,r. This constraint is not} \\ \text{convex (the solution has to belong to the union of disjoint sets).} $$
To avoid minimax formulation, we shall consider T as a supplementary variable subject to the constraints :

$$ (5) \qquad T \ge t_{i,a(i)} + p_{i,a(i)} , \quad i = 1, \dots, n $$

Now, if we denote by $t$ the vector of the $t$, $\lambda \in I$, by $u$ the vector $u = \{t, T\}$, by $q$ the integer $A + 1$ (we have $u \in \mathbb{R}^q$), by $J(u)$ the criterion simply equal to $T$ (i.e. to the last component of $u$) and by $U$ the closed set of all $u \in \mathbb{R}^q$ satisfying constraints (2), (3), (4) and (5), then we can write our problem as a classical minimization problem : find $u \in U$ such that :

(6) **Problem P :**

$$ J(u) \le J(v) , \forall v \in U $$

For the following reasons :

a) $U$ is a subset of the finite-dimensionnal space $\mathbb{R}^q$, $U$ is closed in $\mathbb{R}^q$ and not empty (the schedule $t_{1,1} = 0$, $t_{1,2} = p_{1,1}$, $t_{1,3} = p_{1,1} + p_{1,2}$, ..., is always feasible) ;

b) $J(u)$ is continuous and bounded from below by zero because of (2) and (5).

we know that problem P has a solution but, because of the non-convexity of $U$, this solution is, in general, not unique.

There are many possible extensions of the given model for which the algorithm exposed in the paper can be applied. For more details, see 5. See also 4 for an application of the penalty technique to another kind of scheduling problem.

Further on, we shall always call problem P the "fundamental problem".
## II. APPLICATION OF THE PENALTY TECHNIQUE

The study of penalty technique in infinite dimensionnal spaces can be found :

1) for systems governed by linear partial differential equations (physical applications) : in LIONS [2] for the theory and in KENNETH, [3] for a concrete application.

2) for systems governed by ordinary differential equations (linear or not) with state constraints (applications to economics) in papers of the author : see [6] for the theory and [7] for a concrete application (to a stock problem) with comparison with other methods.

In finite dimensionnal spaces (as in this paper), the penalty technique is old and well known (see COURANT [8]), and we are going to see that the theory, i.e. proof of convergence, can be made even in the non-convex case.

### II. 1. Theory of the penalty technique

Let $\mathcal{B}$ be a closed and not empty set of the vector-space $\mathbb{R}^q$ and let $F(x)$ be a continuous mapping from $\mathbb{R}^q$ to $\mathbb{R}$ (i.e. a function of $q$ real variables).

It is supposed that $F(x)$ satisfies the following condition :

(7) if $||x|| \to \infty$, then necessarily $F(x) \to +\infty$
Here, and later, the norm $||\cdot||$ is the Euclidean norm of $\mathbb{R}^q$.
The fundamental problem is to find $x \in \mathcal{B}$ such that :

(8) Problem P :

$$F(x) \le F(y) \quad \forall y \in \mathcal{B}$$

As for problem (6), it is easy to prove the existence the solution of problem (8). Indeed, $F(x)$ is not bounded from below, but we have condition (7). But, since $\mathcal{B}$ and $F(x)$ are not supposed to be convex, in general this solution is not unique.
Now, let $G(x)$ be a continuous mapping from $R^q$ to $R$ satisfying the following conditions:

(9a) $G(x) \ge 0, \quad \forall x \in \mathbb{R}^q$

(9b) $G(x) = 0$ if and only if $x \in \mathcal{B}$

Any continuous mapping satisfying (9) will be called **penalty function** of the set $\mathcal{B}$. The following theorem can be proved (see the appendix) :

**Theorem 1** : If $\mathcal{B}$ is a closed set of the vector-space $\mathbb{R}^q$, then the following properties are true :

**Property 1** : There always exists at least one penalty function of the set $\mathcal{B}$.

**Property 2** : There exists a **convex** penalty function of $\mathcal{B}$ if and only if $\mathcal{B}$ is a convex set of $\mathbb{R}^q$.

**Property 3** : a) if the set $\mathcal{B}$ is defined by the relations :

$$u_i(x) \le 0, \quad i = 1, \dots, r; \quad v_i(x) = 0, \quad i = 1, \dots, s$$

where $u_i$ and $v_i$ are continuous mappings from $\mathbb{R}^q$ to $\mathbb{R}$;

b) if $\rho(t)$ is the scalar function of $t$ equal to $t^2$ if $t \ge 0$ and equal to zero if $t \le 0$;

Then the function :

$$G(x) = \sum_{i=1}^{r} \rho[u_i(x)] + \sum_{i=1}^{s} v_i^2(x)$$

is a penalty function of the set $\mathcal{B}$.

c) if the functions $u_i$ are all convex, and the functions $v_i$ are all linear, then the penalty function written above is convex.
**Property 4** : If $\mathcal{B} = \bigcup_{i=1}^{m} \mathcal{B}_i$ and $G_i(x)$ is a penalty function of $\mathcal{B}$ for every $i$, then :

$$G(x) = \prod_{i=1}^{m} G_i(x)$$

is a penalty function of $\mathcal{B}$.

**Property 5** : If $\mathcal{B} = \bigcap_{i=1}^{m} \mathcal{B}_i$ and $G_i(x)$ is a penalty function of $\mathcal{B}_i$ for every $i$, then :

$$G(x) = \sum_{i=1}^{m} G_i(x)$$

is a penalty function of $\mathcal{B}$.

Now, let $F_{\varepsilon}(x)$ be the mapping from $\mathbb{R}^q$ to $\mathbb{R}$ called "penalized criterion" and defined by :

$$(10) \qquad F_{\varepsilon}(x) = F(x) + \frac{1}{\varepsilon} G(x)$$
where $\varepsilon$ is a strictly positive parameter.

Finally, we can define the "penalized problem" $P_{\varepsilon}$ in the following way : find $x_{\varepsilon} \in \mathbb{R}^q$ such that :

$$(11) \qquad \text{Problem } P_{\varepsilon} : F(x) \le F(y), \forall y \in \mathbb{R}^q$$

Remarks on the problem $P_{\varepsilon}$ :

1) the problem $P$ is without constraints, so its solution is much easier than solution of problem $P$ (specially if some constraints of problem $P$ are "logical" like constraint (4)).

2) using (7), (9a) and $\varepsilon>0$, we know that $F_{\varepsilon}$ is bounded from below. Hence, since $F$ and $G$ are continuous, $F_{\varepsilon}$ is also continuous and the problem $P_{\varepsilon}$ has a solution (in general not unique).

3) because of Property 2 of Theorem 1, we know that if the problem $P$ is convex (i.e. $F$ convex mapping, $\mathcal{B}$ convex set), then the problem $P_{\varepsilon}$ is also convex (the penalty technique "preserves" convexity)
To formulate the convergence result for the penalized problem $\mathcal{P}$, we have to introduce $d(x)$, the Euclidean distance in $\mathbb{R}^q$ from $x$ to $\mathcal{B}$ as the solution of :

$$d(x) = \inf_{y \in \mathcal{B}} \|x-y\|$$

Note that $d(x)$ is a continuous function satisfying (9), so $d(x)$ is a penalty function of $\mathcal{B}$ (in general not the most convenient to choose).

Now, we can prove the following theorem (for the proof, see the appendix ; the result and its proof are not standard because of the non-uniqueness of the solution of the problem P) :

**Theorem 2** : let $x$ be any optimal solution of problem P and $x_{\varepsilon}$ be any optimal solution of problem $P_{\varepsilon}$. Then, when $\varepsilon \to 0$ with $\varepsilon > 0$, the following properties are true :

**Property 1** : the distance $d(x_{\varepsilon})$ from $x_{\varepsilon}$ to the set $\mathcal{B}$ of the feasible solutions of problem P converges to zero (i.e. $x_{\varepsilon}$ is asymptotically feasible) and $F(x_{\varepsilon})$, value of the criterion of problem P for the solution of problem $P_{\varepsilon}$, converges to $F(x)$, minimal value of $F$ on the set $\mathcal{B}$.

**Property 2** : the sequence $\{x_{\varepsilon}\}$ is the union of subsequences, each of which converges in $\mathbb{R}^q$ to one of the solutions of problem P.

**Property 3** : if the solution $x$ of the problem P is unique, then the whole sequence $\{x_{\varepsilon}\}$ converges in $\mathbb{R}^q$ to $x$.

## II. 2. Application of penalty technique to the scheduling problem.

First of all, we are going to write the constraint (4) in a more convenient form. Since the constants $p_{\lambda}$ are positive for all $\lambda \in I$, the events $t_s \ge t_r + p_r$ and $t_r \ge t_s + p_s$ (with $r \ne s$) are incompatible and the constraint (4) is equivalent to :

$$(12) \quad (t_s - t_r - p_r) (t_s - t_r + p_s) \ge 0, \quad \forall \{s,r\} \in \mathcal{A}$$
Unfortunately, the penalty technique described in II. 1. cannot be applied to the problem (6) because the criterion $J(u) = T$ (where T is the last component of vector u as before) does not satisfy condition (7). So we have to regularize our problem, defining a new criterion $J_\alpha(u)$ :

$$J_{\alpha}(u) = J(u) + \alpha \|u\|_{1}^{2} = T + \alpha \sum_{\lambda \in I} t_{\lambda}^{2} + \alpha T^{2}$$

where $\alpha$ is a strictly positive parameter.

**Remark :** the theory of II. 1. is developed in the general case. In fact, in the particular case of the scheduling problem studied in this paper, it can be proved that the method converges even if $\alpha = 0$ (the reason is that, if $\|u\| \to \infty$, then we may have $J(u) \to -\infty$ but we necessarily have $J_{\varepsilon}(u) \to +\infty$ for any $\varepsilon > 0$). We keep the criterion $J_{\alpha}(u)$ with $\alpha > 0$ because our experience shows that zero is not the value of $\alpha$ which gives the best numerical results.

Our fundamental problem is now the "regularized problem" $P_\alpha$: find $u_\alpha$ such that :

(13) **Problem P_α :**

$$J_{\alpha}(u) \le J_{\alpha}(v), \forall v \in \mathcal{B}$$

It is well known in regularization theory that the problem $P_\alpha$ converges to the problem $P$ as $\alpha$ tends to zero.

Looking at constraints (2), (3), (5) and (12) and using Property 3 of theorem 1, it is easy to prove that :

$$G(u) = \sum_{\lambda \in I} \rho(-t_{\lambda}) + \sum_{i=1}^{n} \rho \left[ t_{i,j-1}^{a(i)} + p_{i,j-1} - t_{ij} \right] \\ + \sum_{i=1}^{n} \rho \left[ t_{i,a(i)} + p_{i,a(i)} - T \right] + \\ + \sum_{\{s,r\} \in \mathcal{R}} \rho \left[ (t_s - t_r - p_r)(t_r - t_s - p_s) \right]$$
is a penalty function of our scheduling problem, where $\rho(t)$ is still
the function equal to $t^2$ if $t \ge 0$ and equal to zero if $t \le 0$.

The "regularized-penalized" criterion will then be :

$$
J_{\alpha\epsilon}(u) = J_{\alpha}(u) + \frac{1}{\epsilon} G(u),
$$

and the"regularized-penalized" problem P$_{αε}$ will be : find
u$_{αε}$ such that :

Problem P :

$$
J_{\alpha\epsilon}(u_{\alpha\epsilon}) \le J_{\alpha\epsilon}(v), \quad \forall v \in \mathbb{R}^q
$$

By application of theorem 2, we know that for small (but
strictly positive) values of α and ε, any solution of problem (14)
approximate a solution of the fundamental problem P. Note that
problem P<sub>αε</sub> is the <u>non-constrained</u> minimization of a twice
differentiable but non-convex function of q real variables.

## II. 3. Description of the algorithm

To solve the problem P<sub>αε</sub>, one can use any standard method
of non-constrained minimization. For the numerical exemple we have
chosen, we have found that the Fletcher-Powell algorithm [12] was
better than any gradient method. But this algorithm is rather
expensive in storage utilization : about q(q+9)/2 real numbers
are to be stored, where q is still the number of variables (q=A+1,
A is the number of tasks to schedule). For small computers (or large
scheduling problems), it will be probably better to use a gradient
method, for which storage is between 2q and 9q (depends on the method
used), than to use the Fletcher-Powell algorithm with overlays.

As usual in penalty technique, good results of convergence
can be obtained for small values of ε only if the initial solution
chosen is close to the optimal.
The natural (and well known) idea is then to solve the problem $P_{\alpha\epsilon}$ with the initial solution given by the user (if no solution is given by the user, we take $u_i=0$, $i=1, ..., q$) for a "big" $\epsilon_1$ ($\epsilon_1 = 1$ for example), then to take the solution of the problem $P_{\alpha\epsilon}$ as an initial solution for the problem $P_{\alpha\epsilon_2}$ with $\epsilon_2$ smaller $\epsilon_1$ then $\epsilon_1$, and so on. The law of variation of $\epsilon$ generally chosen is $\epsilon_{n+1} = \rho \epsilon_n$, with $0 < \rho < 1$.

But, in fact, we do not need the exact solution of problem $P_{\alpha\epsilon}$ for big values of $\epsilon$, so it is useless to make a great number of iterations for each problem. We obtained our best results making *one* iteration of the Fletcher-Powell algorithm and choosing a "slow" law of variation of $\epsilon$, that is $\rho$ near to 1. In our case, the best value of $\rho$ was 0.9 but, if $q$ increases, the best value of $\rho$ also increases. For the efficiency of the algorithm, it is then better to use only *once* the Fletcher-Powell Subroutine but changing $\epsilon$ *at each iteration*.

Because of the non-convexity of the problem $P_{\alpha\epsilon}$, we converge generally (in fact, nearly always) to a *local* optimum of the problem. This local optimum depends on the initial solution $u_0$, on the law $\epsilon_{n+1} = \rho \epsilon_n$ and is characterized by the execution time $T(u_0)$ of the corresponding schedule. For some choices of $u_0$ and $\rho$ (generally for small values of $\rho$, that is for "fast" laws), we may even have a numerical divergence of the penalty technique (a control test on $G(u_\epsilon)$ stops the program in this case) and the solution found may be unfeasible : we then put $T(u_0) = +\infty$.

But the main thing to note is that we found that the computational time necessary to find a local optimum is almost negligible compared with the computational methods (see numerical results in Section IV). So we can, preserving the competivity of our method, solve a great number of times the problem with different initial solutions $u_0$.

A natural idea is then to choose randomly $K$ initial solutions $u_0^k$ independent in probability.
The most simple is to take the $u_{io}^k$, $i = 1, ..., q$ as independent random variables uniformly distributed on $[0, 1]$ where $\hat{T}$ is the execution time of a feasible schedule, but this random choice can be helped by the intuition of the user. Then, we solve the problem using each of these $K$ initial solutions and we keep only the best (i.e. the one for which $T(u_0)$ is the smallest) of the schedules obtained.

Since the number of local optima is bounded, it is easy to prove that the probability to obtain the absolute optimum (that is the optimal schedule) using this technique converges to 1 when $K \to \infty$, so we have once more a "convergent technique". In fact, our numerical experience shows that, on the average, a "rather good" solution is obtained very quickly but a "very good" solution requires a very large $K$.

### 11, 4. Modification of the method

The basic idea of the modification we are going to expose is that in concrete problems the execution times $p_\lambda$ of the elementary tasks are known only with a certain accuracy $\Delta t$. Is other words, we suppose that there exists a strictly positive number $\Delta t$ such as the times $p_\lambda$ are all multiples of $\Delta t$. Then, changing the unit of time by a division of all the $p_\lambda$ by $\Delta t$ (where, of course, $\Delta t$ is taken as large as possible), we obtain an equivalent scheduling problem where all the execution times have *integer* values, and the total execution time of any schedule is also an integer.

Suppose now we know a feasible schedule with a certain integer execution time $T_0$. Then, we are interested only in the local optima which give feasible schedules better than this one, that is with an execution time strictly less than $T_0$, that is less than or equal to $T_0-1$.

Let $\mathcal{B}(\hat{T})$ be the subset of $\mathbb{R}^A$ (where $A$ is still the number of elementary tasks) defined by the inequalities:
$$
(14 \text{ a}) \quad t_{\lambda} \ge 0, \quad \lambda \in I
$$

$$
(14 \text{ b}) \quad t_{ij} \ge t_{i,j-1} + p_{i,j-1}, \quad i = 1, \dots, n, \quad j = 2, \dots, a(i)
$$

$$
(14 \text{ c}) \quad (t_s - t_r - p_r) (t_s - t_r + p_s) \ge 0, \quad \{s,r\} \in \mathbb{R}
$$

$$
(14 \text{ d}) \quad t_{i,a(i)} + p_{i,a(i)} \le \hat{T}, \quad i = 1, \dots, n
$$

where $\hat{T}$ is not an auxiliary variable as before, but a
parameter. By construction, $\mathcal{B}(\hat{T})$ is the set of feasible schedules
with a total execution time less than or equal to $\hat{T}$. We define now
a new problem, the problem $P(\hat{T})$: find any element of the set $\mathcal{B}(\hat{T})$.
Let $F(t)$ be the mapping from $\mathbb{R}^A$ to $\mathbb{R}$ defined by :

$$
F(t) = \sum_{\lambda \in I} \rho(-t_{\lambda}) + \sum_{i=1}^{n} \sum_{j=2}^{a(i)} \rho[t_{i,j-1} + p_{i,j-1} - t_{ij}] + \sum_{\{s,r\} \in \mathcal{R}} \rho[(t_s - t_r - p_r)(t_r - t_s - p_s)] + \sum_{i=1}^{n} \rho[t_{i,a(i)} + p_{i,a(i)} - \hat{T}]
$$

By construction, $F(t)$ is a penalty function of the set
$\mathcal{B}(\hat{T})$, that is :

$$
F(t) \ge 0, \forall t \in \mathbb{R}^A ; \quad F(t) = 0 \quad \text{if and only if} \quad t \in \mathcal{B}(\hat{T})
$$

The solution of the problem $P(\hat{T})$ is the research of a zero
of $F(t)$ but, since, from (16), we see that zero is also the minimum
value of $F(t)$ on the whole space $\mathbb{R}^A$, it is more convenient to mini-
mize (without constraints) $F(t)$. Hence, we solve the problem :
find $\hat{t} \in \mathbb{R}^A$ such that :

$F(\hat{t}) \le F(t), \forall t \in \mathbb{R}^A$

By construction, any solution of (17) is a feasible
schedule with an execution time less than or equal to T̂.

Remarks :

1) it is not necessary to solve the problem (17) with a great accuracy because we know that any solution is an integer vector. Since the minimum value of F(t) is zero, since F(t) is the sum of the positive terms (15), as soon as we get F(t) < 0.25, we are sure
that any component of the solution is approximate with an error less
than 0.5 and, taking the nearest integer value for each component,
we obtain the *exact solution*.

2) $\epsilon$ does not appear in the problem (17) and we have no
trouble about the law of variation of $\epsilon$. Furthermore, the solution
found is not asymptotically feasible as before but **strictly** feasible.

3) $F(t)$ is non-convex as before and we still may converge
to a local optimum. But, here, we can very easily distinguish local
and absolute minima : the minimum $t$ is absolute if and only if $F(t)=0$.

Description of the algorithm

**Step 0** : If the user can give a feasible schedule of execution time $T_0$, we put $\hat{T} = T_0 - 1$, otherwise we put $\hat{T} = \sum_{\lambda \in I} p_\lambda - 1$ since we know that the"natural" schedule has an execution time of $\sum_{\lambda \in I} p_\lambda$.

**Step 1** : We randomly choose an initial (not necessarily feasible) schedule to start the minimization of $F(t)$. This random choice is made as in Section II. 3. The minimization is stopped either if $F(t)$ becomes less than 0.25 (convergence to an absolute minimum of problem (17) ; go to step 2) or if the gradient of $F(t)$ becomes too small (convergence to a local minimum of problem (17) ; return to step 1 with another initial schedule).

**Step 2** : We have found a feasible schedule with execution time $T \le \hat{T}$. We put $\hat{T} = T-1$ and we return to step 1.

Remarks :

1) the random choice of initial solution at step 1 can be
improved by using the following trick. Since the computational time
of the calculation of F(t) is negligible compared with the computa-
tional time of the minimization of F(t), we randomly choose k sche-
dules t₁, t₂, ..., tₖ, we compute F(t₁), F(t₂),..., F(tₖ) and we start
from the solution tᵢ which gives the smallest value F(tᵢ).
2) when $\hat{T}$ decreases, the problem $P(\hat{T})$ becomes more and more difficult to solve, that is the number of times we apply step 1 with the same $\hat{T}$ increases. Furthermore, the problem $P(\hat{T})$ has a solution if and only if $\mathcal{B}(\hat{T})$ is not empty, that is if and only if then exists at least one feasible schedule with an execution time $T \le \hat{T}$, that is if and only if $\hat{T} \ge T^*$ where $T^*$ is the execution time of an optimal schedule of our fundamental problem $P$. Suppose now that we have found an optimal schedule; then, passing by step 2, we put $\hat{T} = T^* - 1$ and we try to solve an *impossible* problem (to find a schedule better than the optimal), i. e. we are going to cycle infinitely on step 1. Unfortunately, since $T^*$ is unknown, this is impossible to avoid. The user must give number $N$ such that if the program passes $N$ times by step 1 without any change of $\hat{T}$, then it stops. $N$ depends on the quality of the schedule required by the user and on the expense in computing time he accepts.
### III. APPLICATION OF COMBINATORIAL METHODS

#### III. 1. The Manne's model

Using the technique of A.S. MANNE [13], we are going to write the scheduling problem as a MLP (mixed linear program, i.e. a linear program with real and integer variables). For that, let $Y_{sr}$ be an array of new auxiliary variables which are restricted to take only the values 0 or 1 and which are defined for all $\{s, r\} \in \mathcal{R}$. Then, the fundamental problem (6) can be formulated (see [1]) as the following MLP :

Under the constraints :

$$18a) \quad t_{\lambda} \ge 0, \quad \lambda \in I$$

$$18b) \quad t_{ij} \ge t_{i,j-1} + p_{i,j-1}, \quad i = 1, \dots, n, \quad j = 2, \dots, a(i)$$

$$18c) \quad T \ge t_{i,a(i)} + p_{i,a(i)}, \quad i = 1, \dots, n$$

$$18d) \quad (M+p_r) Y_{sr} + t_s \ge t_r + p_r, \quad \{s,r\} \in \mathcal{R}$$

$$18e) \quad (M + p_s) (1 - Y_{sr}) + t_r \ge t_s + p_s, \quad \{s,r\} \in \mathcal{R}$$

$$18f) \quad Y_{sr} = 0 \quad \text{or} \quad Y_{sr} = 1, \quad \{s,r\} \in \mathcal{R}$$

Minimize the criterion :

$$19) \quad J(t,T,Y) = T,$$

where $M = \sum_{\lambda \in I} p_\lambda$. Indeed, if $Y_{sr} = 0$, then (18d) becomes $t_s \ge t_r + p_r$ and (18e) is always satisfied (as, obviously, $t_\lambda \le M$, $\forall \lambda \in I$); if $Y_{sr} = 1$, then (18d) is always satisfied and (18e) becomes $t_r \ge t_s + p_s$. Finally, we see that constraints (18d), (18e) and (18f), altogether, are equivalent to constraint (4).

One method to solve this M.L.P. is DRIEBECK'S algorithm (see, for example, [14]). Unfortunately, our experience proves that this algorithm is effective only if the solution of the CLP
(continuous linear program, i.e. problem (18) - (19) where we "forget" about constraint (18f)) is sufficiently close to the optimal solution of the MLP to give useful information about it. Here, the solution of the CLP is obvious ($t_{il} = 0$; $t_{ij} = \sum_{s=1}^{j} p_{is}$, $j>1$) and does not give any useful information. Anyway, whatever the algorithm chosen to solve the MLP, the size of Manne's model (specially the number of constraints) does not allow us to consider problems with more than 15-20 elementary tasks (see [1]).

### III. 2. The branch-and-bound algorithm

The best combinatorial method we know to solve scheduling problems is the branch-and-bound algorithm (see, for example [9] and [11]).

We consider now the integer variables of Manne's model as parameters. At the level $k$ of the algorithm, the first $k$ integers $Y_{sr}$ (after a suitable numerotation) have fixed values, either 0 or 1, that is we have chosen a priori the order in which tasks $O_s$ and $O_r$ will be executed. If we have chosen $Y_{sr} = 0$, then constraints (18d), (18e) and (18f) are replaced by the unique constraint $t_s \ge t_r + p_r$, otherwise they are replaced by $t_r \ge t_s + p_s$. For the further values of $\{s,r\}$, constraints (18d), (18e) and (18f) are simply delayed.

For the linear program corresponding to the level $k$ of the algorithm, the number of variables is now $q = A+1$ and the number of constraints is $2A+k$, where $1 \le k \le \text{Card}(\mathcal{R})$. We see that the size of the linear programs to be solved is much smaller than in Manne's model.

The algorithm can be very much improved if we take care of the fact that the $Y_{sr}$ are not independent. Indeed, if we have chosen $Y_{sr} = 0$, that is $O_s$ must be executed after $O_r$, and $Y_{rt} = 0$, that is $O_r$ must be executed after $O_t$, then the choice $Y_{st} = 1$, that is $O_s$ must be executed before $O_t$, is impossible (the corresponding linear program has no solution).
Taking care of all these *transitivity* relations we can a priori eliminate a very great number of nodes of the tree of values of Y and all the branches starting from these nodes.

Using the branch-and-bound algorithm, we obtain the *absolutely* optimal solution but, even if the initial schedule is good, even taking care of transitivity, the computational time is large and grows very quickly with the number of tasks.

One can use in a "short" computational time a modification of the branch-and-bound algorithm [11] which gives a near-optimal solution. Here, at each level of the algorithm, we try $Y = 0$, then $Y = 1$ (if both are compatible with transitivity relations), we keep the best of the two solutions obtained and we go down in the tree ($k := k + 1$). We shall call this "algorithm of direct descent". This algorithm is not an algorithm of successive approximations like in penalty technique because when we are at the bottom of the tree, that is $k = \text{Card } \mathcal{Y}$, we do have a feasible schedule (generally a rather good one) but without any possibility to improve it. The quality of this schedule depends only on the completely artificial indexing of the integers $Y_{sr}$.
## IV. NUMERICAL RESULTS

We tested the methods described above on a simple example of 5 jobs with 16 elementary tasks (A = 16) executed on 3 machines. The whole data of the problem can be summarised on Fig. 1 :

<figure><img src="image_4.png" /><figcaption>- Figure 1 -</figcaption></figure>

This schedule (of length 12) is of course infeasible (see Rule n° 1) but gives all the data needed : $p_{1,3} = 1$, $p_{2,2} = 2$, $p_{3,2} = 3, \dots$, $k(1,3) = 1$ (task $O_{1,2}$ is executed on machine 1), $k(4,4) = 2, \dots$, $a(1) = 3$ (job (1) is composed of 3 elementary tasks), $a(2) = 4, \dots$

There are 1404 feasible schedules and here is of the optimal ones (also of length 12) :

<figure><img src="image_5.png" /><figcaption>- Figure 2 -</figcaption></figure>

To appreciate the quality of the methods tested, we define what we call the "optimization power" (in per cent) of a method by
P = 100 $T^*/T$, where $T^*$ is the length of an optimal schedule (here, $T^*=12$) and T is the length of the schedule found by the method. So, if the schedule found is optimal, then P =100, if it is twice longer than an optimal, then P = 50 and so on.

The methods were tested using FORTRAN IV on CII 10070.

We have made a large number of tests because the variance
of the quality of results is big (except for method 5). In Fig. 3,
we give the average computational time necessary to obtain given
optimization power using 6 different methods. Computation time "infi-
nity" implies that this optimisation power was not obtained using
this method.
<table><thead><tr><th>Optimization<br>Power</th><th>Method 1</th><th>Method 2</th><th>Method 3</th><th>Method 4</th><th>Method 5</th><th>Method 6</th></tr></thead><tbody><tr><td>75</td><td>3 min. 20 sec.</td><td>7.5 sec.</td><td></td><td>1 hour</td><td>5 min.</td><td>5 min.</td></tr><tr><td>80</td><td>7 min. 20 sec.</td><td>18.3 sec.</td><td>2.5 sec.</td><td>1 hour 10 min.</td><td>5 min.</td><td>5 min.</td></tr><tr><td>85</td><td>18 min. 30 sec.</td><td>22.4 sec.</td><td>6.6 sec.</td><td>1 hour 13 min.</td><td>5 min.</td><td>5 min.</td></tr><tr><td>92</td><td>1 hour 15 min.</td><td>1 min. 12 sec.</td><td>57.2 sec.</td><td>1 hour 20 min.</td><td>Infinity</td><td>11 min.</td></tr><tr><td>100</td><td>Infinity</td><td>Infinity</td><td>Infinity</td><td>1 hour 22 min.</td><td>Infinity</td><td>16 min.</td></tr></tbody></table>

- Fig. 3 -
*Method 1*: classical penalty technique exposed in Section II. 3.

*Method 2*: modified penalty technique exposed in Section II. 4 when it is supposed that the user does not know any feasible schedule.

*Method 3*: same as method 2 but a 75 feasible schedule is given by the user.

*Method 4*: branch-and-bound algorithm (taking care of transivity relations) exposed in Section III. 2 when the user does not give any feasible schedule.

*Method 5*: "direct-descent" modification of branch-and-bound exposed in Section III. 2. The average optimization power obtained is 87 and the computational time is always 5 minutes.

*Method 6*: method 5 is used to find a"good" schedule, then this schedule is improved by method 4.

The results given in Fig. 3 are of course simply indicative because only the numerical exemple described in Fig. 1 was tested. But the difference which appears in the computational times of the different methods is so great that we think that our numerical results are significant.

We have made some tests for an exemple with 40 elementary tasks. For this case, any combinatorial technique described above needs several hours of the CII 10070 and was not tested, but the method 2 gave the following results :
<table><caption>- Fig. 4 -</caption><thead><tr><td>Optimization Power</td><td>Computational time</td></tr></thead><tbody><tr><td>62</td><td>15 sec.</td></tr><tr><td>72</td><td>50 sec.</td></tr><tr><td>75</td><td>4 min. 10 sec.</td></tr><tr><td>78</td><td>14 min. 30 sec.</td></tr><tr><td>80</td><td>19 min. 5 sec.</td></tr><tr><td>82</td><td>22 min. 50 sec.</td></tr></tbody></table>

## CONCLUSION

The first conclusion which appears clearly is that methods 1 and 4 are not competitive (they are exposed in this paper only to introduce methods 2,5 and 6). To obtain a "good" schedule (at 90 for example of Fig. 3) the best method is the "modified penalty technique" exposed in Section II. 4 but "very good" schedules (more than 95 in the same exemple) are obtained in a very great computational time.

To obtain the absolute optimum, the best method seems to be method 6 but it will probably be better to find a "good" schedule using the penalty technique (method 2) then to improve it using the branch-and-bound algorithm (method 4).

Anyway, we think that for a great number of tasks, where combinatorial methods are completely impossible to use (except the heuristic ones), the penalty technique will be able to give near-optimal solutions and that is the reason why we are actually working on the application of the penalty technique to more complicated (and more realistic) models than the example given here for the purpose of comparison.
R E F E R E N C E S

====================

[1] R. W. CONWAY, W.L. MAXWELL, L.W. MILLER "Theory of scheduling" Addison Wesley, 1967

[2] J.L. LIONS "Contrôle optimal des systèmes gouvernés par des équations aux dérivées partielles" Dunod, Paris, 1968.

[3] P. KENNETH, M. SIBONY, J.P. YVON "Penalization techniques for optimal control problems governed by partial differential equations" Comp. Methods in Optimization Problems, 2, 177-186, New-York (1969). See also J.P. YVON, Publ. IRIA, oct. 1968.

[4] P. NEPOMIASTCHY "Application of the optimal control theory with penalty technique to a scheduling problem" (in russian). Zurnal Vyc. Mat. i Mat. Fiz., t10, 4, 1970 (Moscow).

[5] P. NEPOMIASTCHY "Résolution d'un problème d'ordonnancement à l'aide de la méthode de pénalisation et comparaison avec des méthodes combinatoires" Publ. LABORIA (IRIA), Sept. 1972.

[6] P. NEPOMIASTCHY "Méthode de pénalisation pour les systèmes gouvernés par des équations différentielles avec contraintes sur l'état du système" Publ. LABORIA (IRIA), Oct. 1972.

[7] C. LEMARECHAL, P. NEPOMIASTCHY, G. NISSEN "Comparaison de méthodes d'optimisation de gestion de stocks-production" Cahier IRIA, n° 9, t. 1, pp 101 - 181, Mars 1972.

[8] R. COURANT "Variational methods for the solution of problems of equilibrium and vibrations" Bull. Amer. Math. Soc. 49 (1943) pp 1.23.

[9] SAID ASHOUR "A branch-and-bound algorithm for flow shop scheduling problems". Industrial Engineering Research and Development, v2, n° 2, 6, 1970.
[10] N.N. MOISEEV "Numerical Methods in theory of optimal systems" (in russian). Izd. Nauka, Moscow, 1971.

[11] SAID ASHOUR, R.G. PARKER "A precedence graph algorithm for the shop scheduling problem" Operational Research Quarterly, v 22, n° 2, pp 165.175.

[12] R. FLETCHER, M.J.D. POWELL "A Rapidly Convergent Descent Method for Minimization" Computer Journal, vol 6, iss 2, 1963, pp 163.168.

[13] A. S. MANNE "On the job-shop scheduling problem" Operation Research, 8, 2, 1960, pp 219.223.

[14] R. TREMOLIERES "Programmation linéaire en variables mixtes ; la méthode de Driebeck" Bull Metra-France (Jan. 1968).
APPENDIX

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

PROOF OF THEOREM 1 (PROPERTIES OF PENALTY FUNCTIONS)

Proof of property 1 :

Let $d(x)$ be the distance in $\mathbb{R}^q$ from $x$ to the set $\mathcal{B}$ defined by :

(20)

$$
d(x) = \inf_{y \in \mathcal{B}} \|x-y\|
$$

Since $\mathcal{B}$ is supposed to be a closed set of the vector-
space $\mathbb{R}^q$, $d(x)$ is a continuous function of $x$. $d(x)$ obviously
satisfies the relations (9), so $d(x)$ is a penalty function of $\mathcal{B}$
and property 1 is proved.

Proof of property 2 :

1) Let us suppose that the set $\mathcal{B}$ is convex and let us prove that $d(x)$ is then convex. Let $x_1$ et $x_2$ be arbitrary points of $\mathbb{R}^q$. As $\mathcal{B}$ is closed, there exist two points $y_1$ and $y_2$ of $\mathcal{B}$ such that $d(x_1) = \| x_1 - y_1 \|$ and $d(x_2) = \| x_2 - y_2 \|$.

Let $\lambda$ be an arbitrary number such that $\lambda \in [0,1]$ and
$\hat{x}$ and $\hat{y}$ be the points defined by $\hat{x} = \lambda x_1 + (1-\lambda) x_2$,
$\hat{y} = \lambda y_1 + (1-\lambda) y_2$. Since $\lambda$ and $1-\lambda$ are positive numbers, we have :

$$
\lambda d(x_1) + (1-\lambda) d(x_2) = \|\lambda(x_1 - y_1)\| + \| (1-\lambda) (x_2 - y_2)\|
$$

Using the triangle inequality, we obtain :

(21)

$$
\lambda d(x_1) + (1-\lambda) d(x_2) \ge \|\lambda(x_1 - y_1) + (1-\lambda)(x_2 - y_2)\| = \|\hat{x} - \hat{y}\|
$$

But since $y_1 \in \mathcal{B}$, $y_2 \in \mathcal{B}$ and $\mathcal{B}$ is convex, we know that $\hat{y} \in \mathcal{B}$ so, using the definition (20), we obtain $\|\hat{x}-\hat{y}\| \ge d(\hat{x})$ and, since $x_1, x_2$ and $\lambda$ are arbitrary, (21) implies that $d(x)$ is convex.
2) Let us now suppose that $G(x)$ is a convex penalty function of the set $\mathcal{B}$ and let us prove that, in this case, $\mathcal{B}$ is necessarily a convex set.

Now, $x_1$ and $x_2$ are arbitrary points of $\mathcal{B}$, $\lambda$ is still an arbitrary number with $\lambda \in [0,1]$ and we have to prove that $\hat{x} = \lambda x_1 + (1-\lambda) x_2$ belongs to $\mathcal{B}$. Indeed, as $G(x)$ is convex, we have :

$$ (22) \qquad G(\hat{x}) \le \lambda G(x_1) + (1-\lambda) G(x_2) $$

Since $G(x)$ is a penalty function of $\mathcal{B}$, since $x_1 \in \mathcal{B}$ and $x_2 \in \mathcal{B}$, using (9b) we obtain from (22) that $G(\hat{x}) \le 0$ then, using (9a), we obtain that $G(\hat{x}) = 0$ then, using once more (9b), we obtain $\hat{x} \in \mathcal{B}$ and property 2 is proved.

**Proof of property 3 :**

The function $G(x)$ defined in property 3 is obviously a penalty function of $\mathcal{B}$. To prove that if all the $u_i$ are convex and all the $v_i$ are linear, then $G$ is convex, the only difficulty is to prove that if $f(x)$ is a convex function of $x$, $x \in \mathbb{R}^q$, if $h(x) = \rho[f(x)]$, then $h(x)$ is also a convex function of $x$ (note that for $\rho(t) = t^2$, $\forall t$, this is false).

Let $x_1$ and $x_2$ by arbitrary points of $\mathbb{R}^q$, $\lambda$ be an arbitrary number with $\lambda \in [0,1]$, and let us take the following notations :
$$ \hat{x} = \lambda x_1 + (1-\lambda) x_2, \quad f_1 = f(x_1), \quad f_2 = f(x_2), \quad \hat{f} = f(\hat{x}), \quad h_1 = h(x_1), $$
$$ h_2 = h(x_2) \quad \text{and} \quad \hat{h} = h(\hat{x}). \quad \text{We know that } \hat{f} \le \lambda f_1 + (1-\lambda) f_2 \quad \text{and we have to prove that } \hat{h} \le \lambda h_1 + (1-\lambda) h_2. $$

We consider separately each case : $f_1 > 0$ or $f_1 \le 0$, $f_2 > 0$ or $f_2 \le 0$ and $\hat{f} > 0$ or $\hat{f} \le 0$ and we obtain very easily the result for each of these 8 cases except for $f_1 > 0$, $f_2 > 0$, $\hat{f} > 0$. In this case, we have to prove that $\hat{f}^2 \le \lambda f_1^2 + (1-\lambda) f_2^2$. Since we know that $f_1 > 0$, $f_2 > 0$, $\hat{f} > 0$, from $\hat{f} \le \lambda f_1 + (1-\lambda) f_2$ we obtain $\hat{f}^2 \le [\lambda f_1 + (1-\lambda) f_2]^2$ as $\lambda$ and $1-\lambda$ are also positive.
So, it is enough to prove that the quantity $A = \lambda f_1^2 + (1-\lambda) f_2^2 - [\lambda f_1 + (1-\lambda) f_2]^2$ is positive. Indeed, we find $A = \lambda(1-\lambda) (f_1 - f_2)^2$ and, since $\lambda \in [0, 1]$, property 3 is proved.

Using the relations (9a) and (9b) we prove very easily properties 4 and 5.

## PROOF OF THEOREM 2 (CONVERGENCE OF THE PENALTY TECHNIQUE)

Using definition (8) of problem P, we have $x \in \mathcal{B}$, so $x \in \mathbb{R}^q$ and, from definition (11) of problem $P_\epsilon$, we get:

$$F_{\epsilon}(x_{\epsilon}) \le F(x), \quad \forall \epsilon > 0$$

But, since $x \in \mathcal{B}$, we obtain from (9b) that $G(x) = 0$ and from (10) that $F_\epsilon(x) = F(x)$, so we have the inequality:

$$F_{\epsilon}(x_{\epsilon}) \le F(x), \quad \forall \epsilon > 0$$

(23)

But, from (9a) and (10), we know that $F(y) \ge F(y)$, $\forall y \in \mathbb{R}^q$, $\forall \epsilon > 0$. Then, from (23) we deduce that $F(x_\epsilon)$ is bounded from above for every $\epsilon > 0$. Using condition (7) we obtain that $x_\epsilon$ is a bounded vector of $\mathbb{R}^q$ for every $\epsilon > 0$.

Let $\{x_\epsilon\}$ be the sequence such that, for every $\epsilon > 0$, $x_\epsilon$ is one particular (but arbitrary) optimal solution of problem $P_\epsilon$. We know that there exist a closed and bounded set $S$ in $\mathbb{R}^q$ such that the sequence $\{x_\epsilon\}$ is included in $S$. Since in vector-spaces bounded and closed sets are compact, we can extract from the sequence $\{x_\epsilon\}$ a subsequence $\{x_\eta\}$ converging in $\mathbb{R}^q$ to a certain element $z$.

First, we are going to prove that $z \in \mathcal{B}$, i.e. that $z$ is feasible. Indeed, using (10) and (23), we get:

$$F(x_{\epsilon}) + \frac{1}{\epsilon} G(x_{\epsilon}) \le F(x), \quad \forall \epsilon > 0$$

(24)
Hence we have (using (9a)) :

$$0 \le G(x_{\epsilon}) < \epsilon [F(x) - F(x_{\epsilon})], \quad \forall \epsilon > 0$$

Since $x_{\epsilon}$ is bounded in $\mathbb{R}^q$ and $F$ is continuous, we know that $F(x_{\epsilon})$ is also bounded from below and we obtain :

$$\lim_{\epsilon \to 0} G(x_{\epsilon}) = 0$$

Since $G$ is continuous, for the convergent sequence $\{x_{\eta}\}$ we have :

$$0 = \lim_{\eta \to 0} G(x_{\eta}) = G\left(\lim_{\eta \to 0} x_{\eta}\right) = G(z)$$

Hence, using (9b), we get $z \in \mathcal{B}$.

From (24) and (9a) we have :

$$F(x_{\epsilon}) \le F(x), \quad \forall \epsilon > 0$$

Since $F$ is continuous, we then obtain for the convergent sequence $\{x_{\eta}\}$ :

$$F(z) \le F(x)$$

But $x$ is an optimal solution of problem P, that is $F(x)$ is the minimum value of function $F$ on the set $\mathcal{B}$ so, since $z \in \mathcal{B}$, we have $F(x) = F(z)$ and $z$ is also an optimal solution of problem P, and we get :

(25)

$$\lim_{\eta \to 0} F(x_{\eta}) = F(x)$$

On the other hand, by definition of the distance $d(x)$, we have, since $z \in \mathcal{B}$ :

$$0 \le d(y) \le \|z-y\|, \quad \forall y \in \mathbb{R}^q$$

So, for the convergent sequence $\{x_{\eta}\}$, we obtain (since $d$ is continuous) :
(26)

$$ \lim_{\eta \to 0} d(x_\eta) = 0 $$

From the subsequence {$x_\epsilon$} - {$x_\eta$} we can extract an other convergent subsequence and do the same argument and so on until the complete vanish of the sequence {$x_\epsilon$}. Since limits (25) and (26) do not depend on the manner the subsequence was extracted, we obtain these limits for the whole sequence {$x_\epsilon$} :

$$ \lim_{\epsilon \to 0} F(x_\epsilon) = F(x) ; \quad \lim_{\epsilon \to 0} d(x_\epsilon) = 0 $$

Which proves property 1. Since each of the subsequences extracted converges to optimal solutions of problem P, property 2 is also proved.

If the solution of problem P is unique, all these subsequences have the same limit and the whole sequence {$x_\epsilon$} converges to this solution, which ends the proof of theorem 2.