Journal Search Engine
Search Advanced Search Adode Reader(link)
Download PDF Export Citaion korean bibliography PMC previewer
ISSN : 1598-7248 (Print)
ISSN : 2234-6473 (Online)
Industrial Engineering & Management Systems Vol.20 No.1 pp.61-68
DOI : https://doi.org/10.7232/iems.2021.20.1.61

An Optimal Algorithm for the Reliability Optimization Problem of a Series System with Selectable Alternatives

Soochan Kim, Namsu Ahn*
Department of Mechanical and Systems Engineering, KMA, Seoul 01805, Republic of Korea
*Corresponding Author, E-mail: namsu.ahn@gmail.com
August 2, 2020 January 8, 2021 February 17, 2021

ABSTRACT


Reliability is defined as the ability of a system to provide the required functionality for a specified period in a given environment. Since designing a system structure to achieve target reliability arises in many industrial areas, there are various reliability optimization applications. In this research, we discuss one of the reliability optimization problems, that is, placement of components is a series structure, there are alternatives for the component that can be selected, achieving target reliability is a requirement, and an objective is a cost minimization. An optimal algorithm is designed to obtain the optimal solution to the problem, and a simple greedy heuristic is developed to accelerate the convergence speed of the optimal algorithm. Four data sets from the previous research were used to show the performance of the algorithm and our optimal algorithm could obtain the solution in a second. Considering the algorithm performance, our algorithm can be used to address the real-size instances in many industries. Also, we can observe that the convergence speed to an optimal solution depends on the generated bound from the feasible solution of the heuristic.



초록


    1. INTRODUCTION

    Reliability refers to the ability of a system to provide the required functionality for a specified period in a given environment. For example, designing a weapon system should provide high reliability, and it is critical to achieve target reliability by considering available resources such as volume, budget, weight. Problem of designing a system structure to achieve the desired reliability is called a reliability optimization problem (ROP). Since ROP arises in many practical applications, numerous extended and modified versions of the problems are studied (several review papers can be found in (Kuo and Wan, 2007;Soltani, 2014;Twum and Aspinwall, 2013). Also, recent similar studies can be found in (Peiravi et al., 2019;Ardakan et al., 2015;Feizabadi and Jahromi, 2017;Gholinezhad and Hamadani, 2017;Jahromi and Feizabadi, 2017;Ardakan and Hamadani, 2014;Shekhar et al., 2017;Zoulfaghari et al., 2015). Although not directly related to this study, some recent studies with similar purposes are found in (Aslam et al., 2015, 2018;Sindhu et al., 2019).

    In this paper, we deal with one of ROP, more specifically, where the (1) placement of components is a series structure, (2) there are alternatives for a component that can be selected, (3) achieving a target reliability is a requirement, and (4) objective is a cost minimization (throughout this paper, this problem will be referred to as a reliability optimization problem-cost minimization (ROP-Cmin)).

    When each component of the system is connected in series, the reliability of the system can be calculated as i = 1 n r i (system is composed of n number of components and reliability of component i is ri), which is the most common type of system structure that can be observed in a real world. We also assume that, if we can pay a higher cost for a certain component, a replaceable component with higher reliability can be purchased (that is, if ci > cj, then ri > rj). In summary, selectable alternatives exist in ROP-Cmin.

    Many of the existing studies have been performed on, where the constraint is a cost restriction and the objective is reliability maximization (throughout this paper, this problem will be referred to as a reliability optimization problem-reliability maximization (ROP-Rmax)). To avoid confusion of understanding, comparison between the ROP-Cmin and ROP-Rmax in terms of objective and constraints is summarized in Table 1.

    Previous studies on ROP-Rmax can be classified as developing an optimization algorithm (which guarantees to find an optimal solution) and a heuristic algorithm (which can probably find a good solution). Since ROP-Rmax can be converted to a well-known multiple-choice knapsack problem (MCKP) (Sung and Cho, 2000), many optimization approaches can be found in (Ahmadizar and Soltanpanah, 2011;Dyer et al., 1995;Nauss, 1978;Sinha and Zoltners, 1979). Also, studies that provide heuristic algorithms can be found in (Kim et al., 2004, 2008; Coit and Smith, 1996;Nahas and Nourelfath, 2005;Truong et al., 2013).

    The most similar study to this paper was conducted in (Elegbede et al., 2003). The similarities are, an objec-tive is a cost minimization of the system, the restriction is satisfying the target reliability, and optimal methods are discussed. However, subject systems are different from parallel-series system to a series system with selectable alternatives and objectives are dissimilar from allocation of reliability and redundancy to select alternatives for components.

    In (Moon et al., 2014) and (Na, 2017), the authors claimed that many defense R&D projects turn out to be exceeding the planned budget significantly. Therefore, minimizing the cost satisfying the target reliability is an urgent issue in the Republic of Korea. The author in (Na, 2017) claimed that ROP-Cmin is solved with Genetic Al-gorithm and Simulated Annealing in total life cycle management of weapon systems, and the solution is used in validation of military R&D target RAM (reliability, availability, maintainability) values.

    However, to the best of authors’ knowledge, no op-timal algorithm for ROP-Cmin can be found, and this research devotes to developing an optimal algorithm for ROP-Cmin.

    This paper is composed as follows. In section 2, we present a binary integer programming model for the ROP-Cmin. In section 3, we present optimization and heuristic algorithm for the ROP-Cmin. The optimal algorithm solves the modified ROP-Rmax several times until the optimal solution is obtained. The heuristic provides a bound for the optimal algorithm. In section 4, we implemented the algorithms and showed the performances in terms of the consumed CPU time to obtain the optimal solution. Some observations will also be discussed. Finally, section 5 summarizes the main contribution of this paper and presents some future research directions.

    2. MATHEMATICAL FORMULATION

    In this section, we devise the ROP-Cmin in mathe-matical symbols and expressions. ROP-Cmin considered in this research assumes that n components are connected in series, as shown in Figure 1. The objective is minimizing the cost while satisfying the minimum requirement of system reliability.

    To express the problem in a mathematical model, we define some symbols and decision variables as the following (in this research, we assume that if ci > cj, then ri > rj).

    x i j = { 1 ,  if alternative  j  is used for component  i , 0 ,  otherwise.

    Now a mathematical formulation can be given below.

    M i n C S = i = 1 n j = 1 m i c i j x i j
    (1)

    i = 1 n j = 1 m i r i j x i j R .
    (2)

    j = 1 m i x i j = 1 , i = 1 , ... , n .
    (3)

    x i j = { 0 , 1 } , i = 1 , ... , n , j = 1 , ... , m i .
    (4)

    The objective function (1) means we want to mini-mize the sum of the costs of the selected alternatives, nonlinear constraints (2) indicate that the required mini-mum system reliability (R) needs to be satisfied by the selected components in series, constraints (3) explain that exactly one alternative is required to be selected for a component i among mi alternatives, and lastly, constraints (4) denote the requirement of binary decision variables.

    Since the constraint (2) is modeled as a nonlinear expression, it is known to be difficult to solve optimally. Therefore, new optimal method is required to be designed to address the problem.

    3. OPTIMAL AND HEURISTIC ALGORITHMS

    In this section, we propose an optimal and heuristic algorithm for ROP-Cmin, and the optimal algorithm uses the generated bound from heuristic.

    3.1 Optimal Algorithm

    Before we explain the optimal algorithm more in detail, we introduce a mathematical formulation for the ROP-Rmax where n components are connected in series and the objective is maximizing the system reliability under cost restriction. We define some additional symbols as the following.

    • Rs: Reliability of the system when the selected alternatives are connected in series

    • C: Maximum allowable cost for a system

    Now the mathematical formulation for ROP-Rmax can be given below.

    M a x R S = i = 1 n j = 1 m i r i j x i j
    (5)

    i = 1 n j = 1 m i c i j x i j C .
    (6)

    j = 1 m i x i j = 1 , i = 1 , ... , n .
    (7)

    x i j = { 0 , 1 } , i = 1 , ... , n , j = 1 , ... , m i .
    (8)

    The objective function (5) means maximizing the system reliability of the selected alternatives, constraints (6) indicate the cost restriction, and constraints (7) explain exactly one alternative can be selected for each component. Last constraints (8) mean every xij variables take a value of zero or one.

    Let the formulations of ROP-Cmin and ROP-Rmax as Min.CS and Max.RS, respectively. Many studies have been performed to solve Max.RS optimally or approximately. Authors in (Sung and Cho, 2000) claimed to use transforming the nonlinear objective function into a linear one by taking the logarithm as follows.

    ln i = 1 n j = 1 m i r i j x i j = i = 1 n j = 1 m i ln r i j x i j

    Then, the transformed problem with the remaining constraints of Max.RS equals a well-known multiple-choice knapsack problem (MCKP). MCKP is defined as a binary knapsack problem with an addition of disjoint multiple-choice constraints (Sinha and Zoltners, 1979). Although MCKP is known to be NP-complete (Ibaraki and et al., 1978), its linear relaxation by dropping the binary restriction can be solved very efficiently. Many O(n) algorithms ((Dyer et al., 1995;Pisinger, 1995;Zemel, 1984) for linear MCKP have been developed, and as stated in (Martello and Toth, 1990), the MCKP can be solved in O ( i n i b ¯ ) , where i n i and b ¯ are the total number of alternatives and q b q , respectively.

    Research in (Kim et al., 2008) suggested to use of simulated annealing and tabu-search meta-heuristic algorithms for ROP-Rmax, and compared the performance of the algorithms with an optimal solution from the optimization software (ILOG CPLEX 9.1). As they indicated, optimization software obtain the optimal solution within a second, and acquired optimal solution much faster than the heuristic does in some cases. Since the heuristic can-not guarantee obtaining an optimal solution, if we can find an optimal solution within a reasonable amount of time, then it is better.

    In this paper, we used the good property of ROP-Rmax to solve the ROP-Cmin (note again that, the main purpose of this research is solving the ROP-Cmin exactly). Since the ROP-Cmin is a nonlinear programming formulation, we designed an optimal method with ROP-Rmax instead of address ROP-Cmin directly. We first solve ROP-Rmax with a huge positive value of C and check whether obtained RS is greater than or equal to R. If RS is greater than or equal to R, then we decrease C to a certain amount and solve ROP-Rmax again. This procedure will be stopped when RS is smaller than R. Detailed procedure can be summarized in pseudo-code as follows.

    • Input: Prepare parameters C and △ and assign huge and small positive values, respectively.

    • Step 1. Solve ROP-Rmax with parameter C optimally.

    • Step 2. Calculate system reliability with the obtained solution.

      • Step 2-1. If the value is smaller than the system reliability requirement, then stop the procedure.

        The reliability cannot be achieved.

      • Step 2-2. If the value is greater than or equal to the system reliability requirement, store the solution and decrease C by △.

    • Step 3. Solve ROP-Rmax optimally.

    • Step 4. Calculate system reliability with the obtained solution.

      • Step 4-1. If the value is smaller than the system reliability requirement, then stop the procedure. The last feasible solution is an optimal solution.

      • Step 4-2. If the value is greater than or equal to the system reliability requirement, store the solution and decrease C by △. Return to Step 3.

    • Output: Decision either the minimum requirement of system reliability cannot be achieved or optimal solution, which guaranties the minimum sum of cost

    The optimal algorithm described above can be justified according to the following proposition.

    Proposition. If an optimal solution exists in ROP-Cmin, the discussed algorithm for ROP-Cmin finds an opti-mal solution.

    Proof. After we solve ROP-Rmax optimally, there can be two cases. The first case is calculated RS from the solution is greater than R, and the second case is RS is smaller than or equal to R. In the first case, since an optimal solution x* from ROP-Rmax forms a feasible solution to ROP-Cmin, we can obtain a better solution in terms of cost by reducing the value of R in ROP-Rmax. Since the lower value of C guarantees equal or lower value of R (this is true because if ci>cj, then ri>rj.), we can decrease C to a certain amount.

    Also, in the second case, x* from ROP-Rmax cannot be a feasible solution to ROP-Cmin, and no other solution can form a feasible solution to ROP-Cmin for a given C (since obtained RS is obtainable maximum reliability for a given C.).

    Since our algorithm designed for ROP-Cmin starts from a large enough value of C, it finds an optimal solu-tion x*, which generates minimum system cost as long as the problem has a feasible solution.

    3.2 Heuristic Algorithm

    As discussed in the previous subsection, since the number of iterations (number of ROP-Rmax solved) for ROP-Cmin depends on the initial value of C and △, obtaining exact values of C and △ affects the convergence speed of the optimal algorithm. To obtain an initial value of C, we used a simple greedy approach as follows. Note that, since the main purpose of this research is to develop an exact algorithm for ROP-Cmin, no extra effort for heuristic was given in this paper. We first select the most expensive alternative for each component and check whether the product of each reliability ( i = 1 n r i ) is greater than or equal to R. If not so, the required system reliability cannot be achieved. Otherwise, we replace the selected alternative with the next most expensive alternative and calculate the system cost again. This process will be continued until the obtained reliability is greater than or equal to the required R.

    • Input: Sorted all alternatives of components by cost

    • Step 1. Choose the most expensive alternatives for each component.

    • Step 2. Calculate system reliability with the selected components.

      • Step 2-1. If the value is smaller than the system reliability requirement, then stop the procedure.

        The reliability cannot be achieved.

      • Step 2-2. If the value is greater than or equal to the system reliability requirement, store the solution.

    • Step 3. Choose the most expensive alternative among unselected alternatives and calcu-late system reliability with the selected components.

      • Step 3-1. If the reliability is smaller than the re-quirement of the system reliability, then stop the procedure. Output the sum of cost.

      • Step 3-2. If the reliability is greater than or equal to the requirement of system reliability, then go to Step 3.

    • Output: Decision either the minimum requirement of system reliability cannot be achieved or upper bound for the system cost

    Also, for convenience, an initial value of △ was set as the minimum increment unit of cij. If we can find the proper value of △, it will decrease the run time of the algorithm. However, since our algorithm found an optimal solution in a reasonable amount of time for all cases, no extra effort was given in finding tighter values of △ and C.

    4. COMPUTATIONAL RESULTS

    In this section, the performance of the optimal algorithm for ROP-Cmin was reported. The algorithm was implemented in optimization software Xpress Ver. 7.9 (FICO, 2019). Note that, although we tried solving the mathematical formulation of ROP-Cmin using non-linear optimization software such as Lingo (Lindo, 2019) or Excel, we failed to obtain any feasible solution. All experiments were run on an Intel Pentium Dual Core (2.20GHz) with 2 GB RAM, and the running time of the algorithm was given in seconds. All experimental data sets were taken and modified from previous research (Nahas and Nourelfath, 2005). A summary of the four data sets was given in Table 3 (For the illustrative purposes, only data set 4 is given in Table 4 and the other three data sets can be found in (Nahas and Nourelfath, 2005) ).

    In this experiment, there exists one parameter represents the minimum requirement of system reliability. If the value of R is too low or too high, the computational result of ROP-Cmin can be estimated trivially. Therefore, the value of R is changed from 0.5 to 0.9 with an increment of 0.1.

    Here, several symbols are used to represent the computational results. Opt. represents the optimal value (=minimum cost) acquired from the optimal algorithm, Heu. means the cost which is obtained from the greedy heuristic, and lastly, Inf. means no feasible solution can be found under the given value of R. Since heuristic is used to accelerate the convergence speed of an optimal algorithm, Time includes running CPU time of heuristic.

    Computational results are given in Tables 5, 6, and 7 and the optimal solutions are obtained within a insignificant amount of time. Also, we calculated the correlation between the (Heu. - Opt.) and Time, and it was 0.97. Therefore, we can infer that if we want to reduce the running time of the optimal algorithm, obtaining the tighter (=smaller) value of Heu. can be helpful.

    5. CONCLUSIONS AND FUTURE WORKS

    In this research, we considered ROP-Cmin (reliability optimization problem-cost minimization) when n components (alternatives exist for each component) are connected in series and the objective is minimizing the cost while satisfying the requirement of system reliability. Since the problem is modeled as a nonlinear expression, we proposed an optimal algorithm and its main idea is solving the multiple-choice knapsack problem continuously until the optimal solution is obtained. Since the multiple-choice knapsack problem can be solved easily, computational results show that our optimal algorithm finds an optimal solution in a insignificant amount of time.

    Also, we designed a simple greedy heuristic to acceler-ate the convergence speed of an optimal algorithm, and the heuristic provides the bound for the system cost. As discussed, convergence speed to an optimal solution to the problem depends on the gap between the bound from the heuristic and the objective function value from the optimal algorithm. Therefore, developing a better heuristic that can obtain a tight bound can be a good future research topic. Furthermore, the expansion of this research to develop optimal algorithms for other ROPs is required as a follow-up research.

    Soochan Kim is a assistant professor in the department of mechanical & systems engineering at Korea Military Academy. His research interests are operations research and big data analysis.

    Namsu Ahn is a associate professor in the department of mechanical & systems engineering at Korea Military Academy. His research interests are mathematical programming and quality management.

    ACKNOWLEDGMENTS

    Korea Military Academy (Hwarangdae Research Institute) supported this research.

    Figure

    IEMS-21-1-61_F1.gif

    A system, which is composed of n components with selectable alternatives.

    Table

    Comparison between ROP-Cmin and ROP-Rmax

    Symbols and definition

    Summary of four data sets

    Data set 4 (r and c mean reliability and cost of each alternative, respectively)

    Computational results when R is 0.5 and 0.6.

    Computational results when R is 0.7 and 0.8.

    Computational results when R is 0.9.

    REFERENCES

    1. Ahmadizar, F. and Soltanpanah, H. (2011), Reliability optimization of a series system with multiple-choice and budget constraints using an efficient ant colony approach, Expert Systems with Applications, 38(4), 3640-3646.
    2. Ardakan, M. A. and Hamadani, A. Z. (2014), Reliability optimization of series-parallel systems with mixed redundancy strategy in subsystems, Reliability Engineering and System Safety, 130, 132-139.
    3. Ardakan, M. A., Hamadani, A. Z., and Alinaghian, M. (2015), Optimizing bi-objective redundancy allocation problem with a mixed redundancy strategy, ISA Transactions, 55, 116-128.
    4. Aslam, M., Jun, C. H., and Arshad, A. (2015), SkSP-V sampling plan for accelerated life tests, Proceedings of the Institution of Mechanical Engineers, Part O: Journal of Risk and Reliability, 229(3), 193-199.
    5. Aslam, M., Khan, N., and Albassam, M. (2018), Control chart for failure-censored reliability tests under uncertainty environment, Symmetry, 10(12), 690.
    6. Coit, D. W. and Smith, A. E. (1996), Reliability optimization of series-parallel systems using a genetic algorithm, IEEE Transactions on Reliability, 45(2), 254-260.
    7. FICO (2020), Xpress Mosel 4.8.4.
    8. Dyer, M. E., Riha, W. O., and Walker, J. (1995), A hybrid dynamic programming/branch-and-bound algorithm for the multiple-choice knapsack problem, Journal of Computational and Applied Mathematics, 58(1), 43-54.
    9. Elegbede, A. O. C., Chu, C., Adjallah, K. H., and Yalaoui, F. (2003), Reliability allocation through cost minimization, IEEE Transactions on reliability, 52(1), 106-111.
    10. Feizabadi, M. and Jahromi, A. E. (2017), A new model for reliability optimization of series-parallel systems with non-homogeneous components, Reliability Engineering & System Safety, 157, 101-112.
    11. Gholinezhad, H. and Hamadani, A. Z. (2017), A new model for the redundancy allocation problem with component mixing and mixed redundancy strategy, Reliability Engineering and System Safety, 164, 66-73.
    12. Ibaraki, T., Hasegawa, T., Teranaka, K., and Iwase, J. (1978), The multiple choice knapsack problem, Journal of the Operations Research Society of Japan, 21(1), 59-93.
    13. Jahromi, E. and Feizabadi, M. (2017), Optimization of multi-objective redundancy allocation problem with non-homogeneous components, Computer & Industrial Engineering, 108, 111-123.
    14. Kim, H. G., Bae, C. O., and Paik, C. H. (2004), A simulated annealing algorithm for the optimal reliability design problem of a series system with multiple component choices, IE Interfaces, 17, 69-78.
    15. Kim, H. G., Bae, C. O., Kim, J. H., and Son, J. Y. (2008), Solution methods for reliability optimization of a series system with component choices, Journal of Korean Institute of Industrial Engineers, 34(1), 49-56.
    16. Kuo, W. and Wan, R. (2007), Recent advances in optimal reliability allocation, IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 37(2), 143-156.
    17. Martello, S. and Toth, P. (1990), Knapsack Problems: Algorithms and Computer Implementations, Wiley and Sons.
    18. Moon, M. N., Ko, S. Y., Na, H. Y., and Yoo, K. T. (2014), Reliability allocation model of weapon system through total life cycle test, Korean Journal of Military Art and Science, 66(1), 23-46.
    19. Na, I. Y. (2017), Research on achieving target RAM value efficiently using RAP, Proceeding of Korea Military Operations Research Annual Conference, 154-169, 2017.
    20. Nahas, N. and Nourelfath, M. (2005), Ant system for reliability optimization of a series system with multiple-choice and budget constraints, Reliability Engineering and System Safety, 87(1), 1-12.
    21. Nauss, R. M. (1978), The 0-1 knapsack problem with multiple choice constraints, European Journal of Operational Research, 2(2), 125-131.
    22. Peiravi, A., Karbasian, M., Ardakan, M. A., and Coitc, D. W. (2019), Reliability optimization of series-parallel systems with K-mixed redundancy strategy, Reliability Engineering and System Safety, 183, 17-28.
    23. Pisinger, D. (1995), A minimal algorithm for the multiple-choice knapsack problem, European Journal of Operational Research, 83(2), 394-410.
    24. Shekhar, C., Jain, M., Raina, A., and Mishra, R. (2017), Sensitivity analysis of repairable redundant system with switching failure and geometric reneging, Decision Science Letters, 6(4), 337-350.
    25. Sindhu, T. N., Hussain, Z., and Aslam, M. (2019), Parameter and reliability estimation of inverted Maxwell mixture model, Journal of Statistics and Management Systems, 22(3), 459-493.
    26. Sinha, P. and Zoltners, A. A. (1979), The multiple-choice knapsack problem, Operational Research, 27(3), 503-515.
    27. Soltani, R. (2014), Reliability optimization of binary state non-repairable systems: A state of the art survey, International Journal of Industrial Engineering Computations, 5(3), 339-364.
    28. Sung, C. S. and Cho, Y. K. (2000), Reliability optimization of a series system with multiple-choice and budget constraints, European Journal of Operational Research, 127(1), 159-171.
    29. Truong, T. K., Li, K., Xu, Y., Ouyang, A., and Tang, X. (2013), An artificial chemical reaction optimization algorithm for multiple-choice knapsack problem, Proceedings of the International Conference on Artificial Intelligence.
    30. Twum, S. and Aspinwall, E. (2013), Models in design for reliability optimization, American Journal of Scientific and Industrial Research, 4(1), 95-110.
    31. Zemel, E. (1984), An O(n) algorithm for the linear multiple choice knapsack problem and related problems, Information Processing Letters, 18(3), 123-128.
    32. Zoulfaghari, H., Hamadani, A., and Ardakan, M. (2015), Multi-objective availability-redundancy allocation problem for a system with repairable and non-repairable components, Decision Science Letters, 4(3), 289-302.
    Do not open for a day Close