یک الگوریتم دقیق برای به حداقل رساندن هزینه در سیستم های قابل اطمینان مجموعه با انتخاب اجزای متعدد

In this paper, we present an exact method for cost minimization problems in series reliability systems with multiple component choices. The problem can be modelled as a nonlinear integer programming problem with a nonseparable constraint function. The method is of a combined Lagrangian relaxation and linearization method. A Lagrangian bound is obtained by solving the dual of a separable subproblem. An alternative lower bound is derived by 0–1 linearization method. A special cut-and-partition scheme is proposed to reduce the duality gap, thus ensuring the convergence of the method. Computational results are reported to show the efficiency of the method.

Reliability optimization problems are often encountered in many industrial and engineering applications. One of the popular techniques in improving the reliability of a series system is to use parallel redundancy. Fig. 1 illustrates the structure of the series–parallel network. The components in Fig. 1 may represent electronic parts in a section of circuits, coolers and filters in a lubrication system, valves in a pipeline (see, e.g., [1], [21] and [24]) or subsystems of a complicated communication networks. In this paper, we consider the cost minimization problem in series system with multiple component choices. The problem is to minimize the cost of a series system under a minimum overall reliability requirement. Exact solution methods in reliability optimization are mainly for simple series–parallel system. For example, branch-and-bound methods and its combinations with dynamic programming methods, various partial enumeration techniques (see [11], [14] and [17]) and cutting plane method [12]. Few implementable methods have been developed in the literature for reliability optimization problem with a nonseparable reliability function. Misra and Sharma [13] proposed a search algorithm to scan the entire feasible region of the optimal redundancy problem (see also [16]). Ng and Sancho [14] proposed a dynamic programming method combined with depth-first search technique. Chern and Jan [3] presented a two-phase method for solving the reliability problem. Sung and Cho [22] and [23] transformed the reliability problem into an equivalent binary integer problem and proposed a solution space reduction procedure to improve the algorithm. There are also heuristic methods that search for a near-optimal solution of reliability optimization problems. For example, genetic algorithms [4] and [6] and greedy methods [9] . In this paper, we propose a new exact method for solving problem (P). This method is based on the Lagrangian dual search and linearization method. To overcome the nonseparability of the constraint, we first approximate R(x) by a linear function. Lagrangian bounds of the approximation problem can be obtained by using dual search methods. An alternative linear approximation of R(x) is also derived and the resulting separable integer program is solved by 0–1 linearization method. To reduce the duality gap, we proposed a special cut-and-partition scheme to cut certain nonpromising integer subboxes and partition the integer domain into a union of integer subboxes. This facilitates the efficient computation of Lagrangian bound on each integer subbox. Our computational results show that the proposed method is capable of solving (P) with reasonable sizes.

We have presented in this paper an exact method for solving nonlinear integer programming arising from series–parallel reliability systems. The method is based on the Lagrangian dual search and the separable approximation to the original problem. The cut-and-partition scheme proposed in this paper cuts certain integer subboxes from further consideration and partitions the complement set into a union of integer subboxes. Computational results have been reported to show the efficiency of the algorithm.