L'introduction de systèmes instrumentés dédiés aux applications de sécurité impose l'évaluation de leur sûreté de fonctionnement. On utilise généralement pour cela les bases de données de fiabilité génériques. Cependant, le retour d'expérience pour ces systèmes qui présentent en général des défaillances rares est insuffisant pour valider les résultats obtenus. En outre, la collecte de données de fiabilité et leur extrapolation à d'autres composants introduisent des incertitudes.<br />Les travaux de cette thèse portent sur la problématique de la prise en compte des incertitudes relatives aux données de fiabilité des composants pour l'évaluation de la sûreté de fonctionnement des systèmes par le formalisme des sous ensembles flous. La méthodologie proposée est appliquée à l'évaluation des probabilités de défaillance des Systèmes Instrumentés de Sécurité (SIS) en présence de données de fiabilité imprécises. Nous introduisons deux nouveaux facteurs d'importance pour aider le concepteur. En outre, nous proposons une méthodologie d'aide à la conception des SIS basée sur la modélisation par réseaux de fiabilité et l'optimisation par des algorithmes génétiques de la structure des SIS pour le respect des niveaux d'intégrité de sécurité (SIL) exigés.

L'introduction de systèmes instrumentés dédiés aux applications de sécurité impose l'évaluation de leur sûreté de fonctionnement. On utilise généralement pour cela les bases de données de fiabilité génériques. Cependant, le retour d'expérience pour ces systèmes qui présentent en général des défaillances rares est insuffisant pour valider les résultats obtenus. En outre, la collecte de données de fiabilité et leur extrapolation à d'autres composants introduisent des incertitudes. Les travaux de cette thèse portent sur la problématique de la prise en compte des incertitudes relatives aux données de fiabilité des composants pour l'évaluation de la sûreté de fonctionnement des systèmes par le formalisme des sous ensembles flous. La méthodologie proposée est appliquée à l'évaluation des probabilités de défaillance des Systèmes Instrumentés de Sécurité (SIS) en présence de données de fiabilité imprécises. Nous introduisons deux nouveaux facteurs d'importance pour aider le concepteur. En outre, nous proposons une méthodologie d'aide à la conception des SIS basée sur la modélisation par réseaux de fiabilité et l'optimisation par des algorithmes génétiques de la structure des SIS pour le respect des niveaux d'intégrité de sécurité (SIL) exigés / The use of safety related systems imposes to evaluate their dependability. Laboratory data and generic data are often used to provide failure data of safety components to evaluate their dependability parameters. However, due to the lower solicitation of safety systems in plant, safety components have not been operating long enough to provide statistical valid failure data. Furthermore, measuring and collecting failure data have uncertainty associated with them, and borrowing data from laboratory and generic data sources involve uncertainty as well. Our contribution is to propose a fuzzy approach to evaluate dependability parameters of safety systems when there is an uncertainty about dependability parameters of systems components. This approach is applied to determine the failure probability on demand of Safety Instrumented Systems (SIS) in presence of uncertainty. Furthermore, we present an optimal design of SIS by using reliability graphs and genetic algorithms to identify the choice of components and design configuration in a SIS to meet the required SIL

In this thesis, we consider the k-edge connected L-hop-constrained network design problem. Given a weighted graph G=(N,E), a set D of pairs of terminal nodes, and two integers k,L > 1, it consists in finding in G the minimum cost subgraph containing at least k edge-disjoint paths of at most L edges between each pair in D. This problem is of great interest in today's telecommunication industry, where highly survivable networks need to be constructed.<p><p>We first study the particular case where the set of demands D is reduced to a single pair {s,t}. We propose an integer programming formulation for the problem, which consists in the st-cut and trivial inequalities, along with the so-called L-st-path-cut inequalities. We show that these three classes of inequalities completely describe the associated polytope when k=2 and L=2 or 3, and give necessary and sufficient conditions for them to be facet-defining. We also consider the dominant of the associated polytope, and discuss how the previous inequalities can be separated in polynomial time.<p><p>We then extend the complete and minimal description obtained above to any number k of required edge-disjoint L-st-paths, but when L=2 only. We devise a cutting plane algorithm to solve the problem, using the previous polynomial separations, and present some computational results.<p><p>After that, we consider the case where there is more than one demand in D. We first show that the problem is strongly NP-hard, for all L fixed, even when all the demands in D have one root node in common. For k=2 and L=2,3, we give an integer programming formulation, based on the previous constraints written for all pairs {s,t} in D. We then proceed by giving several new classes of facet-defining inequalities, valid for the problem in general, but more adapted to the rooted case. We propose separation procedures for these inequalities, which are embedded within a Branch-and-Cut algorithm to solve the problem when L=2,3. Extensive computational results from it are given and analyzed for both random and real instances.<p><p>Since those results appear less satisfactory in the case of arbitrary demands (non necessarily rooted), we present additional families of valid inequalites in that situation. Again, separation procedures are devised for them, and added to our previous Branch-and-Cut algorithm, in order to see the practical improvement granted by them.<p><p>Finally, we study the problem for greater values of L. In particular, when L=4, we propose new families of constraints for the problem of finding a subgraph that contains at least two L-st-paths either node-disjoint, or edge-disjoint. Using these, we obtain an integer programming formulation in the space of the design variables for each case.<p><p>------------------------------------------------<p><p>Dans cette thèse, nous considérons le problème de conception de réseau k-arete connexe à chemins L-bornés. Etant donné un graphe pondéré G=(N,E), un ensemble D de paires de noeuds terminaux, et deux entiers k,L > 1, ce problème consiste à trouver, dans G, un sous-graphe de cout minimum tel que, entre chaque paire dans D, il existe au moins k chemins arete-disjoints de longueur au plus L. Ce problème est d'un grand intéret dans l'industrie des télécommunications, où des réseaux hautement fiables doivent etre construits.<p><p>Nous étudions tout d'abord le cas particulier où l'ensemble des demandes D est réduit à une seule paire de noeuds. Nous proposons une formulation du problème sous forme de programme linéaire en nombres entiers, laquelle consiste en les inégalités triviales et de coupe, ainsi que les inégalités dites de L-chemin-coupe. Nous montrons que ces trois types d'inégalités décrivent complètement le polytope associé lorsque k=2 et L=2,3, et donnons des conditions nécessaires et suffisantes pour que celles-ci en définissent des facettes. Nous considérons également le dominant du polytope associé et discutons de la séparation polynomiale des trois classes précédentes.<p><p>Nous étendons alors cette description complète et minimale à tout nombre k de chemins arete-disjoints de longueur au plus 2. De plus, nous proposons un algorithme de plans coupants utilisant les précédentes séparations polynomiales, et en présentons quelques résultats calculatoires, pour tout k>1 et L=2,3.<p><p>Nous considérons ensuite le cas où plusieurs demandes se trouvent dans D. Nous montrons d'abord que le problème est fortement NP-dur, pour tout L fixé et ce, meme si les demandes sont toutes enracinées en un noeud. Pour k=2 et L=2,3, nous donnons une formulation du problème sous forme de programme linéaire en nombres entiers. Nous proposons également de nouvelles classes d'inégalités valides, pour lesquelles nous réalisons une étude faciale. Celles-ci sont alors séparées dans le cadre d'un algorithme de coupes et branchements pour résoudre des instances aléatoires et réelles du problème.<p><p>Enfin, nous étudions le problème pour de plus grandes valeurs de L. En particulier, lorsque L=4, nous donnons de nouvelles familles de contraintes pour le problème consistant à déterminer un sous-graphe contenant entre deux noeuds fixés au moins deux chemins de longueur au plus 4, que ceux-ci doivent etre arete-disjoints ou noeud-disjoints. Grace à ces dernières, nous parvenons à donner une formulation naturelle du problème dans chacun de ces deux cas. <p> / Doctorat en sciences, Spécialisation Informatique / info:eu-repo/semantics/nonPublished