Reconfiguration of memory arrays using spare lines is known to be an NP-complete problem. In this paper, we present an algorithm that reconfigures a memory array without any faults by using spare lines effectively even if they contain faulty elements. First, the reconfiguration problem is transformed to an equivalent covering problem in which faulty elements are covered by imaginary fault-free spare lines. Next, the covering problem is heuristically solved by using the Dulmange-Mendelsohn decomposition. The experiments for recently designed memory arrays show that the proposed algorithm is fast and practical.

Investment planning for power plants involves making a long-term plan covering various facility investments, such as the construction of a new power plant or the replacement of an old plant with a new one, under uncertain environments. In this paper, we propose an optimization method for such a planning problem. Our method is based on decision tree analysis, in which uncertain environments are described as scenarios. The maintenance of existing plants is also taken into account by introducing the option of large-scale repair in addition to replacement. In order to avoid combinatorial explosion of failure event scenarios of plants, we introduce the concept of failure risk cost which contributes to simplification of the decision tree and reduction of the calculation time.