Les modèles de simulation de foules visent généralement à produire des foules visuellement crédibles avec l'intention d'insuffler de la vie à des environnements virtuels. Notre travail se concentre sur la génération de comportements statistiquement cohérents qui peuvent être utilisés pour piloter des modèles de simulation de foules sur de longues périodes de temps, jusqu'à plusieurs jours. Dans les foules réelles, les comportements des individus dépendent principalement de l'activité qu'ils ont l'intention d'effectuer. La façon d’ordonnancer cette activité repose sur l'interaction étroite qui existe entre l'environnement, les contraintes spatiales et temporelles associées à l'activité et les caractéristiques personnelles des individus. Par rapport à l'état de l'art, notre modèle gérer mieux cette interaction. Nos principales contributions se situent dans le domaine de l'ordonnancement d'activités et de la planification de chemin. Dans un premier temps, nous proposons un processus d'ordonnancement d'activités individuelles et son extension aux activités coopératives. Basé sur les descriptions de l'environnement, des activités désirées et des caractéristiques des agents, ces processus génèrent une séquence de la tâche pour chaque agent. Des lieux où ces tâches doivent être effectuées sont sélectionnés et un timing relâché est produit. Cet ordonnancement est compatible avec les contraintes spatiales et temporelles liées à l'environnement et à l'activité prévue par l'agent et par d'autres agents en coopération. Il prend également en compte les caractéristiques personnelles des agents, induisant de la diversité dans les ordonnancements produits. Nous montrons que notre modèle produit des comportements statistiquement cohérents avec ceux produits par des personnes dans les mêmes situations. Dans un second temps, nous proposons un processus de planification de chemins hiérarchique. Il repose sur un processus d'analyse de l'environnement automatique qui produit une représentation hiérarchique sémantiquement cohérente des villes virtuelles. La nature hiérarchique de cette représentation est utilisée pour modéliser différents niveaux de prise de décisions. Un chemin grossier est d'abord calculé, puis raffiné pendant la navigation lorsque de l'information pertinente est disponible, permettant ainsi à l'agent d'adapter son chemin à des événements inattendus. Le modèle proposé gère des décisions rationnelles à long terme guidant la navigation des agents dans les villes virtuelles. Il prend en compte la forte relation entre le temps, l'espace et l'activité pour produire les comportements des agents plus crédibles de. Il peut être utilisé pour peupler facilement des villes virtuelles avec des foules au sein desquelles des phénomènes observables émergent de l'activité individuelle. / Crowd simulation models usually aim at producing visually credible crowds with the intent of giving life to virtual environments. Our work focusses on generating statistically consistent behaviours that can be used to pilot crowd simulation models over long periods of time, up to multiple days. In real crowds, people's behaviours mainly depend on the activities they intend to perform. The way this activity is scheduled rely on the close interaction between the environment, space and time constraints associated with the activity and personal characteristics of individuals. Compared to the state of the art, our model better handle this interaction. Our main contributions lie in the domain of activity scheduling and path planning. First, we propose an individual activity scheduling process and its extension to cooperative activity scheduling. Based on descriptions of the environment, of intended activities and of agents' characteristics, these processes generate a task schedule for each agent. Locations where the tasks should be performed are selected and a relaxed agenda is produced. This task schedule is compatible with spatial and temporal constraints associated with the environment and with the intended activity of the agent and of other cooperating agents. It also takes into account the agents personal characteristics, inducing diversity in produced schedules. We show that our model produces schedules statistically coherent with the ones produced by humans in the same situations. Second, we propose a hierarchical path-planning process. It relies on an automatic environment analysis process that produces a semantically coherent hierarchical representation of virtual cities. The hierarchical nature of this representation is used to model different levels of decision making related to path planning. A coarse path is first computed, then refined during navigation when relevant information is available. It enable the agent to seamlessly adapt its path to unexpected events. The proposed model handles long term rational decisions driving the navigation of agents in virtual cities. It considers the strong relationship between time, space and activity to produce more credible agents' behaviours. It can be used to easily populate virtual cities in which observable crowd phenomena emerge from individual activities.

Que ce soit dans l’automobile avec des contraintes thermiques ou dans l’aérospatial et lenucléaire soumis à des rayonnements ionisants, l’environnement entraîne l’apparition de fautesdans les systèmes électroniques. Ces fautes peuvent être transitoires ou permanentes et vontinduire des résultats erronés inacceptables dans certains contextes applicatifs. L’utilisation decomposants dits « rad-hard » est parfois compromise par leurs coûts élevés ou les difficultésd’approvisionnement liés aux règles d’exportation.Cette thèse propose une approche conjointe matérielle et logicielle indépendante de la technologied’intégration permettant d’utiliser des composants numériques programmables dans desenvironnements susceptibles de générer des fautes. Notre proposition comporte la définitiond’une Architecture Reconfigurable à Gros Grains (CGRA) capable d’exécuter des codes applicatifscomplets mais aussi l’ensemble des mécanismes matériels et logiciels permettant de rendrecette architecture tolérante aux fautes. Ce résultat est obtenu par l’association de redondance etde reconfiguration dynamique du CGRA en s’appuyant sur une banque de configurations généréepar une chaîne de programmation complète. Cette chaîne outillée repose sur un flot permettantde porter un code sous forme de Control and Data Flow Graph (CDFG) sur l’architecture enobtenant un grand nombre de configurations différentes et qui permet d’exploiter au mieux lepotentiel de l’architecture.Les travaux, qui ont été validés aux travers d’expériences sur des applications du domaine dutraitement du signal et de l’image, ont fait l’objet de publications en conférences internationaleset de dépôts de brevets. / Whether in automotive with heat stress or in aerospace and nuclear field subjected to cosmic,neutron and gamma radiation, the environment can lead to the development of faults in electronicsystems. These faults, which can be transient or permanent, will lead to erroneous results thatare unacceptable in some application contexts. The use of so-called rad-hard components issometimes compromised due to their high costs and supply problems associated with exportrules.This thesis proposes a joint hardware and software approach independent of integrationtechnology for using digital programmable devices in environments that generate faults. Ourapproach includes the definition of a Coarse Grained Reconfigurable Architecture (CGRA) ableto execute entire application code but also all the hardware and software mechanisms to make ittolerant to transient and permanent faults. This is achieved by the combination of redundancyand dynamic reconfiguration of the CGRA based on a library of configurations generated by acomplete conception flow. This implemented flow relies on a flow to map a code represented as aControl and Data Flow Graph (CDFG) on the CGRA architecture by obtaining directly a largenumber of different configurations and allows to exploit the full potential of architecture.This work, which has been validated through experiments with applications in the field ofsignal and image processing, has been the subject of two publications in international conferencesand of two patents.

Empilant une couche multiprocesseur (MPSoC) et une couche de FPGA pour former un système sur puce reconfigurable en trois dimension (3DRSoC), est une solution prometteuse donnant un niveau de flexibilité élevé en adaptant l'architecture aux applications visées. Pour une application exécutée sur ce système, l'un des principaux défis vient de la gestion de haut niveau des tâches. Cette gestion est effectuée par le service d'ordonnancement du système d'exploitation et elle doit être en mesure de déterminer, lors de l'exécution de l'application, quelle tâche est exécutée logiciellement et/ou matériellement, quand (dimension temporelle) et sur quelles ressources (dimension spatiale, c'est à dire sur quel processeur ou quelle région du FPGA) pour atteindre la haute performance du système. Dans cette thèse, nous proposons des stratégies d'ordonnancement spatio-temporel pour les architectures 3DRSoCs. La première stratégie décide la nécessité de placer une tâche matérielle et une tâche logicielle en face-à-face afin que le coût de la communication entre tâches soit minimisé. La deuxième stratégie vise à minimiser le temps d'exécution globale de l'application. Cette stratégie exploits la présence de processeurs de la couche MPSoC afin d'anticiper, en temps-réel, l'exécution d'une tâche logicielle quand sa version matérielle ne peut pas être allouée sur le FPGA. Ensuite, un outil de simulation graphique a été développé pour vérifier le bon fonctionnement des stratégies développées et aussi nous permettre de produire des résultats. / Stacking a multiprocessor (MPSoC) layer and a FPGA layer to form a 3D Reconfigurable System-on- Chip (3DRSoC) is a promising solution giving a high flexibility level in adapting the architecture to the targeted application. For an application defined as a graph of parallel tasks running on the 3DRSoC system, one of the main challenges comes from the high-level management of tasks. This management is done by the scheduling service of the Operating System and it must be able to determine, on the fly, what task should be run in software and/or hardware, when (temporal dimension) and where (spatial dimension, i.e. on what processor or what area of the FPGA) in order to achieve high performance of the system. In this thesis, we propose online spatio-temporal scheduling strategies for 3DRSoCs. The first strategy decides, during the task scheduling, the need for a SW task and a HW task to communicate in face-to-face so that the communication cost between tasks is minimized. The second strategy aims at minimizing the overall execution time of the application. It exploits the presence of processors in the MPSoC layer in order to anticipate, at run-time, the SW execution of a task when its HW version cannot be allocated to the FPGA. Then, a graphical simulation tool has been developed to verify the proper functioning of the developed strategies and also enable us to produce results.

L’Institut National des Produits Chimiques de l’Académie des Sciences du Vietnam (INPC) développe depuis plusieurs années une activité autour de la recherche de nouveaux médicaments issus de la biodiversité. Le développement d’un nouveau médicament prend de l’ordre d’une dizaine d’années et passe par plusieurs phases. Dans la phase de découverte, l’activité des composés chimiques sur une cible biologique est mesurée afin de mettre en évidence une action inhibitrice. Le développement d’approches in silico pour le criblage virtuel des composés chimiques est une alternative aux approches classiques in vitro beaucoup plus coûteuses à mettre en œuvre. L’utilisation de la grille a été identifiée comme une voie économiquement prometteuse pour accompagner la recherche de nouveaux médicaments au Vietnam. En effet, le développement de nouvelles stratégies basées sur l’utilisation de plates-formes de soumission de tâches (DIRAC, HTCaaS) a permis d’améliorer considérablement le taux de succès et le confort des utilisateurs, ouvrant la voie à une démocratisation de la grille.Dans ce contexte, l’objectif poursuivi dans le cadre de cette thèse est d’étudier dans quelle mesure des plates-formes multidisciplinaires pouvaient répondre aux besoins des chimistes de l’INPC. Le travail s’est concentré sur les modalités d’un partage équitable d’une plate-forme de soumission de tâches sur la grille par une ou plusieurs communautés d’utilisateurs. L’ordonnancement des tâches sur un serveur commun doit permettre que les différents groupes aient une expérience positive et comparable. Sur les infrastructures de grille EGEE et EGI en Europe , on peut distinguer deux grandes catégories d’utilisateurs : les utilisateurs « normaux » qui vont solliciter les ressources pour des tâches requérant typiquement de quelques dizaines à quelques centaines d’heures de calcul, et les « gros » utilisateurs qui vont lancer des grandes productions nécessitant le traitement de plusieurs milliers de tâches pendant des dizaines, voire des centaines de milliers d’heures de calcul. Les stratégies d’ordonnancement déployées aujourd’hui sur les plates-formes comme DIRAC ou HTCaaS ne permettent pas de servir de façon optimale et simultanée ces deux familles d’utilisateurs.Le manuscrit présente une évaluation par simulation des performances de plusieurs stratégies d’ordonnancement des tâches d’une plate-forme soumettant des jobs pilotes. L’outil SimGrid a permis de simuler l’infrastructure de grille régionale déployée en Auvergne à partir de traces archivées de son utilisation. Après évaluation des performances de plusieurs politiques d’ordonnancement tirées de la littérature, une nouvelle politique a été proposée dans laquelle les utilisateurs normaux et les très gros utilisateurs sont gérés de façon indépendante. Grâce à cette politique, le ralentissement expérimenté par les très gros utilisateurs est réduit significativement sans pénaliser excessivement les utilisateurs normaux. L’étude a été étendue à une fédération de clouds utilisant les mêmes ressources et arrive aux mêmes conclusions. Les performances des politiques d’ordonnancement ont ensuite été évaluées sur des environnements de production, à savoir l’infrastructure de grille européenne EGI et l’infrastructure nationale de supercalculateurs de la Corée du Sud. Un serveur DIRAC a été adossé aux ressources de l’organisation virtuelle biomédicale d’EGI pour étudier les ralentissements observés par les utilisateurs de ce serveur. Pareillement, les ralentissements expérimentés par les utilisateurs de la plate-forme HTCaaS au KISTI ont été observés en excellent accord avec les résultats de simulation avec SimGrid.Ces travaux confirment la faisabilité et l’intérêt d’une plate-forme unique au Vietnam au service des communautés scientifiques consommatrices des ressources académiques de grille et de cloud, notamment pour la recherche de nouveaux médicaments. / Virtual Screening (VS) is a computational technique used in the drug discovery process to select the most promising candidate drugs for in vitro testing from millions of chemical compounds. This method can offer an efficient alternative to reduce the cost of drug discovery and platform. The Natural Products Chemistry Institute of the Academy of Sciences of Vietnam (INPC) collects samples from local biodiversity and determines the 3D structure of single molecules. Their challenge is to set up a virtual screening platform on grid computing for their chemists to process their data. However, as the number of users who might have a wide range of virtual screening applications (in terms of the number of tasks and execution time) increases with limited available computing resources, it becomes crucial to devise an effective scheduling policy that can ensure a certain degree of fairness, user satisfaction and overall system throughput. In this context, the thesis focuses on an effective scheduling policy for the virtual screening workflow where multiple users with varying numbers of tasks are actively sharing a common system infrastructure. We have researched in theory and proposed some candidate policies. With the simulation results and the experimentation results in real system, we proposed the best policy for the fairness between users, which can be applied to INPC virtual screening platform.

L’hospitalisation hors les murs est une expression générique qui désigne toutes les formes de structures accueillant des patients pour une prise en charge longue et régulière nécessitant des soins complexes. Les structures hors les murs doivent assurer une prise en charge sure et d’une qualité au moins identique à celle fourni par l’hôpital, tout en contribuant à la diminution des coûts de la prise en charge. D’où la nécessité d’une gestion efficiente des activités des soignants et des ressources humaines. Dans ce travail de recherche, l’intérêt est porté à la problématique générale de gestion des activités de soins en Hospitalisation À Domicile (HAD). Il s’agit d’une problématique très complexe, car elle vise à résoudre simultanément des sous-problèmes réputés NP – difficiles. Dans cette thèse, nous étudions cette problématique au niveau opérationnel de la conception des tournées des soignants. La démarche adoptée pour ce travail de recherche se base sur trois étapes essentielles. Nous commençons par une étude sur le système de santé et les structures d’HAD en France, tout en mettant en claire les facteurs essentiels de leur fonctionnement. Cette étape sera clôturée par une étude du fonctionnement des systèmes d’HAD dans la région Rhône-Alpes, en se basant sur les retours du projet régional Organisation des Soins A Domicile (OSAD). La deuxième étape concerne les problématiques de gestion et la planification des activités de soins et des ressources humaines en HAD. Ce travail conduira à l’élaboration d’une classification des problématiques de la gestion des activités en HAD. En se basant sur la classification identifiée précédemment, nous définissons, les axes de complexité de ce problème : (i) le nombre d’activités de soins par soignant, (ii) la dépendance temporelle entre les activités des patients et (iii) la dimension environnementale. Ensuite, nous proposons un ensemble d’approches et d’outils pour la résolution de la problématique des tournées d’infirmiers en HAD, sous différentes contraintes liées à la réalisation des soins et en particulier aux contraintes de dépendances temporelles. Pour répondre à l’ensemble des contraintes et exigences de performance, nous développons une heuristique originale permettant une résolution en un temps compatible avec les contraintes de mise en oeuvre, pour des instances de grande taille / Home care services, is a generic term that gathers different kind of care: provider, agency, and organization. In France, the most important part of the in-home care is performed by HAD (Hospitalization At Home). The HAD concept is defined by decree. The HAD has to provide only complex care in the patient’s home for 24 motives. HAD are hospitals and have to ensure continuity of care for their patients. Our researches focus on the operation management for home care services. This problem is complex; it needs to solve sub-problems known to be NP - hard. In this work, this problem is studied at the operational level in design of tours of caregivers. The approach followed is based on three essential stages. Firstly, we study the health system and the home care structures in France. At the end of this step, we summarize the outcome obtained of the regional project Organization of Home Care Service (Organisation des Soins A Domicile : OSAD) on the home care structures in the Rhône-Alpes region (France). The second step gathers scientific literature about home care management, particularly about problems of management and planning of activities and human resources in the home care structures. This work leads to design a classification in order to management activities issues in home care structures. Based on this classification, we define three complexity axes of the operation management in home care problem, i.e. (i) the rate of the number of care activities per caregiver, (ii) dependency level between the patients’ activities and (iii) the environmental level. In the third stage, we suggest a set of mathematical approaches and tools for solving the problem of caregivers’ tours. Two MIPL model are developed, the first is based on a Traveling Salesman Problem (TSP) with coordination between the caregivers and the second on RCPSP (Ressources Constrained Project Scheduling Problem). Because the both previous models are time consuming, we suggest an original heuristic to solve the TSP coordinated problem, to resolve the care management activities in home care services

Pour augmenter la durée de vie des réseaux de capteurs sans fil, une solution est d'améliorer l'efficacité énergétique des protocoles de communication. Le regroupement des nœuds du réseau de capteurs sans fil en cluster est l'une des meilleures méthodes. Cette thèse présente propose plusieurs améliorations en modifiant les paramètres du protocole de référence LEACH. Pour améliorer la distribution énergétique des "cluster-heads", nous proposons deux protocoles de clustering centralisés k-LEACH et sa version optimisée k-LEACH-VAR. Un algorithme distribué, appelé e-LEACH, est également proposé pour réduire l'échange d'information périodique entre les nœuds et la station de base lors de l'élection des "cluster-heads". Par ailleurs, le concept l'équilibrage énergétique est introduit dans les métriques d'élection pour éviter les surcharges des nœuds. Ensuite, nous présentons une version décentralisée de k-LEACH qui, en plus des objectifs précédents, intègre la consommation d'énergie globale du réseau. Ce protocole, appelé, k-LEACH-C2D, vise également à favoriser la scalabilité du réseau. Pour renforcer ce dernier et l'autonomie des réseaux, les deux protocoles de routage "multi-hop" probabiliste, dénotés FRSM et CB-RSM construisent des chemins élémentaires entre les "cluster-heads" et la station de base. Le protocole CB-RSM forme une hiérarchie des "cluster-heads" pendant la phase de formation des clusters, en mettant un accent sur l'auto-ordonnancement et l'auto-organisation entre les "cluster-heads" pour rendre les réseaux le plus "scalable". Ces différents protocoles reposent sur l'idée de base que les nœuds ayant l'énergie résiduelle la plus élevée et la plus faible variance de consommation de l'énergie deviennent "cluster-head". Nous constantans le rôle central de la consommation du nœud dans nos différentes propositions. Ce point fera l'objet de la dernière partie de cette thèse. Nous proposons une méthodologie pour caractériser expérimentalement la consommation d'un nœud. Les objectifs visent à mieux appréhender la consommation pour différentes séquences d'état du nœud. Enfin, nous proposons un modèle global de la consommation du nœud. / To increase the lifetime of wireless sensor networks, a solution is to improve the energy efficiency of the communication's protocol. The grouping of nodes in the wireless sensor network clustering is one of the best methods. This thesis proposes several improvements by changing the settings of the reference protocol LEACH. To improve the energy distribution of "cluster-heads", we propose two centralized clustering protocols LEACH and k-optimized version k-LEACH-VAR. A distributed algorithm, called e-LEACH, is proposed to reduce the periodic exchange of information between the nodes and the base station during the election of "cluster-heads". Moreover, the concept of energy balance is introduced in metric election to avoid overloading nodes. Then we presented a decentralized version of k-LEACH, which in addition to the previous objectives, integrates the overall energy consumption of the network. This protocol, called k-LEACH-C2D, also aims to promote the scalability of the network. To reinforce the autonomy and networks, both routing protocols "multi-hop" probability, denoted CB-RSM and FRSM build elementary paths between the "cluster-heads" and elected the base station. The protocol, CB-RSM, forms a hierarchy of "cluster-heads" during the training phase clusters, with an emphasis on self-scheduling and self-organization between "cluster-heads" to make the networks more scalable. These protocols are based on the basic idea that the nodes have the highest residual energy and lower variance of energy consumption become "cluster-head". We see the central role of consumption of the node in our proposals. This point will be the last part of this thesis. We propose a methodology to characterize experimentally the consumption of a node. The objectives are to better understand the consumption for different sequences of the node status. In the end, we propose a global model of the consumption of the node.

Ce manuscrit aborde des problèmes d’ordonnancement et de transport avec une modélisation explicite du transport. De tels problèmes se modélisent communément sous forme de graphes qui sont évalués afin d’obtenir les dates de début des opérations.Les évaluations classiques des graphes sont effectuées au moyen d’algorithmes de plus long chemin permettant d’obtenir une solution semi-active, où toutes les dates des opérations sont au plus tôt. Néanmoins, ces évaluations permettent généralement de ne prendre en compte que des critères de temps ou de distance à minimiser. Les travaux présentés dans ce manuscrit proposent de tenir compte de critères de qualité de service dans la fonction objectif. Cette prise en considération nécessite de nouvelles fonctions d’évaluation du graphe afin d’obtenir des solutions non nécessairement semi-actives permettant de maximiser la qualité de service. En effet, une solution semi-active propose rarement une qualité de service optimale. Les critères de qualité de service adoptés portent sur les ordonnancements et sur le transport.Trois problèmes intégrés sont successivement traités. Le premier problème est un problème de Job-shop avec transport et qualité de service, appelé Job-shop Scheduling Problem with Routing (JSPR). Des pièces, définies par une succession d’opérations, sont à fabriquer sur différentes machines, et entre deux opérations, la pièce doit être transportée de machine en machine. Le critère de qualité de service dans ce problème est dépendant des délais entre, d’une part les différentes opérations sur les machines, et d’autre part entre les différentes opérations de transport. Les gammes opératoires et les opérations de transport sont dépendantes les unes des autres.Le second problème est un problème de Workforce Scheduling and Routing Problem (WSRP), assimilable à un problème de planification de visites à domicile par un ensemble d’employés, et où le transport est pris en compte. Pour ce problème, le critère de qualité de service dépend des dates de début des visites. Les tournées sont indépendantes les unes des autres.Le troisième problème est le Generalised Workforce Scheduling and Routing Problem (GWSRP), qui prend en compte des contraintes de coordination entre les employés. Les tournées de ces derniers sont dépendantes les unes des autres. Elles nécessitent d’être toutes considérées simultanément pour évaluer les dates des visites respectant les contraintes de coordination et maximisant la qualité de service.Pour chaque problème, une nouvelle fonction d’évaluation est proposée. Pour le JSPR, cette fonction est basée sur l’algorithme de (Cordeau and Laporte, 2003) qui est initialement prévu pour le Dial-A-Ride Problem, ainsi que sur l’insertion de time-lags dans le graphe disjonctif du JSPR. Cette évaluation est incluse dans une métaheuristique. Pour le WSRP, la fonction d’évaluation est basée sur un algorithme de calcul du plus court chemin avec un algorithme de type programmation dynamique à labels. Elle est généralisée pour être utilisée dans une génération de colonnes. Et enfin, pour le GWSRP, l’évaluation est effectuée par un modèle PPC qui combiné à une génération de colonnes définissent tous deux un schéma d’optimisation global. / This manuscript addresses scheduling and transport problems where the transport is explicitly taken into account. Such problems are commonly modelled by graphs that are evaluated to obtain the starting times of operations.Classic graph evaluations are performed using longer path algorithms to obtain a semi-active solution, where all operations are left shifted. Nevertheless, these evaluations generally allow only time or distance criteria to be taken into account. The work presented in this thesis propose to take the quality of service criteria into account in the objective function. These considerations require new graph evaluation functions in order to obtain non-semi-active solutions that maximise the quality of service. Indeed, a semi-active solution rarely offers maximum quality of service. Three integrated problems are successively addressed. The first problem is a Job-shop Scheduling Problem with transport and quality of service, referred to as Job-shop Scheduling Problem with Routing (JSPR). Jobs, defined by a succession of operations, are to be performed on different machines, and between two operations, the job must be transported from a machine to another machine. The quality of service criterion in this problem depends on the delay between, on the one hand, the different operations belonging to the same job, and on the other hand, between the different transport operations. Machine-operations and transport-operations are dependent.The second problem is a Workforce Scheduling and Routing Problem (WSRP), which is similar to a problem of planning home services by a set of employees, and where transport is taken into account. For this problem, the quality of service criterion depends on the starting times of the visits. The trips of employees are independent.The third problem is the Generalised Workforce Scheduling and Routing Problem (GWSRP), which takes coordination constraints between employees into account. The trips are dependent on each other. The evaluation function of the starting times must consider simultaneously all trips in order to respect all coordination constraints and to maximise the service quality.For each problem, a new evaluation function is proposed. For the JSPR, this function is based on the algorithm of (Cordeau and Laporte, 2003) which is introduced first for the Dial-A-Ride Problem. The evaluation function, for the JSPR, is based on the insertion of time-lags in the disjunctive graph. This evaluation is included in a metaheuristic. For the WSRP, the evaluation function is based on the dynamic labelling algorithm used for an Elementary Shortest Path Problem With Resource Constraints. This function is generalised in order to be included in a column generation scheme. Finally, for the GWSRP, the evaluation is performed by a PPC model combined with a generation of columns and both define an overall optimisation scheme.

Nous assistons ces dernières années à une émergence constante de nouvelles applications, notamment pour les services audiovisuels. Ces applications imposent au réseau un certain nombre de contraintes pour qu’elles puissent fonctionner correctement. Le développement de mécanismes permettant d’offrir une garantie à ces contraintes, est donc devenu un objectif crucial. La norme IEEE 802.16j est l’une des solutions sans fil qui propose plus de ressources afin de supporter les nouveaux services de télécommunications. Dans la présente thèse, nous focalisons notre étude sur la problématique de la qualité de service dans les réseaux WiMAX relais. Nos contributions se regroupent à travers les étapes ci-dessous : Nous proposons un protocole de routage multicast pour les services IPTV (HDTV, SD-TV, Web-TV et Mobile-TV). Ce protocole repose d’une part sur un nouveau mécanisme de construction de l’arbre multicast basé sur les nombres premiers et d’autre part, sur une nouvelle méthode d’agrégation basée sur le standard de compression Vidéo «SVC». L’objectif est de supporter l’hétérogénéité des utilisateurs tout en optimisant la consommation des ressources. Par ailleurs, nous étudions le problème d’ordonnancement dans les réseaux WiMAX. Nous proposons un algorithme d’ordonnancement adaptatif AWRR, ce dernier se base sur une technique à charge pondérée. L’objectif est d’ajuster dynamiquement le poids de chaque classe de service, en prenant en compte la charge de la file d’attente et les contraintes de la QoS. Enfin, nous nous intéressons à l’étude de la problématique du chemin optimal contraint. Nous proposons une solution déterministe basée sur une fonction de coût. Notre fonction permet aussi d’assurer le contrôle d’admission, elle se base sur deux fonctions de coût élémentaires qui prennent en compte quatre critères de QoS. / Over recent years, new applications steadily developed in a tremendous space, especially in audiovisual services area. The present applications have some of constraints to work properly. The developments of mechanism which enable to overcome these constraints become a critical issue in this area. The IEEE 802.16j standard is one of wireless communication technology which offering more resources to support new telecommunication services. In this thesis, we focus our research on the problem of quality of service (QoS) inWiMAX relay networks. Our contributions are classified as follows : we proposed a multicast routing protocol for IPTV services (such as HD-TV, SD-TV, Web-TV and Mobile-TV). This proposed protocol used a new multicast tree construction mechanism based-on prime numbers. We also developed a new aggregation method based on standard video compression called Scalable Video Coding (SVC). Our goal is to support user’s heterogeneity while optimizing resources consumption. In addition, we studied the problem of scheduling inWiMAX networks.We proposed an adaptive scheduling algorithm AWRR for IPTV services. The aim of this method is to support QoS constraints by using two schedulers, and assigning a dynamic value to each service queue. Finally, we interested to study about the problem of path selection. We proposed a solution based on a deterministic cost function. This function also ensures admission control based on two basic cost functions which include four QoS criteria. This thesis has been prepared in the MIPS/GRTC laboratory, University of Haute Alsace, under a research contract external (CRE) framework with France Telecom R&D. All proposed mechanisms were evaluated by the simulator QualNet, Matlab and mathematical analysis.

La sélection d’un modèle approprié est l’une des tâches essentielles de l’apprentissage statistique. En général, pour une tâche d’apprentissage donnée, on considère plusieurs classes de modèles ordonnées selon un certain ordre de « complexité». Dans ce cadre, le processus de sélection de modèle revient `a trouver la « complexité » optimale, permettant d’estimer un modèle assurant une bonne généralisation. Ce problème de sélection de modèle se résume à l’estimation d’un ou plusieurs hyper-paramètres définissant la complexité du modèle, par opposition aux paramètres qui permettent de spécifier le modèle dans la classe de complexité choisie. L’approche habituelle pour déterminer ces hyper-paramètres consiste à utiliser une « grille ». On se donne un ensemble de valeurs possibles et on estime, pour chacune de ces valeurs, l’erreur de généralisation du meilleur modèle. On s’intéresse, dans cette thèse, à une approche alternative consistant à calculer l’ensemble des solutions possibles pour toutes les valeurs des hyper-paramètres. C’est ce qu’on appelle le chemin de régularisation. Il se trouve que pour les problèmes d’apprentissage qui nous intéressent, des programmes quadratiques paramétriques, on montre que le chemin de régularisation associé à certains hyper-paramètres est linéaire par morceaux et que son calcul a une complexité numérique de l’ordre d’un multiple entier de la complexité de calcul d’un modèle avec un seul jeu hyper-paramètres. La thèse est organisée en trois parties. La première donne le cadre général des problèmes d’apprentissage de type SVM (Séparateurs à Vaste Marge ou Support Vector Machines) ainsi que les outils théoriques et algorithmiques permettant d’appréhender ce problème. La deuxième partie traite du problème d’apprentissage supervisé pour la classification et l’ordonnancement dans le cadre des SVM. On montre que le chemin de régularisation de ces problèmes est linéaire par morceaux. Ce résultat nous permet de développer des algorithmes originaux de discrimination et d’ordonnancement. La troisième partie aborde successivement les problèmes d’apprentissage semi supervisé et non supervisé. Pour l’apprentissage semi supervisé, nous introduisons un critère de parcimonie et proposons l’algorithme de chemin de régularisation associé. En ce qui concerne l’apprentissage non supervisé nous utilisons une approche de type « réduction de dimension ». Contrairement aux méthodes à base de graphes de similarité qui utilisent un nombre fixe de voisins, nous introduisons une nouvelle méthode permettant un choix adaptatif et approprié du nombre de voisins. / The selection of a proper model is an essential task in statistical learning. In general, for a given learning task, a set of parameters has to be chosen, each parameter corresponds to a different degree of “complexity”. In this situation, the model selection procedure becomes a search for the optimal “complexity”, allowing us to estimate a model that assures a good generalization. This model selection problem can be summarized as the calculation of one or more hyperparameters defining the model complexity in contrast to the parameters that allow to specify a model in the chosen complexity class. The usual approach to determine these parameters is to use a “grid search”. Given a set of possible values, the generalization error for the best model is estimated for each of these values. This thesis is focused in an alternative approach consisting in calculating the complete set of possible solution for all hyperparameter values. This is what is called the regularization path. It can be shown that for the problems we are interested in, parametric quadratic programming (PQP), the corresponding regularization path is piece wise linear. Moreover, its calculation is no more complex than calculating a single PQP solution. This thesis is organized in three chapters, the first one introduces the general setting of a learning problem under the Support Vector Machines’ (SVM) framework together with the theory and algorithms that allow us to find a solution. The second part deals with supervised learning problems for classification and ranking using the SVM framework. It is shown that the regularization path of these problems is piecewise linear and alternative proofs to the one of Rosset [Ross 07b] are given via the subdifferential. These results lead to the corresponding algorithms to solve the mentioned supervised problems. The third part deals with semi-supervised learning problems followed by unsupervised learning problems. For the semi-supervised learning a sparsity constraint is introduced along with the corresponding regularization path algorithm. Graph-based dimensionality reduction methods are used for unsupervised learning problems. Our main contribution is a novel algorithm that allows to choose the number of nearest neighbors in an adaptive and appropriate way contrary to classical approaches based on a fix number of neighbors.

La coordination des activités dans une chaîne logistique a suscité récemment beaucoup d'attention dans larecherche de gestion. Dans une chaîne logistique typique, des produits finis sont produits et transportés pour êtrestockage temporairement ou arriver directement chez clients. Pour réaliser la représentation opérationnelleoptimale, la coordination et l'intégration de la production, de la livraison, et du stockage devient très importante.L'étude récente a considéré le coût de stockage de client avec le coût fixe de transport ou la taille fixe des lots, cequi est irréaliste.Dans cette thèse, nous étudions la coordination de traitement des produits en lots et l'ordonnancement des lots, quiinclut la coordination du traitement en lots des produits dans les groupes après l'étape de production,l'ordonnancement des lots après les productions exigent la livraison du fournisseur ainsi que le stockage desproduits aux clients. Ce travail focalise sur les cas du simple-fournisseur/plusieurs-clients et le cas de simplefournisseur/plusieurs-transporteurs. Pour le premier scénario avec plusieurs-clients, deux modèles illustrent letransfert des lots aux clients. Dans le premier modèle, nous avons considéré un simple-fournisseur/plusieurs-clientsavec un transporteur disponible pour servir les clients sans considération du problème de tournée de véhicule. Puis,dans le deuxième modèle, nous avons considéré un simple-fournisseur/plusieurs-clients avec plusieurs transportersdisponibles pour servir les clients. Différentes hypothèses sont proposées et comparées dans le dernier chapitre.Pour ce qui concerne le deuxième scénario, nous avons étudié le cas du simple-fournisseur avec plusieurstransporteurs disponibles pour servir un seul client. Dans ce scénario, des modèles avec les véhicules homogèneset hétérogènes sont étudiés. Tout le coût du système est calculé en additionnant de tout le coût de la livraison et destockage pour les différents clients et transporteurs qui se sont dans le système à étudier. Le nombre des produitsdans les lots peut être inégal et les lots sont limités seulement par la capacité du transporteur utilisé. Le coût destockage chez les clients dépend de chaque client, la distance entre le fournisseur et leurs clients dépend del'emplacement de client, qui est le cas du coût de livraison également qui dépend de l'emplacement du client. Dansle cas des multi transporteurs, le coût de livraison dépend du transporteur utilisé.Dans chaque modèle, nous présentons ce qui suit : procédures de solution pour résoudre chaque modèle, plusieursexemples numériques pour soutenir des résultats mathématiques et pour clarifier le problème, et comparaisons desperformances parmi différents résultats. La future extension de cette recherche peut considérer des contraintes detemps et de coût de chargement dans l'étape de production, la considération du tourné de véhicule avec un cout destockage chez les clients. / The coordination of logistics activities in a supply chain has recently received a lot of attention in operationsmanagement research. In a typical supply chain, finished products are produced and either shipped to be temporarystorage or arrived directly on time to the customers. To achieve optimal operational performance, the coordinationand integration of production, delivery, and storage is an important consideration. The recent study consideredcustomer storage cost with fixed transportation cost or fixed batch size, which is unrealistic. In this thesis, we studythe coordinate of batching and scheduling activities, which includes the coordination of batching of products inbatches after the production stage, the coordination of scheduling, customer(s) orders which require the deliveryfrom the supplier, and the storage of products at the customer(s). This study focus on single-supplier/multi-customerscenario and single-supplier/multi-transporter scenario. For the first scenario with multi-customer, two modelsillustrate the transferring of batches to the customer. Where in the first model, we considered a singlesupplier/ multicustomerwith one capacitated transporter available to serve the customers without the vehicle routingconsideration. Then, in the second model, we considered a single-supplier/multi-customer with multi-transportavailable to serve the customers. In this case different assumption is proposed and compared in the last chapter.Concerning the second scenario, we studied the case of single-supplier with multi-transporter available to serve asingle customer. In this scenario, models with homogeneous and heterogeneous vehicles are studied. The totalsystem cost is calculated by summing the total delivery and storage cost for different customers and transporters inthe system. The number of products by batch is unequal and they are limited only by the capacity of the transporterused. The storage cost of the customers depends on the customer destination, the distance between the supplierand their customers depends on the customer location, which is the case of the delivery cost also which depends onthe customer¿s location. In the case of the multi-transporters, the delivery cost depends on the transporter used.In each model, we present the following: solution procedures to solve each model, many numerical examples tosupport mathematical findings and to clarify the problem under study, and performance comparisons amongdifferent findings. The future extension of this research may involve considering setup time and cost constraints inthe production stage, the vehicle routing consideration with inventory in the multi-customer case.