%% LyX 1.3 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[english,frenchb]{amsbook}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{a4wide}
\setlength\parskip{\smallskipamount}
\setlength\parindent{0pt}
\usepackage{graphicx}
\usepackage{amssymb}

\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
%% Because html converters don't know tabularnewline
\providecommand{\tabularnewline}{\\}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
 \numberwithin{section}{chapter}
 \theoremstyle{plain}    
 \newtheorem{thm}{Theorem}[section]
 \numberwithin{equation}{section} %% Comment out for sequentially-numbered
 \numberwithin{figure}{section} %% Comment out for sequentially-numbered
 \theoremstyle{definition}
  \newtheorem*{xca*}{Exercice}
 \theoremstyle{definition}
  \newtheorem*{example*}{Exemple}
 \theoremstyle{definition}
 \newtheorem*{defn*}{Définition}
 \theoremstyle{definition}
  \newtheorem{xca}{Exercice}
 \theoremstyle{plain}    
 \newtheorem{algorithm}[thm]{Algorithme} %%Delete [thm] to re-start numbering
 \theoremstyle{remark}
 \newtheorem*{rem*}{Remarque}
 \theoremstyle{definition}
  \newtheorem*{problem*}{Problème}
 \theoremstyle{plain}    
 \newtheorem*{thm*}{Théorème} 
 \theoremstyle{plain}    
 \newtheorem*{lem*}{Lemme} %%Delete [thm] to re-start numbering
 \theoremstyle{plain}    
 \newtheorem*{prop*}{Proposition} 
 \theoremstyle{remark}    
 \newtheorem{notation}[thm]{Notation} 
 \theoremstyle{remark}
 \newtheorem{rem}[thm]{Remarque}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\usepackage{hyperref}
\usepackage[english,francais]{babel}
\makeatletter
% Yucky bugware to make hyperref and babel[francais] work together
\def\url#1{{\selectlanguage{english}\hyper@normalise\url@{#1}}}
\def\href#1#2{{\selectlanguage{english}\hyper@normalise\href@{#1}{#2}}}
\makeatother
\newcommand{\solution}{ \vspace{2cm}}

\usepackage[english,francais]{babel}
\makeatother
\begin{document}

\chapter{Ordonnancement}


\section{Étude de cas \protect \\
Ordonnancement de tâches avec contraintes de précédences}


\subsection{Exemple: construction d'une maison}

\begin{xca*}
On veut construire une maison, ce qui consiste en $9$ tâches, le
plus rapidement possible, avec les contraintes suivantes:
\begin{itemize}
\item Certaines tâches dépendent d'autres tâches
\item Toutes les tâches demandent une semaine de travail.
\item Chaque ouvrier ne peut travailler que sur une tâche par jour
\item Il n'y a pas de gain de temps si plusieurs ouvriers travaillent sur
la même tâche
\end{itemize}
\end{xca*}
\vspace{0.3cm}
\begin{center}\includegraphics[%
  width=0.75\paperwidth]{maison}\end{center}
\vspace{0.3cm}

\begin{example*}
Organisez un emploi du temps pour un ouvrier, de façon à construire
la maison le plus rapidement.

\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline 
&
\selectlanguage{english}
semaine 1\selectlanguage{frenchb}
&
\selectlanguage{english}
semaine 2\selectlanguage{frenchb}
&
\selectlanguage{english}
semaine 3\selectlanguage{frenchb}
&
\selectlanguage{english}
semaine 4\selectlanguage{frenchb}
&
\selectlanguage{english}
semaine 5\selectlanguage{frenchb}
&
\selectlanguage{english}
semaine 6\selectlanguage{frenchb}
&
\selectlanguage{english}
semaine 7\selectlanguage{frenchb}
\tabularnewline
\hline
\hline 
\selectlanguage{english}
ouvrier 1\selectlanguage{frenchb}
&
&
&
&
&
&
&
\tabularnewline
\hline
\end{tabular}

De même, s'il y a deux ouvriers:

\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline 
&
\selectlanguage{english}
semaine 1\selectlanguage{frenchb}
&
\selectlanguage{english}
semaine 2\selectlanguage{frenchb}
&
\selectlanguage{english}
semaine 3\selectlanguage{frenchb}
&
\selectlanguage{english}
semaine 4\selectlanguage{frenchb}
&
\selectlanguage{english}
semaine 5\selectlanguage{frenchb}
&
\selectlanguage{english}
semaine 6\selectlanguage{frenchb}
&
\selectlanguage{english}
semaine 7\selectlanguage{frenchb}
\tabularnewline
\hline
\hline 
\selectlanguage{english}
ouvrier 1\selectlanguage{frenchb}
&
&
&
&
&
&
&
\tabularnewline
\hline
\selectlanguage{english}
ouvrier 2\selectlanguage{frenchb}
&
&
&
&
&
&
&
\tabularnewline
\hline
\end{tabular}

De même, s'il y a trois ouvriers:

\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline 
&
semaine 1&
\selectlanguage{english}
semaine 2\selectlanguage{frenchb}
&
\selectlanguage{english}
semaine 3\selectlanguage{frenchb}
&
\selectlanguage{english}
semaine 4\selectlanguage{frenchb}
&
\selectlanguage{english}
semaine 5\selectlanguage{frenchb}
&
\selectlanguage{english}
semaine 6\selectlanguage{frenchb}
&
\selectlanguage{english}
semaine7\selectlanguage{frenchb}
\tabularnewline
\hline
\hline 
\selectlanguage{english}
ouvrier 1\selectlanguage{frenchb}
&
&
&
&
&
&
&
\tabularnewline
\hline
\selectlanguage{english}
ouvrier 2\selectlanguage{frenchb}
&
&
&
&
&
&
&
\tabularnewline
\hline
\selectlanguage{english}
ouvrier 3\selectlanguage{frenchb}
&
&
&
&
&
&
&
\tabularnewline
\hline
\end{tabular}

Et s'il y a plus d'ouvriers ?
\end{example*}
\begin{defn*}
Dans le jargon de la recherche opérationnelle, nous avons \emph{ordonnancé}
des \emph{tâches} (construction des fondations, ...) sur plusieurs
processeurs (les ouvriers), avec des contraintes de précédences (un
ordre partiel). 

Un \emph{ordonnancement} est \emph{optimal} s'il minimise la \emph{fonction
objectif} (ici la durée totale).
\end{defn*}

\subsection{Cas d'un processeur}

\begin{xca*}
Chercher un algorithme pour ordonnancer optimalement des tâches avec
contraintes de précédences sur un processeur. 

Quelle est la complexité de cet algorithme?

Démontrez l'optimalité de l'ordonnancement obtenu.
\end{xca*}
%

%

%

%

\solution

En fait, ce que l'on recherche c'est une énumération $t_{1},\ldots,t_{n}$
des tâches de sorte que si $t_{i}<t_{j}$

alors $i<j$. Une telle énumération des tâches est appelée \emph{extension
linéaire} de l'ordre partiel.

On peut voir ça comme un tri des tâches. Mais attention, on ne peut
utiliser les algorithmes de tri usuels en $O(n\log n)$, (tri insertion,
tri fusion, \ldots{}), que si l'ordre est total (toutes les tâches
sont comparables).


\subsection{Cas d'un nombre illimité de processeurs}

\begin{xca*}
Chercher un algorithme pour ordonnancer optimalement des tâches avec
contraintes de précédences sur un nombre infini de processeurs.

Quelle est la complexité de cet algorithme?

Démontrez l'optimalité de l'ordonnancement obtenu.
\end{xca*}
%

%

%

%

\solution

Il s'agit d'un algorithme \emph{glouton.}

À chaque étape, on maximise localement le nombre de tâches effectuées,
et il se trouve que le problème est suffisamment simple pour que le
résultat soit un optimal global.


\subsection{Cas de deux processeurs}

\begin{xca}
Ordonnancez optimalement les trois ordres partiels suivants sur $2$
processeurs:

1: \includegraphics{ordo2-1}, 2: \includegraphics{ordo2-2}, 3: \includegraphics{ordo2-3}
\end{xca}

\subsubsection{Algorithme de Coffman-Graham (algorithme de liste)}

L'idée est comme pour $p=\infty$ de construire un algorithme de type
glouton.

On associe à chaque tâche $t$ une priorité $P(t)$.

Il sera pratique de considérer un processeur inactif comme en train
d'exécuter une tache vide $\emptyset$. C'est d'ailleurs pas si déraisonnable,
vu que en pratique en assembleur il y a une instruction spécifique
\texttt{nop} pour dire à un processeur de ne rien faire.

Par convention, on pose $P(\emptyset)=-\infty$.

\begin{algorithm}
Algorithme de liste pour ordonnancer des tâches unitaires soumises
à des contraintes de précédences sur $p$ processeurs.
\begin{enumerate}
\item Calculer la priorité $P(t)$ de toutes les tâches.
\item $d:=1$.
\item Parmi les tâches minimales (on dira aussi \emph{disponibles}), en
choisir $p$ de priorité maximale (s'il y a moins de $p$ tâches minimales,
les prendre toutes), et les placer dans l'ordonnancement à la date
$d$.


Le choix du processeur est sans importance; par convention, on mettra
celle de poids max sur le premier processeur, et ainsi de suite. 

On note $t_{d,k}$ la tâche exécutée au temps $d$ sur le processeur
$k$.

\item Réitérer à la date $d:=d+1$ avec les tâches restantes.
\end{enumerate}
\end{algorithm}
On appelle cet algorithme \emph{algorithme de liste} parce qu'une
façon de l'implanter est de commencer par construire une \emph{liste}
des tâches par ordre de priorité décroissantes, et ensuite de construire
l'ordonnancement en prenant les éléments dans la liste dans l'ordre.

\begin{xca*}
Trouver des fonctions de priorité pour que cet algorithme de liste
donne des ordonnancements optimaux dans les cas $p=1$ et $p=\infty$.
\end{xca*}
%

%

%

%

\solution

Il s'agit essentiellement d'une généralisation des algorithmes que
l'on a vu précédemment.

\begin{xca*}
Évaluez la complexité de cet algorithme.
\end{xca*}
%

%

%

\solution

\begin{xca*}
Peut-on avoir $t_{d,1}=\emptyset$ ?
\end{xca*}
%

%

%

\solution

Seulement si on est arrivé à la fin de l'ordonnancement.

\begin{rem*}
la priorité $P(t_{d,1})$ des tâches sur le premier processeur est
décroissante.
\end{rem*}
\begin{xca*}
Vérifiez-le! 

Donnez aussi un contre-exemple dans le cas du deuxième processeur.
\end{xca*}
%

%

%

\solution

Soit $t$ une tâche placée à une date $>d$. En regardant successivement
les prédécesseurs de $t$ de date $>d$, on fini par trouver une tâche
$t'\leq t$ disponible. D'après le critère de choix de la tâche sur
le premier processeur, on a $P(t')\leq P(t_{d,1})$. Comme la fonction
de priorité est croissante, on en déduit que $P(t)\leq P(t_{d,1})$.

Contre exemple: \includegraphics{ordo2-4}

\begin{problem*}
Quelle fonction de priorité choisir dans le cas de deux processeurs
?
\begin{enumerate}
\item $P(t):=\textrm{nombre de successeurs de }t$:


Avec l'ordre $2$ ci-dessus, l'algorithme donne un ordonnancement
non optimal.

\item $P(t):=\textrm{taille de la plus grande chaîne partant de }t$:


Avec l'ordre $3$ ci-dessus, l'algorithme donne de manière non-déterministe
un ordonnancement non optimal.

\end{enumerate}
\end{problem*}
\begin{defn*}
On va définir $P(t)$ récursivement comme suit:

Pour chaque tâche $t$ maximale, on pose $P(t):=0$.

On regarde ensuite les tâches maximales dans le reste de l'ordre.

Pour chacune d'entre elles, on construit la liste décroissante des
priorités de ses successeurs immédiats. Pour déterminer quelles sont
les tâches les plus prioritaires, on compare ces listes lexicographiquement.
Ensuite, on assigne aux tâches les priorités $1,$ $2,$ \ldots{}
par ordre de priorité.

On réitère avec les tâches restantes.
\end{defn*}
\begin{xca*}
Calculer les priorités pour les ordres ci-dessus, ainsi que l'ordonnancement
correspondant.

Donner un exemple sur lequel le calcul des priorités est intéressant.

Évaluer la complexité du calcul des priorités.

%

%

%

%

\solution
\end{xca*}
\begin{thm*}
L'algorithme de Coffman-Graham donne un ordonnancement optimal.
\end{thm*}
La preuve du théorème repose sur le lemme suivant.

\begin{lem*}
Soit $d$ telle que $P(t_{d,2})<P(t)$ pour une certaine tâche $t$
exécutée après $t_{d,2}$ (typiquement, $t_{d,2}=\emptyset$). Alors,
$t_{d,1}<t$. La construction de la fonction de priorité nous permet
de dire bien plus fort: pour toute tâche vérifiant $P(t')\geq P(t_{d,1})$,
on a $t'<t$.
\end{lem*}
\begin{xca*}
Démontrez le! Indication: on considèrera d'une part l'ensemble $T$
des tâches $t$ exécutées après $t_{d,2}$, et d'autre part l'ensemble
$T'$ des tâches $t'$ telles que $P(t')\geq P(t_{d,1})$.
\end{xca*}
%

%

%

%

\solution

\begin{proof}
Principe de la preuve du théorème.

On pose $d_{0}:=0$, et on repère les positions $d_{1},\textrm{ }d_{2},\ldots$
comme ci-dessus. 

On définit des blocs de tâches $B_{0},\textrm{ }B_{1},\textrm{ }B_{2},\ldots$
entre chacune de ces positions:\[
B_{k}:=\left\{ t_{d_{k}+1,1},t_{d_{k}+1,2},\ldots,t_{d_{k+1},1}\right\} .\]


En appliquant le lemme, on montre que toutes les tâches de $B_{0}$
précèdent toutes les tâches de $B_{1}$, et ainsi de suite avec les
blocs suivants.

Cette décomposition en blocs prouve l'optimalité de l'ordonnancement.
\end{proof}
\begin{xca*}
Donnez les décompositions en blocs de la preuve dans les exemples
d'ordonnancements que l'on a vu.
\end{xca*}

\subsubsection{Algorithme de Fuji et al.}

Cet autre algorithme est basé sur la remarque suivante: 

\begin{rem*}
Un ordonnancement de tâches de durée unitaire sur $2$ processeurs
est une couverture de l'ordre partiel an antichaînes de taille au
plus $2$, de sorte que deux antichaînes ne se croisent pas.
\end{rem*}
\begin{algorithm}
Ordonnancement de tâches unitaires soumises à des contraintes de précédences
sur $2$ processeurs.
\begin{enumerate}
\item Chercher une couverture de l'ordre partiel en antichaînes de taille
au plus $2$.\\
(Comment peut-on faire ça ?)
\item Décroiser les antichaînes obtenues.
\end{enumerate}
\end{algorithm}
Le faire sur un exemple intéressant


\subsection{Cas de $p$ processeurs}

\begin{problem*}
Est-ce que l'algorithme de Fuji et al. marche encore ?

Indication: analysez l'exemple suivant sur $3$ processeurs:
\end{problem*}
\vspace{0.3cm}
\begin{center}\includegraphics{ordo3-1}\end{center}
\vspace{0.3cm}

%

%

%

%

\solution

Conclusion: la couverture optimale en antichaînes de taille au plus
$3$ est composée de deux antichaînes; mais on ne peut pas les décroiser
en un ordonnancement de durée $2$.

\begin{problem*}
Est-ce que l'algorithme de Coffman-Graham marche encore ?

Indication: analysez les exemples suivants sur $3$ processeurs:
\end{problem*}
\vspace{0.3cm}
\begin{center}\includegraphics{ordo3-2} ~~~~~~~~~~\includegraphics{ordo3-3}\end{center}
\vspace{0.3cm}

%b

%

%

%

\solution

Conclusion: Coffman-Graham sur $3$ processeurs donne un ordonnancement
raisonnable, mais pas forcément optimal.

\begin{problem*}
Peut-on quand même utiliser un algorithme de liste pour trouver une
solution optimale?

Comment chercher toutes les solutions optimales?
\end{problem*}
\begin{defn*}
Un ordonnancement sera dit \emph{tassé à gauche} s'il n'y a pas de
date $d$ avec un processeur inactif, alors qu'il restait des tâches
disponibles. Les algorithmes de liste donnent de tels ordonnancements
tassés à gauche.
\end{defn*}
\begin{xca*}
Montrer que tout ordonnancement $O$ peut être transformé en un ordonnancement
$O'$ tassé à gauche sans augmentation de durée totale.

\solution

En déduire qu'il existe toujours un ordonnancement tassé à gauche
optimal.

On dit que l'ensemble des ordonnancements tassés à gauche est \emph{dominant}.

\solution

Montrez que tout ordonnancement tassé à gauche peut être obtenu par
un algorithme de liste (indication: construire une fonction de priorité
\emph{ad hoc} pour cet ordonnancement).

\solution
\end{xca*}
On peut en fait utiliser le principe des l'algorithmes de liste pour
faire une recherche exhaustive:

À chaque fois que l'on doit faire un choix de $p$ tâches parmi les
tâches disponibles, on explore à tour de rôle tous les choix possibles.
On parcourt alors un arbre de choix, dont les extrémités sont les
ordonnancements tassés à gauches.

% Le faire sur les exemples précédents

C'est ce qu'on appelle un méthode \emph{arborescente}.

Évidement, la complexité devient exponentielle!

Pour limiter les dégâts, il faut autant que possible essayer d'éliminer
les choix qui sont clairement mauvais, de façon à \emph{couper des
branches}.

Typiquement, si on a déjà trouvé un ordonnancement de durée $D$,
ce n'est pas la peine d'explorer les branches où les choix déjà faits
impose qu'il y ait des tâches après $D$.

Une telle méthode s'appelle \emph{branch and bound} en anglais.


\subsubsection{Cas particulier: l'ordre de précédence est une anti-arborescence}

\begin{thm*}
Si l'ordre de précédence est une anti-arborescence, alors l'algorithme
de liste avec comme fonction de priorité la cohauteur donne un ordonnancement
optimal.
\end{thm*}

\subsection{Ordonnancement de tâches de durées non unitaires}

\begin{problem*}
Parmi les algorithmes que nous avons vu précédemment, lesquels s'adaptent
au cas ou les tâches sont de durées arbitraires ?
\end{problem*}

\subsubsection{Cas d'un processeur}

\begin{xca*}
Est-ce qu'un algorithme de liste donne un ordonnancement optimal ?
\end{xca*}
%

%

%

%

\solution

Pas de difficulté: n'importe quelle extension linéaire de l'ordre
des tâches fera l'affaire.


\subsubsection{Cas d'un nombre illimité de processeurs}

\begin{xca*}
Est-ce qu'un algorithme de liste donne un ordonnancement optimal ?
\end{xca*}
%

%

%

%

\solution

Pas de difficulté. 

Il s'agit en fait d'un cas particulier de la méthode PERT: pour déterminer
la durée totale, il suffit de rechercher un chemin critique. C'est
encore un cas de théorème min-max, qui peut être vu comme cas particulier
du théorème de dualité de la programmation linéaire.

\begin{xca*}
Déterminer la complexité de la recherche d'un chemin critique.
\end{xca*}
%

%

%

%

\solution

D'ailleurs on peut aussi utiliser la programmation linéaire, comme
on l'avait fait en TP.

Tel quel, c'est un peu utiliser un marteau pilon!

Mais on avait pu de la sorte traiter des variantes de ce problème,
avec par exemple des tâches de durées variables, moyennant un coût,
etc.


\subsubsection{Cas de deux processeurs}

\begin{thm*}
Même sans contrainte de précédences, le problème d'ordonnancer des
tâches sur $2$ processeurs de manière optimale est NP-complet!
\end{thm*}

\subsection{Synthèse}

On a vu ici des exemples d'applications des principales méthodes d'ordonnancement:

\begin{enumerate}
\item Méthode PERT
\item Méthodes de liste
\item Programmation linéaire
\item Méthodes arborescentes avec stratégies de coupes
\end{enumerate}
\begin{prop*}
Considérons le problème d'assigner $n$ tâches de durées unitaires
sur $p$ processeurs, sous des contraintes de précédences, et avec
les contraintes et but comme ci-dessus.
\end{prop*}
\begin{itemize}
\item $1$ ou $2$ processeurs: algorithmes en $O(n+m)$;
\item $3$ processeurs: complexité inconnue;
\item $p$ processeurs: NP-complet 
\item $\infty$ processeurs: $O(n+m)$.
\end{itemize}
Ceci est typique des problèmes d'optimisation discrète, où de légères
modifications dans les contraintes peuvent faire une grande différence
de complexité. En fait, la complexité évolue souvent de la manière
suivante:

\begin{itemize}
\item Pas de contrainte: facile
\item Quelques contraintes: complexité polynomiale de degré de plus en plus
grand
\item Plus de contraintes: très difficiles (NP-complet). Les algorithmes
sont basés sur une recherche arborescente.
\item Encore plus de contraintes: facile. Éventuellement toujours NP-complet,
mais la plupart des branches peuvent être coupées très tôt, ce qui
donne une bonne complexité en moyenne.
\end{itemize}

\section{Description des problèmes d'ordonnancements}

De manière générale, un problème d'ordonnancement consiste à organiser
l'exécution de tâches, en leur attribuant des ressources et en fixant
leurs dates d'exécution. Pour une classification des différents types
d'ordonnancements, nous renvoyons à l'introduction de \cite{Carlier_Chretienne.PO}.

\begin{notation}
Quelques notations relativement standard (que l'on a pas forcément
respecté ci-dessus!):
\end{notation}
\begin{description}
\item [$m$]nombre de machines;
\item [$n$]nombre de tâches;
\item [$I$]ensemble des tâches;
\item [$i$]indice d'une tâche ou d'un événement;
\item [$t_{i}$]date de début d'exécution de la tâche $i$ ou de l'événement
$i$;
\item [$C_{i}$]date de fin d'exécution de la tâche $i$;
\item [$C_{\textrm{max}}$]durée totale de l'ordonnancement: $C_{\textrm{max}}:=\textrm{max}(C_{i})$;
\item [$p_{i}$]durée de la tâche $i$;
\item [$p_{i,j}$]durée de la tâche $(i,j)$ (graphe CPM/PERT)
\item [$p_{ik}$]durée de la tâche $i$ sur la machine $k$;
\item [$r_{i}$]date de disponibilité de la tâche $i$;
\item [$d_{i}$]date échue de la tâche $i$ (\emph{dead-line});
\item [$T_{i}$]retard de la tâche $i$: $T_{i}:=\textrm{max}(0,C_{i}-d_{i})$;
\item [$U_{i}$]indice de retard: $U_{i}=1$ si la tâche est en retard,
et $0$ sinon;
\item [$w_{i}$]poids de la tâche $i$;
\item [$a_{ij}$]contrainte potentielle entre deux tâches ($t_{j}-t_{i}\geq a_{ij}$);
\item [$<$]ordre partiel sur l'ensemble des tâches.
\end{description}
\begin{xca*}
Ci-dessous est une liste de problèmes (pour la plupart déjà rencontrés
dans ce cours), et qui rentrent dans le cadre des problèmes d'ordonnancements.
Déterminer la classification de chacun de ces problèmes, ainsi que
la valeur des différentes variables ci-dessus. Précisez aussi quelles
sont les contraintes disjonctives et les contraintes cummulatives.
\end{xca*}
\begin{enumerate}
\item Ordonnancement de tâches unitaires sur des processeurs avec contraintes
de précédences;
\item Assignement de cours à des professeurs (ou de nageurs pour un relais
$4$ nages);
\item Problème des visites;
\item Conception d'un emploi du temps dans un petit collège. Pour simplifier,
on suppose que toutes les classes, de la 6ème à la 3ème, ont le même
nombre d'heures de chaque matière, et qu'il y a un professeur par
matière;
\item Ordonnancement du chantier du TP.
\end{enumerate}

\section{Méthodes polynomiales et pseudo-polynomiales}

Nous allons voir une série de cas particuliers pour lesquels il existent
des méthodes polynomiales de résolution.

Il faudrait être prudent avec la définition de polynomial. 

Polynomial en quoi ? Polynomial en la taille des données.

Or, dans les données des entiers peuvent apparaître, et il y a deux
façons de mesurer la taille d'un tel entier $a$:

\begin{enumerate}
\item Le nombre de bits pour stocker $a$ en base $2$, c'est-à-dire $\textrm{log}(a)$.
\item Le nombre de bits pour stocker $a$ en base $1$, c'est-à-dire $a$.
\end{enumerate}
Selon le choix de cette mesure, le même algorithme peut être polynomial
ou exponentiel.

Un algorithme est \emph{polynomial} s'il est polynomial pour la mesure
$1$.

Un algorithme est \emph{pseudo-polynomial} s'il est polynomial pour
la mesure $2$.

Nous renvoyons à \cite[p.~76]{Carlier_Chretienne.PO}pour les détails.


\subsection{Ordonnancement de tâches morcelables (avec préemption)}

Lorsque les tâches sont morcelables, les problèmes deviennent nettement
plus faciles, et on peut plus souvent les résoudre par des méthodes
polynomiales ou pseudo-polynomiales.


\subsubsection{Machines identiques / intervalles de temps distincts}

\begin{problem*}
Le but est d'ordonnancer des tâches morcelables de durée $p_{1},\ldots,p_{n}$
sur $m$ machines identiques de telle sorte que la tâche $i$ s'exécute
dans l'intervalle de temps $[r_{i},\textrm{ }d_{i}]$.
\end{problem*}
\begin{xca*}
Ordonnancement sur deux machines identiques, de quatre tâches morcelables
$A,B,C,D$ avec $p_{A}=p_{B}=p_{D}=2$, $p_{C}=4$; $d_{A}=d_{D}=5$;
$d_{B}=3$, $d_{C}=4$; $r_{A},r_{B},r_{C}=0$, $r_{D}=2$. 

Construisez un problème de transport permettant de résoudre ce problème
par la programmation linéaire. 

Indice: découper le temps en $5$ plages horaires $[0,1]$, $[1,2]$,
$[2,3]$, $[3,4]$, $[4,5]$.
\end{xca*}
%

%

%

%

\solution

\begin{rem*}
Cette méthode ne marche que si les dates $r_{i}$ et $d_{i}$ sont
entières!

De plus, on ne s'autorise à morceler les tâches qu'en fragments de
durée entière. Il est concevable qu'un morcellement plus fin puisse
donner de meilleurs résultats.
\end{rem*}
Si l'on accepte ces restrictions, la programmation linéaire donne
un algorithme pseudo-polynomial (le nombre de plage horaires est borné
par $\textrm{max}(d_{i})-\textrm{min}(r_{i})$).

\begin{xca*}
Pour le moment on a seulement cherché une solution faisable du problème
d'ordonnancement. Cela peut se faire efficacement par un algorithme
de flot.

On veut maintenant en plus optimiser la date de fin d'exécution. Construisez
un problème de transport qui permette de résoudre ce problème.

Indice: Introduisez des coûts sur le réseau précédent.
\end{xca*}
%

%

%

%

\solution


\subsubsection{Machines identiques / durée minimale}

\begin{problem*}
Le but est d'ordonnancer des tâches morcelables de durée $p_{1},\ldots,p_{n}$
sur $m$ machines identiques en minimisant la durée totale $C_{max}$.
\end{problem*}
\begin{xca*}
Donner un ordonnancement optimal pour $m:=3$, $n:=5$, $p_{1}:=10$,
$p_{2}:=8$, $p_{3}:=4$, $p_{4}:=14$, $p_{5}:=1$.
\end{xca*}
%

%

%

%

\solution

\begin{xca*}
On pose \[
B:=\textrm{max }\left(\textrm{max}_{i}\textrm{ }p_{i},\textrm{ }\frac{1}{m}\left(\sum_{i=1}^{n}p_{i}\right)\right).\]


Vérifiez que $B\leq C_{max}$.
\end{xca*}
On peut construire facilement un ordonnancement vérifiant $B=C_{max}$
(et donc optimal)!

Il suffit de remplir le diagramme de Gantt de gauche à droite et de
haut en bas.

\begin{example*}
Ordonnancement de Mac Naughton pour $m:=3$, $n:=5$, $p_{1}:=10$,
$p_{2}:=8$, $p_{3}:=4$, $p_{4}:=14$, $p_{5}:=1$.
\end{example*}
%

%

%

%

\solution

La définition de $B$ assure que les tâches ne se recouvrent pas elles-mêmes
($p_{i}\leq B$), et qu'il y a assez de place ($\sum_{i=1}^{n}p_{i}\leq mB$).
Il se trouve que cela suffit!

\begin{algorithm}
(Mac Naughton) 
\begin{enumerate}
\item $B:=\textrm{max }\left(\textrm{max}_{i}\textrm{ }p_{i},\textrm{ }\frac{1}{m}\left(\sum_{i=1}^{n}p_{i}\right)\right).$
\item $t:=0$; $k:=1$;
\item Pour chaque tâche $i$:

\begin{enumerate}
\item Si $t+p_{i}\leq B$, on affecte $i$ sur la machine $k$ entre les
instants $t$ et $t+p_{i}$ et on pose $t:=t+p_{i}$.
\item Sinon on affecte $i$ sur la machine $k$ entre $t$ et $B$ et sur
la machine $k+1$ entre les instants $0$ et $p_{i}-(B-t)$, et on
pose $k:=k+1$ et $t:=p_{i}-(B-t)$.
\end{enumerate}
\end{enumerate}
\end{algorithm}
\begin{xca*}
Construire un ordonnancement pour $m:=4$ et $(p_{1},\ldots,p_{7}):=(5,10,2,8,3,4,20)$.
\end{xca*}
%

%

%

%

\solution

On remarque qu'il y a a relativement peu de préemptions (au plus $m-1$).


\subsubsection{Machines identiques, temps minimal, contraintes de précédences}

\begin{problem*}
Le but est d'ordonnancer des tâches morcelables de durée $p_{1},\ldots,p_{n}$
sur $m$ machines identiques en minimisant la durée totale $C_{max}$,
et avec des contraintes de précédences entre les tâches.
\end{problem*}
\begin{xca*}
Donnez des algorithmes polynomiaux pour une et deux machines, et pour
un nombre illimité de machines.
\end{xca*}
%

%

%

%

\solution

Dans ces trois cas, on peut se ramener au problème d'ordonnancement
de tâches unitaires en morcelant chaque tâche $i$ en une succession
de $p_{i}$ tâches unitaires.

\begin{rem*}
Il faut tout de même supposer que les durées des tâches sont entières.

Pour être précis, les algorithmes ainsi obtenus sont pseudo-polynomiaux.
\end{rem*}

\subsubsection{Machines distinctes, temps minimal}

\begin{problem*}
Le but est d'ordonnancer des tâches morcelables sur machines distinctes
en minimisant la durée totale $C_{max}$, sachant que la durée d'exécution
de la tâche $i$ sur la machine $j$ est $p_{ij}$.
\end{problem*}
\begin{xca*}
Le tableau suivant donne les valeurs de $p_{ij}$ pour $4$ tâches
devant être exécutées sur $3$ machines. Donnez un encadrement rapide
de $C_{max}$.

\begin{tabular}{|c|c|c|c|}
\hline 
tâche\textbackslash{}machine&
1&
2&
3\tabularnewline
\hline
\hline 
1&
15&
10&
6\tabularnewline
\hline 
2&
9&
9&
9\tabularnewline
\hline 
3&
8&
6&
8\tabularnewline
\hline 
4&
3&
3&
2\tabularnewline
\hline
\end{tabular}
\end{xca*}
%

%

%

%

\solution

Slowinski et Labetoulle et Lawler ont proposé une méthode très esthétique
pour résoudre ce problème via la programmation linéaire.

L'idée est de ne pas se préoccuper, dans un premier temps, des dates
exactes à laquelle les tâches seront exécutées. On ne s'intéresse
qu'à la durée totale $x_{ij}$ que la tâche $i$ passe sur la machine
$j$ dans un ordonnancement donné. Une deuxième phase, le théorème
de Birkhoff-Von Neumann (si si!) permettra de construire les détails
de l'ordonnancement.

\begin{xca*}
Vérifiez que pour tout ordonnancement, les $x_{ij}$ sont solution
faisable du programme linéaire suivant:\[
\textrm{ }\sum_{j=1}^{m}x_{ij}\leq C_{max},\textrm{ pour }i=1,\ldots,n\]
\[
\sum_{i=1}^{n}x_{ij}\leq C_{max},\textrm{ pour }j=1,\ldots,m\]
\[
\sum_{j=1}^{m}\frac{x_{ij}}{p_{ij}}=1,\textrm{ pour }i=1,\ldots,n\]
\[
x_{ij}\geq0,\textrm{ pour }i=1,\ldots,n\textrm{ et }j=1,\ldots,m\]


où l'on minimise $C_{max}$.
\end{xca*}
%

%

%

%

\solution

La première phase consiste à chercher une solution $x_{ij}$ optimale
pour ce programme linéaire.

\begin{xca*}
Une solution optimale de ce programme linéaire pour notre exemple
est donnée par la table suivante. On a $C_{\textrm{max}}:=9$. 

Construisez un ordonnancement de durée $C_{\textrm{max}}$ donnant
ces valeurs aux $x_{ij}$.

\begin{tabular}{|c|c|c|c|}
\hline 
tâche\textbackslash{}machine&
1&
2&
3\tabularnewline
\hline
\hline 
1&
&
&
6\tabularnewline
\hline 
2&
3&
3&
3\tabularnewline
\hline 
3&
4&
3&
\tabularnewline
\hline 
4&
2&
1&
\tabularnewline
\hline
\end{tabular}.
\end{xca*}
%

%

%

%

\solution

A-t'on été chanceux?

Il n'est pas évident qu'il existe toujours un ordonnancement optimal
de durée $C_{\textrm{max}}$!

\begin{example*}
Construction systématique pour notre exemple.
\end{example*}
Pour construire un tel ordonnancement, on transforme la matrice des
$x_{ij}$ en une matrice $M$ bistochastique en rajoutant une ligne
et une colonne avec des coefficients $c_{i}$ et $l_{j}$ idoines:

\begin{enumerate}
\item $c_{i}:=C_{max}-\sum_{j=1}^{m}x_{ij}$ :durée totale pendant laquelle
la tâche $i$ n'est pas exécutée;
\item $l_{j}:=C_{max}-\sum_{i=1}^{n}x_{ij}$ :durée totale pendant laquelle
la machine $j$ ne fait rien.
\end{enumerate}
Pour être précis, c'est $\frac{1}{C_{\textrm{max}}}M$ qui est une
matrice bistochastique.

Le théorème de Birkhoff-Von Neumann permet alors de décomposer $M$
sous la forme\[
M=\sum_{k=1}^{l}\lambda_{k}P_{k},\]
 où chaque $P_{k}$ est une matrice de permutation et $\sum_{k}\lambda_{k}=C_{\textrm{max}}$.

On construit l'emploi du temps final en associant à chaque $k$ une
plage de temps de durée $\lambda_{k}$ pendant laquelle les tâches
sont assignées aux machines selon la permutation $P_{k}$!


\subsection{Ordonnancement de tâches non morcelables}


\subsubsection{Problème central de l'ordonnancement; modélisation par graphe potentiel
tâche}

Rappel: soit $i$ et $j$ deux tâches d'un problème d'ordonnancement,
et $t_{i}$ et $t_{j}$ leurs dates respectives de début d'exécution.
On appelle \emph{contrainte potentielle} une containte de la forme
$t_{j}-t_{i}\geq a_{ij}$.

\begin{xca*}
Considérons un ensemble de cinq tâches $\{1,2,3,4,5\}$ soumises aux
contraintes temporelles suivantes:
\begin{enumerate}
\item La tâche $i$ dure $p_{i}$;
\item La tâche $2$ commence au temps $3$;
\item Les tâches $2$ et $3$ doivent se chevaucher sur au moins une unité
de temps;
\item La tâche $4$ ne peut commencer qu'après la fin des tâches $1$ et
$2$;
\item La tâche $5$ ne peut pas commencer avant le début de la tâche $3$.
\end{enumerate}
Il n'y a pas de contraintes de ressources.

L'objectif est d'optimiser la durée totale.

Modéliser ces contraintes par des contraintes potentielles. On rajoutera
deux tâches fictives $0$ et $6$ de façon à mesurer facilement la
durée totale par $t_{6}-t_{0}$.

Représenter ces contraintes sur un graphe dont les sommets sont les
tâches et les arêtes sont les contraintes.

Peut-on éliminer certaines arêtes ?

Quelles méthodes pour traiter ce problème ?
\end{xca*}
%

%

%

%

\solution

\begin{defn*}
Le problème central de l'ordonnancement consiste à choisir les dates
d'exécutions pour un ensemble de tâches $I$, de façon à respecter
des contraintes potentielles et à minimiser la durée totale.

Le graphe utilisé ci-dessus s'appelle \emph{graphe potentiel-tâche}.

Il s'agit d'une variante des graphes potentiel-événement utilisés
à l'origine dans les méthodes CPM/PERT. Les graphes potentiel-tâches
ont l'avantage d'être souvent plus simples, et de permettre plus facilement
l'introduction de nouvelles contraintes.
\end{defn*}
\begin{xca*}
Peut-on modéliser par un graphe potentiel tâche:
\end{xca*}
\begin{itemize}
\item Des contraintes de précédences ?
\item Des dates de disponibilité? Des dates échues ?
\item Des délais de communication ?
\item Des durées d'exécution ?
\item Des contraintes de ressources ?
\end{itemize}
%

%

%

%

\solution

Les problèmes avec contraintes de ressources (contraintes disjonctives/cumulatives)
sont habituellement beaucoup plus difficiles que ceux sans (problèmes
de \emph{décision}), et ne peuvent pas être modélisés par des graphes
potentiel-tâches. Une approche classique est de les modéliser par
des \emph{réseaux de Pétri temporisés}. Nous renvoyons à \cite{Carlier_Chretienne.PO}
pour plus d'information.


\subsection{Problèmes sans contraintes de ressources}


\subsubsection{Optimisation de la durée totale}

\begin{xca*}
Donner une méthode polynomiale pour résoudre un problème modélisé
par un graphe potentiel-tâche, et pour lequel on veut optimiser la
durée totale.
\end{xca*}
%

%

%

%

\solution


\subsubsection{Étude de faisabilité}

\begin{xca*}
Le problème modélisé par le graphe potentiel tâche suivant a-t'il
une solution ?
\end{xca*}
\vspace{0.3cm}
\begin{center}\includegraphics{ordo4-1}\end{center}
\vspace{0.3cm}

%

%

%

%

\solution

\begin{defn*}
La \emph{valeur} d'un chemin dans le graphe potentiel-tâches est la
somme des coefficients sur les arcs du chemin.
\end{defn*}
Si le graphe potentiel-tâche a un cycle de valeur strictement positive,
alors il n'y a pas de solutions. En fait, il s'agit du \emph{seul
cas} ou il n'y ait pas de solutions:

\begin{thm*}
Il existe une solution faisable si et seulement si le graphe potentiel-tâche
n'a pas de cycles de valeur strictement positive.
\end{thm*}
En particulier, s'il les valuations sont strictement positives, il
n'y a de solution que s'il n'y a pas de cycles. C'est typiquement
le cas pour des contraintes de précédences.

\begin{xca*}
On a déjà démontré l'un des sens du théorème. L'objectif de cet exercice
est de donner un démonstration constructive de l'autre sens.

On suppose qu'il n'y a pas de cycles de valeur strictement positive,
et on veut démontrer qu'il y a une solution faisable.

Soit $i$ et $j$ deux tâches, et $C_{ij}$ l'ensemble des chemins
élémentaires (sans boucles) allant de $i$ à $j$. Vérifier que $C_{ij}$
est fini. 

Si $C_{ij}$ est vide, on pose $l(i,j):=-\infty$. Sinon, il existe
donc un chemin dans $C_{ij}$ de plus grande valeur; un tel chemin
est appelé critique, et on note $l(i,j)$ sa valeur. Vérifier que
si $c$ est un chemin quelconque allant de $i$ à $j$, alors sa valeur
est inférieure à $l(i,j)$.

On défini pour chaque tâche $i$, sa \emph{date d'exécution au plus
tôt} $r_{i}:=l(0,i)$.

Vérifiez que les $r_{i}$ ainsi définis forment une solution faisable.

Vérifiez qu'il s'agit aussi d'une solution optimale pour la durée
totale.
\end{xca*}
%

%

%

%

\solution

\begin{problem*}
Comment calculer les $r_{i}$ effectivement ?
\end{problem*}
Lorsqu'il n'y a pas de cycles, il suffit de faire un parcours en profondeur
du graphe, en partant du sommet $0$ (algorithme en $O(m)$, où $m$
est le nombre de contraintes).

Dans le cas général, les potentiels $t_{i}$ peuvent être interprétés
comme les variables duales du problème de transport construit à partir
du graphe potentiel-tâches. Du coup, les $r_{i}$ peuvent être calculés
par une variante de l'algorithme de Ford-Fulkerson en $O(n^{3})$
(en gros, comme dans la démonstration du théorème, on peut se contente
de chercher une solution faisable; celle-ci sera directement optimale
si on s'y prend bien; donc on est ramené à un problème de flot).


\subsubsection{Potentiels calés à gauche et à droite}

On appelle les $r_{i}$ \emph{ensemble de potentiels calés à gauche}.
On pourrait de même construire un \emph{ensemble de potentiels calés
à droite}, en partant cette fois de la dernière tâche. On obtient
alors les dates d'exécution au plus tard\emph{\[
f_{i}:=l(0,n+1)-l(i,n+1).\]
} Pour tout ordonnancement optimal, on a alors $r_{i}\leq t_{i}\leq f_{i}$
(pourquoi ?).

La quantité $f_{i}-r_{i}$ mesure combien de marge on a pour exécuter
la tâche $i$.

Lorsque $i$ est sur un chemin critique, on a $f_{i}-r_{i}=0$: si
on perds du temps dans l'exécution de la tâche $i$ la durée totale
de l'ordonnancement sera affectée.

Dans l'ensemble des tâches pour préparer un cours, la photocopie des
documents est clairement une tâche critique \ldots{}

Ce que l'on vient de faire est une méthode de \emph{chemin critique.}
C'est une variante de la méthode CPM/PERT, ou méthode des potentiels
(cf. \cite[p.~112]{Carlier_Chretienne.PO})


\subsubsection{Optimisation d'une fonction linéaire des $t_{i}$}

\begin{rem}
Ce que l'on vient de faire se généralise lorsque l'on recherche non
plus à optimiser la durée totale $t_{n+1}-t_{0}$ de l'ordonancement,
mais une fonction linéaire quelconque des $t_{i}$. On peut toujours
se ramener à un programme linéaire, et en fait même à un problème
de transport (mais plus forcément à un problème de flot).
\end{rem}
\begin{xca}
Regarder comment cette remarque s'applique pour le problème du chantier
que l'on avait vu en TP.
\end{xca}

\subsection{Problèmes avec contraintes de ressources renouvellables}

La plupart de ces problèmes sont NP-complets, même dans des cas apparemment
simple comme l'ordonnancement sur deux processeurs de tâches indépendantes,
mais de durées quelconques.

Il y a quelques exceptions comme celles que l'on avait rencontré au
début:

\begin{itemize}
\item Tâches unitaires sur $1$ et $2$ processeurs identiques avec contraintes
de précédences
\item Tâches unitaires indépendantes avec contraintes de disponibilité ou
de dates échues
\end{itemize}

\subsection{Problèmes à ressources consommables}

\begin{xca*}
Lire \cite[p.~101-107]{Carlier_Chretienne.PO}. 

En particulier calculer un ordonnancement optimal pour l'exemple p.~104.
\end{xca*}

\section{Méthodes Arborescentes et dynamiques}


\section{Algorithmes approchés}

\begin{thebibliography}{1}
\bibitem{Carlier_Chretienne.PO}\emph{Problèmes d'ordonnancement, Modélisation, Complexité, Algorithmes};
J.~Carlier, P.~Chrétienne, Masson, Études et recherches en informatique,
1988.\end{thebibliography}

\end{document}
