De nombreux systèmes réels et applications, tels que les ateliers flexibles et systèmes embarqués, sont formés de tâches communicantes et sont modélisables par des réseaux de Petri pondérés. Le comportement de ces systèmes peut être vérifié sur leur modèle dès la phase de conception afin d'éviter les simulations post-conception coûteuses. Ces systèmes doivent satisfaire trois propriétés : vivacité, capacité bornée et réversibilité. La vivacité préserve la possibilité d'exécuter chaque tâche. La capacité bornée assure une quantité limitée de ressources. La réversibilité évite une initialisation coûteuse et permet de réinitialiser le système. Les méthodes d'analyse de ces propriétés ont généralement une complexité exponentielle. Dans cette thèse, nous étudions plusieurs sous-classes expressives des réseaux de Petri pondérés, soient les classes Fork-Attribution, Choice-Free, Join-Free et Equal-Conflict, pour lesquelles nous développons les premiers algorithmes polynomiaux garantissant vivacité, capacité bornée et réversibilité. Premièrement, nous apportons des transformations polynomiales qui préservent de nombreuses propriétés des réseaux de Petri pondérés et facilitent l'étude de leur comportement. Deuxièmement, nous utilisons ces transformations pour obtenir plusieurs conditions polynomiales suffisantes de vivacité pour les sous-classes considérées. Enfin, ces transformations simplifient l'étude de la réversibilité sous hypothèse de vivacité. Nous donnons plusieurs caractérisations et conditions polynomiales suffisantes de réversibilité pour les sous-classes étudiées. Nos conditions passent à l'échelle et sont aisément implémentables dans les systèmes réels. / Many real systems and applications, including flexible manufacturing systems and embedded systems, are composed of communicating tasks and may be modeled by weighted Petri nets. The behavior of these systems can be checked on their model early on at the design phase, thus avoiding costly simulations on the designed systems. Usually, the models should exhibit three basic properties: liveness, boundedness and reversibility.Liveness preserves the possibility of executing every task, while boundedness ensures that the operations can be performed with a bounded amount ofresources. Reversibility avoids a costly initialization phase and allows resets of the system.Most existing methods to analyse these properties have exponential time complexity.By focusing on several expressive subclasses of weighted Petri nets, namely Fork-Attribution, Choice-Free, Join-Free and Equal-Conflict nets,the first polynomial algorithms that ensure liveness, boundednessand reversibility for these classes have been developed in this thesis.First, we provide several polynomial time transformations that preserve structural andbehavioral properties of weighted Petri nets, while simplifying the study of their behavior.Second, we use these transformations to obtain several polynomial sufficient conditions of livenessfor the subclasses considered. Finally, the transformations also prove useful for the study of the reversibility propertyunder the liveness assumption. We provide several characterizations and polynomial sufficient conditionsof reversibility for the same subclasses. All our conditions are scalable and can be easily implemented in real systems.

À l'instar d'œuvres telles que Kinoautomat de Radúz Činčera, SAM - Sound Activated Mobile d'Edward Ihnatowicz et Glowflow de Myron Krueger, des artistes ont développé, dès les années 1960, des installations artistiques engageant des situations d'interaction collective co-localisée inédites, c'est-à-dire impliquant plusieurs voire de nombreux spectateurs interagissant dans le même lieu via et avec un dispositif informatique. Le nombre de ces travaux ne cesse d'augmenter depuis le début du 21ème siècle, profitant des nouvelles opportunités offertes par les avancées dans les technologies de vision par ordinateur en temps réel et par l'avènement de l'informatique ubiquitaire marquée par la multiplication et l'interopérabilité des appareils informatiques mobiles. Si les expériences en la matière sont de plus en plus fréquentes, elles n'ont jusqu'à ce jour fait l'objet d'aucune analyse structurée et, encore moins, de propositions d'outils et de méthodes de conception dédiés. Comment, aujourd'hui, concevoir de tels dispositifs artistiques interactifs dont la complexité intrinsèque implique des questions aussi bien de l'ordre technique, social, cognitif qu'esthétique ? Cette thèse met à contribution des travaux antérieurs dans les domaines de l'interaction homme-machine (IHM), du travail coopératif assisté par ordinateur (TCAO) et des arts interactifs dans le but d'accroître notre connaissance quant aux défis auxquels sont confrontés à la fois les artistes et les participants de telles installations et, au-delà, les concepteurs de ces dispositifs en devenir. Un ensemble d'outils et de lignes directrices sont proposés pour la conception de systèmes d'interaction collective co-localisée pour les installations d'art numérique. Est d'abord développé un système de classification centré sur les aspects les plus décisifs permettant l'émergence d'une expérience collective. Deux approches différentes sont ensuite explorées pour trouver les bases d'un langage de modélisation graphique pour l'analyse et la conception de tels dispositifs. S'appuyant sur les réseaux de Petri, la deuxième approche permet de modéliser aussi bien les ressources spatiales et matérielles d'une installation, que les interactions homme-machine, humain(s)-humain(s) et humain(s)-machine(s)-humain(s). Les investigations menées pour cette recherche ont nécessité de mettre un accent particulier sur les conditions - qu'elles soient spatiales, matérielles ou humaines - qui affectent la capacité pour les participants de telles installations de co-construire une expérience esthétique commune en l'absence d'orchestration ou d'un objectif pré-annoncé à atteindre. Si cette approche singulière concerne en premier lieu les arts interactifs, elle peut revêtir également un caractère pertinent pour d'autres communautés de recherche, y compris et en premier lieu, celle de l'IHM, ainsi que celles du TCAO, des Nouvelles interfaces pour l'expression musicale (NIME), du design d'interaction ou encore de la culture, en particulier de la muséographie. / With works such as Kinoautomat by Radúz Činčera, SAM - Sound Activated Mobile by Edward Ihnatowicz, and Glowflow by Myron Krueger, artists have deployed, as early as the 1960s, art installations engaging novel situations of collective co-located interaction, i.e involving multiple or even many spectators interacting in the same place via and with a digital apparatus. The number of those works has continued to increase since the beginning of the 21st century, taking advantage of the new opportunities offered by advances in real-time computer vision technologies and the advent of ubiquitous computing marked by the multiplication and interoperability of mobile computing devices. While experiences in this area are more and more frequent, they have not yet been the subject of structured analysis and, even less, of proposals for dedicated tools and design methods. How can we, nowadays, conceive such interactive art installations whose intrinsic complexity involves questions of the technical, social, cognitive and aesthetic order? This dissertation draws on previous work in the fields of human-computer interaction (HCI), computer-supported cooperative work (CSCW), and interactive arts research with the aim of increasing our knowledge of the challenges faced both by art practitioners and participants in such collective interactive installations, and, beyond, the designers of apparatus in a promising future. A set of tools and guidelines are proposed when designing collective co-located interactions for digital art installations. First a classification system is developed centered on the most decisive aspects that allow the emergence of a collective experience. Two distinct approaches are then explored to find the bases of a graphical modeling language for the design and analysis of such apparatus. Build on top of Petri nets, the second approach supports modeling the spatial and material resources of an installation, as well as the human-machine, human-human and human-machine-human interactions. The investigations conducted for this research have required laying particular emphasis on the conditions - whether spatial, material, or human - which affect the ability for participants to co-construct a common aesthetic experience in the absence of orchestration or a preannounced goal to be achieved. While this singular approach primarily concerns interactive arts, it may be relevant to a wide range of research communities, including, and foremost, that of HCI, as well as CSCW, New Interfaces for Musical Expression (NIME), interaction design, and even culture, museography in particular.

L'un des aspects fondamentaux des systèmes informatiques modernes, et en particulier des systèmes critiques, est la possibilité d'exécuter plusieurs processus, partageant des ressources communes, de façon simultanée. De par leur nature concurrentielle, le bon fonctionnement de ces systèmes n'est assuré que lorsque leurs comportements ne dépendent pas d'un ordre d'exécution prédéterminé. En raison de cette caractéristique, il est particulièrement difficile de s'assurer qu'un système concurrent ne possède pas de faille. Dans cette thèse, nous étudions la vérification formelle, une approche algorithmique qui vise à automatiser la vérification du bon fonctionnement de systèmes concurrents en procédant par une abstraction vers des modèles mathématiques. Nous considérons deux de ces modèles, les réseaux de Petri et les systèmes d'addition de vecteurs, et les problèmes de vérification qui leur sont associés. Nous montrons que le problème d'accessibilité pour les systèmes d'addition de vecteurs (avec états) à deux compteurs est PSPACE-complet, c'est-à-dire complet pour la classe des problèmes solubles à l'aide d'une quantité polynomiale de mémoire. Nous établissons ainsi la complexité calculatoire précise de ce problème, répondant à une question demeurée ouverte depuis plus de trente ans. Nous proposons une nouvelle approche au problème de couverture pour les réseaux de Petri, basée sur un algorithme arrière guidé par une caractérisation logique de l'accessibilité dans les réseaux de Petri dits continus. Cette approche nous a permis de mettre au point un nouvel algorithme qui s'avère particulièrement efficace en pratique, tel que démontré par notre implémentation logicielle nommée QCover. Nous complétons ces résultats par une étude des systèmes de transitions bien structurés qui constituent une abstraction générale des systèmes d'addition de vecteurs et des réseaux de Petri. Nous considérons le cas des systèmes de transitions bien structurés à branchement infini, une classe qui inclut les réseaux de Petri possédant des arcs pouvant consommer ou produire un nombre arbitraire de jetons. Nous développons des outils mathématiques facilitant l'étude de ces systèmes et nous délimitons les frontières au-delà desquelles la décidabilité des problèmes de terminaison, de finitude, de maintenabilité et de couverture est perdue. / One fundamental aspect of computer systems, and in particular of critical systsems, is the ability to run simultaneously many processes sharing resources. Such concurrent systems only work correctly when their behaviours are independent of any execution ordering. For this reason, it is particularly difficult to ensure the correctness of concurrent systems.In this thesis, we study formal verification, an algorithmic approach to the verification of concurrent systems based on mathematical modeling. We consider two of the most prominent models, Petri nets and vector addition systems, and their usual verification problems considered in the literature.We show that the reachability problem for vector addition systems (with states) restricted to two counters is PSPACE-complete, that is, it is complete for the class of problems solvable with a polynomial amount of memory. Hence, we establish the precise computational complexity of this problem, left open for more than thirty years.We develop a new approach to the coverability problem for Petri nets which is primarily based on applying forward coverability in continuous Petri nets as a pruning criterion inside a backward coverability framework. We demonstrate the effectiveness of our approach by implementing it in a tool named QCover.We complement these results with a study of well-structured transition systems which form a general abstraction of vector addition systems and Petri nets. We consider infinitely branching well-structured transition systems, a class that includes Petri nets with special transitions that may consume or produce arbitrarily many tokens. We develop mathematical tools in order to study these systems and we delineate the decidability frontier for the termination, boundedness, maintainability and coverability problems for these systems.

L'un des problèmes fondamentaux de test pour les systèmes à événements discrets (SEDs) est l'identification d'un état final, c'est-à-dire, étant donné un système dont l'état courant est inconnu, trouver une séquence d'événements d'entrée pouvant le conduire à un état connu. Les séquences de synchronisation (SS), sans information de sortie, sont une solution classique à ce problème. Dans cette thèse, nous étudions la détermination des SS pour des systèmes modélisés par des réseaux de Petri synchronisés (SynPN) non bornés, une classe de réseaux de Petri avec des entrées. Dans la première partie de cette thèse, nous développons deux méthodes: 1) construction d'une représentation finie, appelée improved modified coverability graph (IMCG), pour d'écrire exactement l'espace d'états infini d'un 1-place-unbounded SynPN; 2) conversion d'un 1-place-unbounded SynPN en un automate pondéré (WA) fini et sauf équivalent. Les deux graphes sont ainsi potentiellement des outils puissants pour déterminer les SS pour une telle sous-classe de réseaux de Petri. Dans la seconde partie de cette thèse, nous développons des algorithmes de calcul pour deux problèmes de synchronisation de localisation dans le cas où l'IMCG ou le WA sont déterministes : synchronisation sur un seul nœud et synchronisation sur un sous-ensemble de nœuds de ces deux graphes. L'avantage de ces algorithmes de calcul est de réduire le calcul sur les graphes globaux (IMCG ou WA) à celui du plus petit sous-graphe: la composante fortement connectée ergodique peut réduire l'effort de calcul mais peut également être appliquée lorsque le IMCG ou le WA équivalent déterministes ne sont pas fortement connexes / One of the fundamental testing problems for discrete event systems (DESs) is the identification of a final state, i.e., given a system whose current state is unknown, find an input sequence that can drive it to a known state. Synchronizing sequences (SSs), without output information, are one conventional solution to this problem. In this thesis, we address the computation of SSs for systems modeled by unbounded synchronized Petri nets (SynPNs), a class of Petri nets with inputs. In the first part of this thesis, we utilize two methods: 1) construct a finite representation, called improved modified coverability graph (IMCG), to exactly describe the infinite state space of a 1-place-unbounded SynPN; 2) convert a 1-place-unbounded SynPN into an equivalent finite location weighted automaton (WA) with safety conditions. Both graphs are thus, potentially, useful tools to compute SSs for such subclass of nets. In the second part of this thesis, we develop computation algorithms for two location synchronization problems in the case either the IMCG or the WA is deterministic: synchronization into a single node and synchronization into a subset of nodes of these two graphs. The advantage of these computation algorithms consists in reducing the computation on the global graphs (IMCGs or WAs) to the one on the smaller subgraph: the ergodic strongly connected component (SCC), which can reduce the computational effort and furthermore can also be applied when the converted deterministic IMCG or WA is not strongly connected

Dans le transport ferroviaire, le coût et la disponibilité du matériel roulant sont des questions majeures. Pour optimiser le coût de maintenance du système de transport ferroviaire, une solution consiste à mieux détecter et diagnostiquer les défaillances. Actuellement, les architectures de surveillance/diagnostic centralisées atteignent leurs limites et imposent d'innover. Cette innovation technologique peut se matérialiser par la mise en oeuvre d’architectures embarquées de surveillance/diagnostic distribuées et communicantes afin de détecter et localiser plus rapidement les défaillances et de les valider dans le contexte opérationnel du train. Les présents travaux de doctorat, menés dans le cadre du FUI SURFER (SURveillance active Ferroviaire) coordonné par Bombardier, visent à proposer une démarche méthodologique d’évaluation de la sûreté de fonctionnement d’architectures de surveillance/diagnostic. Pour ce faire, une caractérisation et une modélisation génériques des architectures de surveillance/diagnostic basée sur le formalisme des Réseaux de Petri stochastiques ont été proposées. Ces modèles génériques intègrent les réseaux de communication (et les modes de défaillances associés) qui constituent un point dur des architectures de surveillance/diagnostic retenues. Les modèles proposés ont été implantés et validés théoriquement par simulation et une étude de sensibilité de ces architectures de surveillance/diagnostic à certains paramètres influents a été menée. Enfin, ces modèles génériques sont appliqués sur un cas réel du domaine ferroviaire, les systèmes accès voyageurs des trains, qui sont critiques en matière de disponibilité et diagnosticabilité. / In the railway transport, rolling stock cost and availability are major concern. To optimise the maintenance cost of the railway transport system, one solution consists in better detecting and diagnosing failures. Today, centralized monitoring/diagnosis architectures reach their limits. Innovation is therefore necessary. This technological innovation may be implemented with embedded distributed and communicating monitoring/diagnosis architectures in order to faster detect and localize failures and to make a validation with respect to the train operational context.The present research work, carried out as part of the SURFER FUI project (french acronym standing for railway active monitoring) lead by Bombardier, aim to propose a methodology to assess dependability of monitoring/diagnosis architectures. To this end, a caracterisation et une modélisation génériques des monitoring/diagnosis architectures based on the stochastic Petri Nets have been proposed. These generic models take into account communication networks (and the associated failure modes), which constitutes a central point of the studied monitoring/diagnosis architectures. The proposed models have been edited and theoretically validated by simulation. A sensitiveness of the monitoring/diagnosis architectures to parameters has been studied. Finally, these generic models have applied to a real case of the railway transport, train passenger access systems, which are critical in term of availability and diagnosability.

Le travail présenté dans cette thèse constitue une contribution originale à lamodélisation et à l'analyse de performances des systèmes de vélos en libre-service. De nombreuses villes en Europe ont suscité un intérêt considérable et un engouement à l'égard de ce nouveau mode de transport écologique (Vélib' à Paris, Vélov'v à Lyon, Bicing à Barcelone, ...) et dont les progrès technologiques ne cessent de les faire émerger dans les quatre coins dumonde. Contrairement aux systèmes de transport traditionnels, très peu d'étudesfondamentales ont été menées et pourtant, de nombreuses questions émergent, la principale étant celle d'un rééquilibrage (régulation) de la distribution de vélos dans les différentes stations afin de satisfaire au mieux les demandes des usagers. C'est dans ce cadre que s'inscrit cette thèse de doctorat portant sur la modélisation, l'analyse et l'évaluation de performances de ce mode de transport en libre service. Ce travail, basé sur les réseaux de Petri, est d'une aide précieuse pour la mise en oeuvre, l'exploitation et la régulation de ce type de systèmes.La complexité dynamique de tels systèmes, perçus comme des systèmes à événements discrets, nous a conduit au développement d'une approche à base d'une classe particulière de réseaux de Petri stochastiques ayant des arcs à poids variables pertinents aussi bien pour l'analyse que pour la simulation. Un ensemble de modèles et de méthodes d'analyse associées sont développés en vue de leur régulation, en prenant en compte différents paramètres de décision qui les caractérisent notamment le nombre de stations, la capacité de chaque station, les seuils de régulation, la capacité des véhicules de régulation, le type et/ou la fréquence de régulation choisi (périodique ou continue), …. En plus d'être paramétrables, les modèles proposés permettent d'étudier plusieurs configurations en fonction de différents modes de fonctionnement possibles (mode sans régulation, mode avec régulation, mode dynamique, mode statique, etc). La présentation de cette thèse comporte plusieurs illustrations et applicationspermettant d'aider le lecteur à la compréhension du travail développé.A notre connaissance, il s'agit d'un premier travail du genre dans la littérature sur les réseaux de Petri et plus généralement, l'un des premiers sur les systèmes de vélos en libre-service. / Public Bicycle-Sharing Systems (PBSS) have been appearing in more and more cities around the world in the last few years. Although their apparent success as an alternative form of public transportation mode, there are major challenges confronting the operators while few scientific works are available to support such complex dynamical systems to influence their economic viability and operational efficiency. One of the most crucial factors for the success of a PBS system is its ability to ensure that bicycles are available for pick up and vacant berths available for bicycle drop off at every station. In this thesis, we develop an original discrete event approach for modelling and performance evaluation of public bicycle-sharing systems by using Petri nets with time, inhibitor arcs and variable arc weights.

Cette thèse porte sur le diagnostic des systèmes à événements discrets modélisés par des Réseaux de Petri labellisés (RdP-L). Les problèmes de diagnostic monolithique et de diagnostic modulaire sont abordés. Des contributions sont proposées pour résoudre les problèmes d'explosion combinatoire et de complexité de calcul. Dans le cadre de l'analyse de la diagnosticabilité monolithique, certaines règles de réduction sont proposées comme un complément pour la plupart des techniques existantes de l'analyse de la diagnosticabilité, qui simplifient le modèle RdP-L tout en préservant sa propriété de diagnosticabilité. Pour un RdP-L sauf et vivant, une nouvelle condition suffisante pour la diagnosticabilité est proposée. Pour un RdR-L borné et non bloquant après l'occurrence d'une faute, l'analyse à-la-volée est améliorée en utilisant la notion d'explications minimales qui permettent de compacter l'espace d'état ; et en utilisant des T-semiflots pour trouver rapidement un cycle indéterminé. Une analyse à-la-volée utilisant Verifier Nets (VN) est proposée pour analyser à la fois les RdP-L bornés et non-bornés, ce qui permet d'obtenir un compromis entre efficacité du calcul et limitation des explosions combinatoires. Dans le cadre de l'analyse de la diagnosticabilité modulaire, une nouvelle approche est proposée pour les RdP-Ls décomposés. Les règles de réduction, qui préservent la propriété de la diagnosticabilité modulaire, sont appliquées pour simplifier le modèle initial. La diagnosticabilité locale est analysée en construisant le VN et le Graphe d'Accessibilité Modifié (MAG) du modèle local. La diagnosticabilité modulaire est vérifiée en construisant la composition parallèle du MAG et des graphes d'accessibilités d'autres modules du système. La complexité de calcul est inférieure à celles des autre approches dans la littérature. D'autre part, l'explosion combinatoire est également réduite en utilisant la technique de ε-réduction / This thesis deals with fault diagnosis of discrete event systems modeled by labeled Petri nets (LPN). The monolithic diagnosability and modular diagnosability issues are addressed. The contributions are proposed to reduce the combinatorial explosion and the computational complexity problems. Regarding monolithic diagnosability analysis, some reduction rules are proposed as a complement for most diagnosability techniques, which simplify the LPN model and preserve the diagnosability property. For a safe and live LPN, a new sufficient condition for diagnosability is proposed. For a bounded LPN that does not deadlock after a fault, the on-the-fly diagnosability analysis is improved by using minimal explanations to compact the state space; and by using T-invariants, to find quickly an indeterminate cycle. An on-the-fly diagnosability analysis using Verifier Nets (VN) is proposed to analyze both bounded and unbounded LPN, which achieves a compromise between computation efficiency and combinatorial explosion limitation. Regarding modular diagnosability analysis, a new approach is proposed for decomposed LPNs model. Reduction rules, that preserve the modular diagnosability property, are applied to simplify the model. The local diagnosability is analyzed by building the VN and the Modified Reachability Graph (MRG) of the local model. The modular diagnosability is verified by building the parallel composition of the MRG and the reachability graphs of other modules of the system. We prove in this study that the computational complexity of our approach is lower than existing approaches of literature. The combinatorial explosion is also reduced by using the ε -reduction technique.

Avec l'évolution de la technologie, l'homme a procédé à la conception de systèmes de plus en plus complexes mais aussi de plus en plus sensibles aux défauts qui peuvent les affecter. Une procédure de diagnostic contribuant au bon déroulement du processus est ainsi nécessaire. Dans ce contexte, le but de cette thèse est le diagnostic des systèmes à événements discrets modélisés par des Réseaux de Petri Étiquetés (RdPE) partiellement observables. Sous l'hypothèse que chaque défaut est modélisé par le tir d'une transition non observable, deux approches de diagnostic à base d'estimation d'état sont développées. Une première approche composée de deux étapes consiste à estimer l'ensemble des marquages de base sur un horizon élémentaire glissant. La première étape consiste à déterminer un ensemble de vecteurs candidats à partir d'une approche algébrique. La deuxième étape consiste à éliminer les solutions candidates calculées qui ne sont pas associées à une trajectoire possible du RdPE. Comme l'ensemble des marquages de base pourra aussi être important, une deuxième approche de diagnostic évitera cet écueil en n'estimant pas les marquages. Une technique de relaxation des problèmes de Programmation Linéaire en Nombres Entiers (PLNE) sur un horizon fuyant est utilisée afin d'avoir un diagnostic en temps polynomial. / With the evolution of technology, humans have made available systems increasingly complex but also increasingly sensitive to faults that may affect it. A diagnostic procedure which contributes to the smooth running of the process is thus necessary. In this context, the aim of this thesis is the diagnosis of discrete event systems modeled by partially observed Labeled Petri Nets (LPNs). Under the assumption that each defect is modeled by the firing of an unobservable transition, two diagnostic approaches based on state estimation are developed. A first approach is to estimate the set of basis markings on a sliding elementary horizon. This approach is carried out in two steps. The first step is to determine a set of candidate vectors from an algebraic approach. The second step is to eliminate the calculated candidate solutions that are not associated with a possible trajectory of the LPN. As the set of basis markings can also be huge, a second diagnostic approach will avoid this pitfall by not estimating the markings. A relaxation technique of Integer Linear Programming (ILP) problems on a receding horizon is used to have a diagnosis in polynomial time.

L’objectif de ce travail est d’exploiter les potentialités offertes par la conduite coopérative afin de fluidifier le trafic au niveau des intersections isolées. Pour ce faire, nous avons proposé un nouveau système de régulation au sein des intersections en s’inspirant du principe de l’intersection autonome. Nous avons appelé notre système : SVAC (système du véhicule-actionneur coopératif). Il repose sur la possibilité des échanges d’information entre le véhicule et son environnement de conduite.Le SVAC permet une régulation plus précise du trafic puisqu’il se base sur les requêtes de droit de passage envoyées par les véhicules réellement présents dans l’intersection. En outre, grâce à la signalisation à bord, la régulation consiste à définir les séquences de passage des véhicules, ce qui permet de personnaliser la signalisation. Le gain de précision soulève plusieurs obstacles. D’une part, nous nous heurtons systématiquement à l’absence de modèles mathématiques permettant d’aborder le problème. D’autre part, la simple énumération des séquences implique une explosion combinatoire, ce qui ne convient pas à l’application temps-réelle de la régulation des intersections. Pour s’affranchir des deux problématiques nous avons utilisé les réseaux de Petri P-temporisés. Le modèle nous a permis de décrire sous la forme d’équations mathématiques les compteurs des différents évènements observés par les véhicules. Deux objectifs de régulation ont été dégagés après avoir déduit le temps moyen d’attente basé sur la formule de Little. Le premier consiste à vider les intersections au plus tôt. Nous avons proposé un algorithme de programmation dynamique et deux heuristiques. La première heuristique est directement issue de l’analyse des propriétés du problème posé. La deuxième est basée sur l’algorithme de colonies de fourmis. En effet, le problème défini est un cas particulier du problème du voyageur de commerce. Le deuxième objectif de régulation consiste à minimiser instantanément la longueur de la file d’attente. Dans ce cadre, nous avons supposé le fonctionnement à vitesse maximale du réseau de Petri. L’utilisation des contraintes sur les ressources nous a permis de définir des règles simples de régulation en utilisant le mapping.Dans ce mémoire, nous avons utilisé la simulation microscopique basée sur les lois de poursuite pour s’approcher du comportement de conduite. La simulation a servi pour la comparaison des différentes approches proposées dans ce mémoire avec les régulateurs adaptatifs et les intersections autonomes. Dans tous les cas notre approche se distingue par un gain de capacité, ce qui nous a encouragé de reproduire le SVAC à travers un prototype de robots. Cette maquette montre la faisabilité du système au moins pour des applications industrielles. / The aim of this work is to benefit from the potential of the cooperative driving in order to optimize the traffic throughput at isolated intersections. To achieve this objective, we have proposed a new traffic control system for isolated intersections: Cooperative Vehicle-Actuation Signalization (CVAS). The concept of this new system is based on the assumption of the ability of exchanging information between each vehicle and the surrounding vehicles or the nearby infrastructure.The system allows more precise control of the traffic since it determines the right-of-way of each vehicle according to its corresponding data sent by the embedded wireless device. The right-of-way is displayed to the driver by means of the onboard signalization. The control system determines the sequence of the vehicles to be directed through the intersection. For the sake of benefiting the improvement brought by the new system, we face several challenges. On the one hand, we are confronted with the absence of a mathematical model to address the control problem. On the other hand, despite the fact that the optimal passing sequence of vehicles can be found by the simple enumeration of all feasible sequences, the exhaustive search does not fulfill the requirements of the real-time application. To overcome these two problems, we seek help from the P-timed Petri nets. This mathematical modeling tool is able to describe the events observed by the position markers in the form of mathematical equations. Two different objectives of the control have been derived from the Little's formula. The first one aims to minimize the maximum exit time of vehicles present in the intersection. An algorithm of dynamic programming and two heuristics have been proposed to achieve this objective. The first heuristic is based on the analysis of the properties of the control problem. The second heuristic is based on the analogy between the dealt problem and the problem of Traveling Salesman Problem, which can be solved successfully by the algorithm of ant colony system. The second objective of the control is to instantly minimize the queue length. A protocol of relaying the right of way has been determined from the assumption of a Petri net that operates at its maximum speed. This simple protocol of control can be extended to all possible layouts of the isolated intersections by using the technique of “mapping”.In this work, a microscopic model (car-following model) is used to simulate the driving behavior. The simulations show that the CVAS system outperforms the other systems which are popularly used at present. It is even better than some innovative systems based on the technology of the cooperative driving. The good results encouraged us to replicate the system under real conditions through a prototype of NXT robots. The tests of this prototype prove the feasibility of the system at least for industrial applications.

Les travaux présentés dans cette thèse portent sur l'ordonnancement d'applications sur des plate- formes hétérogènes à grande échelle. Dans la mesure où le problème général est trop complexe pour être résolu de façon exacte, nous considérons deux relaxations. Tâches divisibles : La première partie est consacrée aux tâches divisibles, qui sont des appli- cations parfaitement parallèles et pouvant être arbitrairement subdivisées pour être réparties sur de nombreux processeurs. Nous cherchons à minimiser le temps de travail total lors de l'exécution de plusieurs applications aux caractéristiques différentes sur un réseau linéaire de processeurs, sachant que les données peuvent être distribuées en plusieurs tournées. Le nombre de ces tour- nées étant fixé, nous décrivons un algorithme optimal pour déterminer précisément ces tournées, et nous montrons que toute solution optimale requiert un nombre infini de tournées, résultat restant vrai sur des plate-formes non plus linéaires mais en étoile. Nous comparons également notre méthode à des méthodes déjà existantes. Ordonnancement en régime permanent : La seconde partie s'attache à l'ordonnancement de nombreuses copies du même graphe de tâches représentant une application donnée. Au lieu de chercher à minimiser le temps de travail total, nous optimisons uniquement le cœur de l'or- donnancement. Tout d'abord, nous étudions des ordonnancements cycliques de ces applications sur des plate-formes hétérogènes, basés sur une seule allocation pour faciliter leur utilisation. Ce problème étant NP-complet, nous donnons non seulement un algorithme optimal, mais éga- lement différentes heuristiques permettant d'obtenir rapidement des ordonnancements efficaces. Nous les comparons à ces méthodes classiques d'ordonnancement, telles que HEFT. Dans un second temps, nous étudions des applications plus simples, faites de nombreuses tâches indépendantes, que l'on veut exécuter sur une plate-forme en étoile. Les caractéristiques de ces tâches variant, nous supposons qu'elles peuvent être modélisées par des variables aléatoires. Cela nous permet de proposer une ε-approximation dans un cadre clairvoyant, alors que l'ordonnan- ceur dispose de toutes les informations nécessaires. Nous exposons également des heuristiques dans un cadre non-clairvoyant. Ces différentes méthodes montrent que malgré la dynamicité des tâches, il reste intéressant d'utiliser un ordonnancement statique et non des stratégies plus dynamiques comme On-Demand. Nous nous intéressons ensuite à des applications, dont plusieurs tâches sont répliquées sur plu- sieurs processeurs de la plate-forme de calcul afin d'améliorer le débit total. Dans ce cas, même si les différentes instances sont distribuées aux processeurs tour à tour, le calcul du débit est difficile. Modélisant le problème par des réseaux de Petri temporisés, nous montrons comment le calculer, prouvant également que ce calcul peut être fait en temps polynomial avec le modèle Strict One-Port. Enfin, le dernier chapitre est consacré à l'application de ces techniques à un processeur multi- cœur hétérogène, le Cell d'IBM. Nous présentons donc un modèle théorique de ce processeur ainsi qu'un algorithme d'ordonnancement adapté. Une implémentation réelle de cet ordonnanceur a été effectuée, permettant d'obtenir des débits intéressants tout en simplifiant l'utilisation de ce processeur et validant notre modèle théorique.