Optimal testing and repairing a failed series system
Identifieur interne : 000614 ( PascalFrancis/Curation ); précédent : 000613; suivant : 000615Optimal testing and repairing a failed series system
Auteurs : Mikhail Y. Kovalyov [Biélorussie] ; Marie-Claude Portmann [France] ; Ammar Oulamara [France]Source :
- Journal of combinatorial optimization [ 1382-6905 ] ; 2006.
Descripteurs français
- Pascal (Inist)
English descriptors
- KwdEn :
Abstract
We consider a series repairable system that includes n components and assume that it has just failed because exactly one of its components has failed. The failed component is unknown. Probability of each component to be responsible for the failure is given. Each component can be tested and repaired at given costs. Both testing and repairing operations are assumed to be perfect, that is, the result of testing a component is a true information that this component is failed or active (not failed), and the result of repairing is that the component becomes active. The problem is to find a sequence of testing and repairing operations over the components such that the system is always repaired and the total expected cost of testing and repairing the components is minimized. We show that this problem is equivalent to minimizing a quadratic pseudo-boolean function. Polynomially solvable special cases of the latter problem are identified and a fully polynomial time approximation scheme (FPTAS) is derived for the general case. Computer experiments are provided to demonstrate high efficiency of the proposed FPTAS. In particular, it is able to find a solution with relative error s = 0.1 for problems with more than 4000 components within 5 minutes on a standard PC with 1.2 Mhz processor.
| pA |
|
|---|
Links toward previous steps (curation, corpus...)
- to stream PascalFrancis, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000419
Links to Exploration step
Pascal:06-0493027Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Optimal testing and repairing a failed series system</title><author><name sortKey="Kovalyov, Mikhail Y" sort="Kovalyov, Mikhail Y" uniqKey="Kovalyov M" first="Mikhail Y." last="Kovalyov">Mikhail Y. Kovalyov</name><affiliation wicri:level="1"><inist:fA14 i1="01"><s1>Faculty of Economics, Belarusian State University, and United Institute of Informatics Problems, National Academy of Sciences of Belarus, Skorini 4</s1><s2>220050 Minsk</s2><s3>BLR</s3><sZ>1 aut.</sZ></inist:fA14><country>Biélorussie</country></affiliation></author><author><name sortKey="Portmann, Marie Claude" sort="Portmann, Marie Claude" uniqKey="Portmann M" first="Marie-Claude" last="Portmann">Marie-Claude Portmann</name><affiliation wicri:level="1"><inist:fA14 i1="02"><s1>MACSI Project LORIA-INRIA, Ecole des Mines de Nancy, Pare de Saurupt</s1><s2>540042 Nancy</s2><s3>FRA</s3><sZ>2 aut.</sZ><sZ>3 aut.</sZ></inist:fA14><country>France</country></affiliation></author><author><name sortKey="Oulamara, Ammar" sort="Oulamara, Ammar" uniqKey="Oulamara A" first="Ammar" last="Oulamara">Ammar Oulamara</name><affiliation wicri:level="1"><inist:fA14 i1="02"><s1>MACSI Project LORIA-INRIA, Ecole des Mines de Nancy, Pare de Saurupt</s1><s2>540042 Nancy</s2><s3>FRA</s3><sZ>2 aut.</sZ><sZ>3 aut.</sZ></inist:fA14><country>France</country></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">INIST</idno><idno type="inist">06-0493027</idno><date when="2006">2006</date><idno type="stanalyst">PASCAL 06-0493027 INIST</idno><idno type="RBID">Pascal:06-0493027</idno><idno type="wicri:Area/PascalFrancis/Corpus">000419</idno><idno type="wicri:Area/PascalFrancis/Curation">000614</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Optimal testing and repairing a failed series system</title><author><name sortKey="Kovalyov, Mikhail Y" sort="Kovalyov, Mikhail Y" uniqKey="Kovalyov M" first="Mikhail Y." last="Kovalyov">Mikhail Y. Kovalyov</name><affiliation wicri:level="1"><inist:fA14 i1="01"><s1>Faculty of Economics, Belarusian State University, and United Institute of Informatics Problems, National Academy of Sciences of Belarus, Skorini 4</s1><s2>220050 Minsk</s2><s3>BLR</s3><sZ>1 aut.</sZ></inist:fA14><country>Biélorussie</country></affiliation></author><author><name sortKey="Portmann, Marie Claude" sort="Portmann, Marie Claude" uniqKey="Portmann M" first="Marie-Claude" last="Portmann">Marie-Claude Portmann</name><affiliation wicri:level="1"><inist:fA14 i1="02"><s1>MACSI Project LORIA-INRIA, Ecole des Mines de Nancy, Pare de Saurupt</s1><s2>540042 Nancy</s2><s3>FRA</s3><sZ>2 aut.</sZ><sZ>3 aut.</sZ></inist:fA14><country>France</country></affiliation></author><author><name sortKey="Oulamara, Ammar" sort="Oulamara, Ammar" uniqKey="Oulamara A" first="Ammar" last="Oulamara">Ammar Oulamara</name><affiliation wicri:level="1"><inist:fA14 i1="02"><s1>MACSI Project LORIA-INRIA, Ecole des Mines de Nancy, Pare de Saurupt</s1><s2>540042 Nancy</s2><s3>FRA</s3><sZ>2 aut.</sZ><sZ>3 aut.</sZ></inist:fA14><country>France</country></affiliation></author></analytic><series><title level="j" type="main">Journal of combinatorial optimization</title><title level="j" type="abbreviated">J. comb. optim.</title><idno type="ISSN">1382-6905</idno><imprint><date when="2006">2006</date></imprint></series></biblStruct></sourceDesc><seriesStmt><title level="j" type="main">Journal of combinatorial optimization</title><title level="j" type="abbreviated">J. comb. optim.</title><idno type="ISSN">1382-6905</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Boolean function</term><term>Combinatorial optimization</term><term>Failure detection</term><term>Failures</term><term>Polynomial approximation</term><term>Polynomial time</term><term>Quadratic function</term><term>Repair</term><term>Repairable system</term><term>Repairing</term><term>Series system</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Optimisation combinatoire</term><term>Approximation polynomiale</term><term>Fonction booléenne</term><term>Fonction quadratique</term><term>Défaillance</term><term>Dépannage</term><term>Réparation</term><term>Système réparable</term><term>Système série</term><term>Temps polynomial</term><term>Détection panne</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">We consider a series repairable system that includes n components and assume that it has just failed because exactly one of its components has failed. The failed component is unknown. Probability of each component to be responsible for the failure is given. Each component can be tested and repaired at given costs. Both testing and repairing operations are assumed to be perfect, that is, the result of testing a component is a true information that this component is failed or active (not failed), and the result of repairing is that the component becomes active. The problem is to find a sequence of testing and repairing operations over the components such that the system is always repaired and the total expected cost of testing and repairing the components is minimized. We show that this problem is equivalent to minimizing a quadratic pseudo-boolean function. Polynomially solvable special cases of the latter problem are identified and a fully polynomial time approximation scheme (FPTAS) is derived for the general case. Computer experiments are provided to demonstrate high efficiency of the proposed FPTAS. In particular, it is able to find a solution with relative error s = 0.1 for problems with more than 4000 components within 5 minutes on a standard PC with 1.2 Mhz processor.</div></front></TEI><inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>1382-6905</s0></fA01><fA03 i2="1"><s0>J. comb. optim.</s0></fA03><fA05><s2>12</s2></fA05><fA06><s2>3</s2></fA06><fA08 i1="01" i2="1" l="ENG"><s1>Optimal testing and repairing a failed series system</s1></fA08><fA11 i1="01" i2="1"><s1>KOVALYOV (Mikhail Y.)</s1></fA11><fA11 i1="02" i2="1"><s1>PORTMANN (Marie-Claude)</s1></fA11><fA11 i1="03" i2="1"><s1>OULAMARA (Ammar)</s1></fA11><fA14 i1="01"><s1>Faculty of Economics, Belarusian State University, and United Institute of Informatics Problems, National Academy of Sciences of Belarus, Skorini 4</s1><s2>220050 Minsk</s2><s3>BLR</s3><sZ>1 aut.</sZ></fA14><fA14 i1="02"><s1>MACSI Project LORIA-INRIA, Ecole des Mines de Nancy, Pare de Saurupt</s1><s2>540042 Nancy</s2><s3>FRA</s3><sZ>2 aut.</sZ><sZ>3 aut.</sZ></fA14><fA20><s1>279-295</s1></fA20><fA21><s1>2006</s1></fA21><fA23 i1="01"><s0>ENG</s0></fA23><fA43 i1="01"><s1>INIST</s1><s2>26611</s2><s5>354000133266580060</s5></fA43><fA44><s0>0000</s0><s1>© 2006 INIST-CNRS. All rights reserved.</s1></fA44><fA45><s0>8 ref.</s0></fA45><fA47 i1="01" i2="1"><s0>06-0493027</s0></fA47><fA60><s1>P</s1></fA60><fA61><s0>A</s0></fA61><fA64 i1="01" i2="1"><s0>Journal of combinatorial optimization</s0></fA64><fA66 i1="01"><s0>USA</s0></fA66><fC01 i1="01" l="ENG"><s0>We consider a series repairable system that includes n components and assume that it has just failed because exactly one of its components has failed. The failed component is unknown. Probability of each component to be responsible for the failure is given. Each component can be tested and repaired at given costs. Both testing and repairing operations are assumed to be perfect, that is, the result of testing a component is a true information that this component is failed or active (not failed), and the result of repairing is that the component becomes active. The problem is to find a sequence of testing and repairing operations over the components such that the system is always repaired and the total expected cost of testing and repairing the components is minimized. We show that this problem is equivalent to minimizing a quadratic pseudo-boolean function. Polynomially solvable special cases of the latter problem are identified and a fully polynomial time approximation scheme (FPTAS) is derived for the general case. Computer experiments are provided to demonstrate high efficiency of the proposed FPTAS. In particular, it is able to find a solution with relative error s = 0.1 for problems with more than 4000 components within 5 minutes on a standard PC with 1.2 Mhz processor.</s0></fC01><fC02 i1="01" i2="X"><s0>001D01A04</s0></fC02><fC02 i1="02" i2="X"><s0>001D01A06</s0></fC02><fC03 i1="01" i2="X" l="FRE"><s0>Optimisation combinatoire</s0><s5>01</s5></fC03><fC03 i1="01" i2="X" l="ENG"><s0>Combinatorial optimization</s0><s5>01</s5></fC03><fC03 i1="01" i2="X" l="SPA"><s0>Optimización combinatoria</s0><s5>01</s5></fC03><fC03 i1="02" i2="X" l="FRE"><s0>Approximation polynomiale</s0><s5>02</s5></fC03><fC03 i1="02" i2="X" l="ENG"><s0>Polynomial approximation</s0><s5>02</s5></fC03><fC03 i1="02" i2="X" l="SPA"><s0>Aproximación polinomial</s0><s5>02</s5></fC03><fC03 i1="03" i2="X" l="FRE"><s0>Fonction booléenne</s0><s5>03</s5></fC03><fC03 i1="03" i2="X" l="ENG"><s0>Boolean function</s0><s5>03</s5></fC03><fC03 i1="03" i2="X" l="SPA"><s0>Función booliana</s0><s5>03</s5></fC03><fC03 i1="04" i2="X" l="FRE"><s0>Fonction quadratique</s0><s5>04</s5></fC03><fC03 i1="04" i2="X" l="ENG"><s0>Quadratic function</s0><s5>04</s5></fC03><fC03 i1="04" i2="X" l="SPA"><s0>Función cuadrática</s0><s5>04</s5></fC03><fC03 i1="05" i2="X" l="FRE"><s0>Défaillance</s0><s5>05</s5></fC03><fC03 i1="05" i2="X" l="ENG"><s0>Failures</s0><s5>05</s5></fC03><fC03 i1="05" i2="X" l="SPA"><s0>Fallo</s0><s5>05</s5></fC03><fC03 i1="06" i2="X" l="FRE"><s0>Dépannage</s0><s5>06</s5></fC03><fC03 i1="06" i2="X" l="ENG"><s0>Repairing</s0><s5>06</s5></fC03><fC03 i1="06" i2="X" l="SPA"><s0>Reparo</s0><s5>06</s5></fC03><fC03 i1="07" i2="X" l="FRE"><s0>Réparation</s0><s5>07</s5></fC03><fC03 i1="07" i2="X" l="ENG"><s0>Repair</s0><s5>07</s5></fC03><fC03 i1="07" i2="X" l="SPA"><s0>Reparación</s0><s5>07</s5></fC03><fC03 i1="08" i2="X" l="FRE"><s0>Système réparable</s0><s5>08</s5></fC03><fC03 i1="08" i2="X" l="ENG"><s0>Repairable system</s0><s5>08</s5></fC03><fC03 i1="08" i2="X" l="SPA"><s0>Sistema reparable</s0><s5>08</s5></fC03><fC03 i1="09" i2="X" l="FRE"><s0>Système série</s0><s5>09</s5></fC03><fC03 i1="09" i2="X" l="ENG"><s0>Series system</s0><s5>09</s5></fC03><fC03 i1="09" i2="X" l="SPA"><s0>Sistema serie</s0><s5>09</s5></fC03><fC03 i1="10" i2="X" l="FRE"><s0>Temps polynomial</s0><s5>10</s5></fC03><fC03 i1="10" i2="X" l="ENG"><s0>Polynomial time</s0><s5>10</s5></fC03><fC03 i1="10" i2="X" l="SPA"><s0>Tiempo polinomial</s0><s5>10</s5></fC03><fC03 i1="11" i2="X" l="FRE"><s0>Détection panne</s0><s5>11</s5></fC03><fC03 i1="11" i2="X" l="ENG"><s0>Failure detection</s0><s5>11</s5></fC03><fC03 i1="11" i2="X" l="SPA"><s0>Detección falla</s0><s5>11</s5></fC03><fN21><s1>324</s1></fN21><fN44 i1="01"><s1>PSI</s1></fN44><fN82><s1>PSI</s1></fN82></pA></standard></inist></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/PascalFrancis/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000614 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Curation/biblio.hfd -nk 000614 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= PascalFrancis
|étape= Curation
|type= RBID
|clé= Pascal:06-0493027
|texte= Optimal testing and repairing a failed series system
}}
| This area was generated with Dilib version V0.6.33. |  |