Table des figures
II.1 Principe de fonctionnement d'un AE selon Schoenauer
2003). 16
II.2 front de Parito 18
II.3 Rand de Parito . 19
II.4 Crowding distance. 20
III.1 Architectures Parallèles. 28
III.2 Architecture MIMD à mémoire
partagée . 29
III.3 Architecture MIMD à mémoire non
partagée. 29
III.4 Distribution de calculs de performance 30
III.5 Exemple de modèle en îlots. 31
III.6 Population totalement distribuée. 32
1
INTRODUCTION GÉNÉRALE
La vie professionnelle par son caractère d'être
irrégulière, et dans le sens quelle subie à des
règles bien définies à priori, elle doit être bien
organisée, où chaque domaine professionnel se diffère par
sa propre façon de s'organiser.
Parmi les concepts les plus connues dans les domaines
d'organisations professionnelles, on trouve la planification d'horaires de
travail. Par exemple, Les usines ont besoin d'optimiser le rendement de leurs
chaines de production, alors chaque machine de production effectue une
tâche particulière à une période fixée a
priori. Les hôpitaux ont besoin d'affecter un certain nombre de
personnels constitués d'infirmiers, de médecins... à des
postes de travail convenables dans des périodes aussi bien
déterminer a priori, toute en respectant les règles de gestion
des hôpitaux. L'affectation des tâches ou des personnels à
des périodes invariables nécessite souvent la mise en oeuvre d'un
planning de travail d'une manière périodique et
stratégique. ce dernier permet de réduire fidèlement le
coût de la production et améliorer la qualité des
services.
La planification du temps consiste --au sens large-- à
allouer des ressources à un nombre limité d'acteurs humain ou
à des agents artificielles dans un intervalle de temps, de façon
à satisfaire au mieux un ensemble d'objectifs tels que la
réduction des coûts ou l'amélioration de la qualité
des services, toute en respectant un certain nombre de contraintes, tel que les
conditions du travail.
Cette recherche met en scène la problématique de
la planification des horaires et plus particulièrement le
problème de l'emploi de temps dans un contexte général et
sa complexité au quotidien dans les entreprises. En effet, la question
de l'aménagement du temps de travail et de ses enjeux préoccupe
toute société ou établissement actif ce qui a
incité les chercheurs à proposer des méthodes et des
techniques pour aider à gérer au mieux les horaires de
travail.
2
Chapitre I
LE PROBLÈME D'EMPLOI DE
TEMPS
Le principale motivation de l'Algorithmiques est de
résoudre des problèmes informatiques, ce que veut dire de
traitement automatique de l'information de la maniéré la plus
efficace possible. Or, même si intuitivement on croit ce qu'efficace
semble signifier, la réalité est loin d'être aussi simple.
La théorie de la complexité est une discipline qui
s'intéresse à étudier les différents
problèmes informatiques et les classer en fonction des
ressources nécessaires à leur résolution
algorithmique (temps de calcul, espace mémoire) ainsi elle s'attache
à la formalisation de concept d'efficacité d'un
algorithme.
Certains problèmes, même s'ils semblent
d'être faciles à résoudre ou théoriquement
possèdent des solutions calculables, la recherche d'un algorithme
qui produise une telle solution est pratiquement difficile. Cette
difficulté est justifier par le fait que le temps du calcul ou l'espace
mémoire nécessaire pour produire la solution sur une machine est
très important. En effet, une simple augmentation dans la taille des
entrées implique une augmentation généralement
exponentielle dans le nombre des combinaisons (solutions)
candidates (admissibles, possibles, acceptables) qui forment un
espace de recherche combinatoire et qui doit être examiné
d'une manière exhaustive pour trouver la solution
certaine.
Généralement, pour résoudre un
problème, on essaye de trouver l'algorithme le plus efficace, où
la notion d'efficacité induit normalement toutes les ressources de
calcul nécessaires pour son exécution. Or, le temps
d'exécution est généralement le facteur dominant pour
sélectionner un bon algorithme.
I.1 La complexité Temporelle
La complexité temporelle d'un algorithme est
définie théoriquement par le nombre d'ins-tructions
élémentaires qui le constituant. Mais, il est pénible de
compter précisément toutes les instructions, même si on
retient seulement les opérations critiques. Alors, on se contentera
souvent d'estimer leur nombre[13].
On dit que f(n) = è(g(n)) (f(n) est de
complexité g(n)), s'il existe un réel k positif non nul
et un nombre naturel fixe n0 tels que : ?n n > n0f(n) < k.g(n).
L'écriture ci-dessus signifie quef(n) est
bornée par g(n), et donc on peut écrire :
3
| 
