Loading...
Please wait, while we are loading the content...
Similar Documents
Approche de réseaux de neurones récurrents pour le problème de l'ordonnancement cyclique et sa variante
| Content Provider | Semantic Scholar |
|---|---|
| Author | Low, Kok Seng |
| Copyright Year | 2008 |
| Abstract | Un probleme d'ordonnancement consiste a executer sur un horizon de temps donne un ensemble de taches au moyen de ressources en nombre limite. On rencontre ce probleme dans divers domaines, comme l'industrie de production, dans les systemes de transport ou encore dans les ordinateurs avec l'allocation des tâches. Dans cette these, nous nous concentrons sur le probleme d'ordonnance cyclique, Les proprietes liees a l'ordonnancement en general, ainsi qu'a sa version cyclique seront etudiees. Le probleme d'ordonnancement des tâches est un probleme NP-complet, le temps necessaire pour le resoudre peut etre exponentiel dans le pire des scenarios. Ceci a motive notre travail de recherche et nous a mene a developper une approche efficace utilisant les reseaux de neurones pour le resoudre. Cette these se concentre particulierement sur le probleme du Job Shop Cyclic et sur son utilisation dans le cadre des ateliers flexibles (FMS : Flexible Manufacturing System). Pour cela, nous avons developpe deux modeles de resolutions bases sur les reseaux de neurones. Le premier a pour objectif de minimiser le temps de cycle et le second a pour objectif de minimiser les encours de production. On remarque une absence de travaux utilisant les reseaux de neurones sur ce type de probleme dans la litterature scientifique. Ceci est du a l'architecture complexe des reseaux de neurones, a la difficulte de definir les conditions initiales, au reglage de ses parametres (taux d'apprentissage, condition d'arret, etc. ) ainsi que sa tendance a generer des solutions impossibles. Neanmoins, dans cette these, nous proposons 3 variations autour des reseaux de neurones : un reseau de neurones recurrents (RNN), une relaxation Lagrangienne pour un reseau de neurones recurrents (LRRNN) et un reseau Hopfield avance. Plusieurs algorithmes ont ete combines avec ces reseaux de neurones pour assurer que les solutions generees sont toutes possibles et pour reduire l'effort de recherche des solutions optimales. Une phase pretraitement CDRP (Competitive Dispatch Rule Phase) a ete developpee pour generer des solutions initiales correctes avant que les 3 reseaux de neurones soient initialises. Celle-ci permet de reduire l'espace de recherche du probleme. Pour le probleme du FMS cyclique, une phase modifiee (MCDRP) a ete egalement developpee. Pour s'echapper des optimums locaux, une phase de perturbation a ete developpee pour relancer la recherche dans une autre region de l'espace de recherche. Enfin, une phase de post traitement assure que les solutions finales sont toujours dans l'espace des solutions possibles. Dans une premiere partie, nous avons etendu nos travaux au probleme du job shop cyclique avec des contraintes de precedence lineaire. Selon la litterature en ordonnancement cyclique, il est possible de transformer les contraintes lineaires en contraintes uniformes equivalentes, c'est pour cette raison qu'un algorithme de delinearisation a ete developpe pour permettre de traiter ce probleme avec notre approche lagrangienne precedente. Nous avons ete capable de demontrer la conformite et l'applicabilite des approches utilisant des reseaux RNN, LRRNN et Advanced Hopfield a travers une evaluation comparative. Les resultats experimentaux indiquent que les 3 approches proposees sont des alternatives attrayantes par rapport a d'autres approches heuristiques traditionnelles meme si parfois celles-ci restent couteuses en terme de calcul. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://www.lgi2a.univ-artois.fr/spip/IMG/pdf/these_kok_seng_low_.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
