Components Assignment Problem for Multi-Source Multi-Sink Flow Networks with Reliability and Budget Constraints

Noha Nasr Elden¹, Moatamad Hassan¹, Mohamed Abd El-Aziz²

¹Mathematics and Computer Science Department, Faculty of Science, Aswan University, Aswan, Egypt.
²Information Systems Department, Faculty of Computer and Information Sciences, Ain Shams University, Cairo, Egypt.

DOI: 10.4236/jcc.2022.106009                

Abstract

System reliability optimization problem of multi-source multi-sink flow network is defined by searching the optimal components that maximize the reliability and minimize the total assignment cost. Therefore, a genetic-based approach is proposed to solve the components assignment problem under budget constraint. The mathematical model of the optimization problem is presented and solved by the proposed genetic-based approach. The proposed approach is based on determining the optimal set of lower boundary points that maximize the system reliability such that the total assignment cost does not exceed the specified budget. Finally, to evaluate our approach, we applied it to various network examples with different numbers of available components; two-source two-sink network and three-source two-sink network.

Keywords

Multi-Source Multi-Sink Stochastic-Flow Networks, System Reliability Optimization, Components Assignment Problem

1. Introduction

The assignment problem (AP) is one of the most important concerns in manufacturing and service systems and it has gotten a lot of attention from scholars. AP is in charge of allocating various resources to various activities on a one-to- one basis [1]. The goal of the Component Assignment Problem (CAP) is to find the best way to assign n accessible components to m positions in a system in order to enhance system reliability [2]. In [3] discussed CAP in a single-source single-sink stochastic flow network (SFN), they studied the matter of searching the optimal components to be appointed to the network for maximizing reliability. The system reliability of an SFN is improved in [4] by searching for the best resource to assign using a genetic algorithm approach (GA). Existing [5] defined the topic as a double-resource assignment problem and suggested an optimization technique solution for the two resource types, transmission line and transmission facility. They devised a method that used the GA to solve the CAP with the optimal reliability while adhering to the assignment budget constraint [6]. They discovered an efficient technique based on a GA to handle the resource assignment problem by finding the optimal resource assignment, which leads to maximum system reliability, in the CAP for a Stochastic-Flow Network (SFN) presented in [3]. The Component Assignment Problem (CAP) attempts to find the best way to assign n suitable components to m places in a system in order to maximize system reliability [2]. Additionally, [7] has solved the aforementioned problem as a multi-objective CAP. They suggested a two-stage solution to the multi-objective CAP due to reliability and assignment cost for SFN.

[8] studied the CAP under lead-time constraints to maximize system reliability, and [9] solved it as a multi-objective problem. In the case of considering both lead-time and assignment cost, the CAP has been studied by [10] [11] [12] [13]. In [10], a multi-objective GA-based on RWGA approach was proposed to obtain the optimal solution, i.e., the system reliability was maximized and both the total lead-time and the assignment cost were minimized. In [11] the CAP has been formulated as a fuzzy linear optimization problem, considering node failure [12]. In [13] presented a MOPSO-based approach for determining the optimal components that can be assigned to an SFN to maximize system reliability while minimizing total cost and total lead-time.

The problem of allocating various resources at the source nodes in order to maximize the system reliability for multi-source multi-sink SFN is discussed in [14]. An algorithm was developed to solve it. Considering the transmission cost constraints, the resource allocation problem was developed and solved by [15]. Hsieh and Lin [16] proposed updating schemes to solve the resource allocation problem for an unreliable multi-source multi-sink flow network, taking into consideration changing the resource demand or the characteristic of the SFN. In [17] and [5], the multi-source multi-sink SFN flow assignment problem was discussed. Additionally, to maximize system reliability, the flow assignment problem for multi-source multi-sink SFN was studied and solved using a proposed GA [18]. While in [19], the transmission cost was considered in order to maximize the reliability of the capacity vector. A GA-based algorithm was presented by [20] to determine the best set of lower boundary points for maximizing system reliability such that transmission cost does not exceed a specified upper bound. Finally, [21] studied the components assignment problem subject to reliability of the capacity vector.

The components assignment problem in the context of system reliability is investigated in this work. I.e., I expanded on the issue raised by [22]. In addition, a genetic-based algorithm was devised to overcome the CAP limitation in multi-source multi-sink flow networks while maximizing system reliability.

The following is a summary of the paper’s structure. The mathematical formulation of the problem is presented in Section 2. The components of the suggested strategy are described in Section 3. Section 4 contains the pseudo-code for the proposed technique. In part 5, we include some examples, and in section 6, we present our conclusions. Finally, we offer notations at the appendix.

2. Problem Formulation

Assume that $\mathcal{C}=\left\{{�}_1,{�}_2,{�}_3,\cdots ,{�}_n\right\}$ is set of components assigned to the set of arcs A such that ${�}_i\ne {�}_e$ for $i\ne e$. The problem is then formulated as:

Maximize $R_s(\; C\; )$

s.t.

$Z\left(\mathcal{C}\right)\le \mathcal{B}$

where $Z\left(\mathcal{C}\right)={\displaystyle {\sum }_{i=1}^n{z}_i}$ ; $z_i$ represents the cost of the assigned components ${\mathcal{C}}_i$ and $\mathcal{B}$ represents the budget.

2.1. The Proposed Algorithm

2.1.1. Representation

The following subsections explain the steps of the proposed algorithm. The chromosome $\mathcal{C}=\left\{{�}_1,{�}_2,{�}_3,\cdots ,{�}_n\right\}$ with length n, represents the set of candidate components. The component ${�}_1$ is assigned to arc a₁, ${�}_2$ is assigned to a₂, …, and ${�}_n$ is assigned to a_n.

2.1.2. Crossover

Uniform crossover is used to generate new offspring. To avoid duplicate components we use modified crossover [17]. Figure 1 shows the crossover process.

2.1.3. Mutation

Swap mutation is used to keep the cost value of the selected components and to avoid duplicate ones. Figure 2 explains the mutation process.

2.1.4. Evaluation

We will generalize the approach proposed by [20] to find all lower vectors satisfying the following constraints:

${\displaystyle \underset{i=1}{\overset{\sigma }{\sum }}{\displaystyle \underset{k=1}{\overset{k_{i,j}}{\sum }}{f}_{i,j,k,w}}}=d_{w,j},w=1,\cdots ,m;j=1,\cdots ,\theta$ (1)

Figure 1. Modified uniform crossover.

Figure 2. Mutation operation.

${\displaystyle \underset{j=1}{\overset{\theta }{\sum }}{\displaystyle \underset{k=1}{\overset{k_{i,j}}{\sum }}{f}_{i,j,k,w}}}\le r_{w,i},w=1,\cdots ,m;i=1,\cdots ,\sigma$ (2)

$x_e={\displaystyle \underset{i=1}{\overset{\sigma }{\sum }}{\displaystyle \underset{j=1}{\overset{\theta }{\sum }}{\displaystyle \underset{k=1}{\overset{k_{i,j}}{\sum }}{\displaystyle \underset{w=1}{\overset{m}{\sum }}\left\{f_{i,j,k,w}|a_e\in M{P}_{i,j,k}\right\}}}}}\le M_e,e=1,2,3,\cdots ,n$ (3)

$f_{i,j,k,w}\le ℂ,i=1,\cdots ,\sigma ;j=1,\cdots ,\theta ;w=1,\cdots ,m;k=1,\cdots ,k_{i,j}$ (4)

where $ℂ=\text{Min}\left\{L_k|k=1,2,\cdots ,np\right\}$ and $L_k$ is the maximum capacity of $M{P}_{i,j,k}$ given by $L_k=\min \left\{M_e|a_e\in M{P}_{i,j,k}\right\}$. If $X_1,X_2,\cdots ,X_{Popsize}$ represent a generated set of capacity vectors that corresponds to the flow vectors that satisfy constraints (3) through (6). If the network is cyclic, [22], then remove the non-minimal ones in $X_1,X_2,\cdots ,X_{Popsize}$ to obtain all lower boundary points. Otherwise, the generated capacity vectors are all lower boundary points, [23]. Finally, if $X_1,X_2,\cdots ,X_q$ are all lower boundary points, then system reliability $R_s\left(\mathcal{C}\right)$ is defined as:-

$R_s\left(\mathcal{C}\right)=P_r{\displaystyle {\cup }_{i=1}^q\left\{Y|Y\ge X^i\right\}}$ (5)

Here, $P_r\left\{Y\right\}=P_r\left\{y_1\right\}\cdot P_r\left\{y_2\right\}\cdot \cdots \cdot P_r\left\{y_n\right\}$. We use the inclusion/exclusion rule, [24] to evaluate the expression given in (7).

2.1.5. Fitness Function

The fitness function is the system reliability for the assigned components $R_s\left(\mathcal{C}\right)$ if $Z\left(\mathcal{C}\right)$ less than or equals $\mathcal{B}$. Otherwise, the fitness value is set to zero.

$Fit\left(\mathcal{C}\right)=\{\begin{array}{ll}{R}_s\left(\mathcal{C}\right)\hfill & \text{if}Z\left(\mathcal{C}\right)\le \mathcal{B}\hfill \\ 0\hfill & \text{Otherwise}\hfill \end{array}$ (6)

2.1.6. Selection Process

The Roulette Wheel selection process is used here to select new parents [22]. The following steps summarize the selection process: summing all fitness values of chromosomes ( $\mathcal{S}$ ) in the current population. Generate a random number $\mathfrak{r}$ in the range $0\le r\le \mathcal{S}$. Starting from the first to the current one, calculate the sum of fitness values $�$. If $�\ge r$, then the current chromosome is selected. Otherwise, go to repeat Step i.

2.2. The Algorithm

The following steps describe the whole algorithm used to solve the CAP problem. In addition, the corresponding flowchart is shown in Figure 3.

Figure 3. Flow chart of the proposed algorithm.

Begin

Set parameters M, R, D, Pc, Pm, 𝒫, and 𝒢

Set gn = 0, gt = 0

Initialize 𝒫

While gn < 𝒢, do

While gt < 𝒫, do

Randomly select two chromosomes

Apply crossover according to Pc

Apply mutation according to Pm

Evaluate the current chromosome (Calculate Z(𝒞), R_s(𝒞), and fit(𝒞))

If (fit(𝒞) > 0), then set gt = gt + 1

End do

Set gn = gn + 1

Replace the parents

End do

Report the best solution found (The highest fit(𝒞))

End

3. Experimental Results

3.1. Two-Source Two-Sink Network

We study in first example, the computer network shown in Figure 4 which has two sources and two sinks. Table 1 lists the available components, and the minimal path MPs for this network are:- MP_1,1,1 = {a₁, a₅}, MP_1,1,2 = {a₁, a₆, a₉} , MP_1,1,3 = {a₂, a₇, a₉}, MP_1,2,1 = {a₁, a₆, a₁₄}, MP_1,2,2 = {a₂, a₇, a₁₄}, MP_2,1,1 = {a₃, a₇, a₉}, MP_2,1,2 = {a₄, a₈, a₁₃, a₉}, MP_2,2,1 = {a₃, a₇, a₁₄}, MP_2,2,2 = {a_4, a₈, a₁₃, a₁₄}, MP_2,2,3 = {a₄, a₈, a₁₀} and MP_2,2,4 = {a₄, a₁₁, a₁₂}.

Here we let R = (r_1,1, r_1,2, r_2,1, r_2,2) = (15, 17, 10, 13), D = (d_1,1, d_1,2, d_2,1, d_2,2) = (9, 10, 5, 8), and costs of the available components are (41, 52, 51, 32, 61, 52, 31, 42, 21, 62, 51, 52 ,41, 22, 31, 22, 11, 32, 51, 51).

Figure 4. Network with two sources and two sinks.

Table 1. Available components.

Table 2 lists the lower vectors for the proposed algorithm’s first generation. The best $R_s\left(\mathcal{C}\right)$ values obtained at each generation are shown in Figure 5. The best value of $R_s\left(\mathcal{C}\right)$ was 0.981306 at the first generation. Table 3 presents the results of our suggested approach for various $\mathcal{C}$ values.

3.2. Three-Source Two-Sink Network

The second example we present in this paper includes three sources and two sinks shown in Figure 6. Table 4 shows the available components with capacities, costs and probabilities. The best $R_s\left(\mathcal{C}\right)$ equals to 0.540484 and the corresponding $Z\left(\mathcal{C}\right)$ and $\mathcal{C}$ is 21 and (3, 7, 8, 12, 11, 2, 9, 1, 10, 6) respectively. The corresponding lower vectors are given in Table 5. The Minimal Paths (MPs) are:- MP_1,1,1 = {a₁, a₇}, MP_1,1,2 = {a₂,a₉}, MP_1,2,1 = {a₁, a₈}, MP_2,1,1 = {a₃, a₉}, MP_2,2,1 = {a₄, a₁₀}, MP_3,1,1 = {a₅, a₉} and MP_3,2,1 = {a₆, a₁₀}. R = (r_1,1, r_1,2, r_1,3, r_2,1, r_2,2, r_2,3, r_3,1, r_3,2, r_3,3) = (5, 2, 3, 5, 3, 2, 2, 2, 3) and D = (d_1,1, d_1,2,, d_2,1, d_2,2, d_3,1, d_3,2) = (3, 1, 2, 2, 1, 3).

4. Discussion

Through the searching process about the best components, the GA parameters were 𝒫 = 10, 𝒢 = 100, 𝒸𝓇 = 0.70 and 𝓂𝓇 = 0.02 for all studied cases. Generating all lower boundary to evaluate $R_s\left(\mathcal{C}\right)$ is based on discovering all possible flow vector solutions. It is impossible to estimate the number of viable solutions. As a result, in order to generate all possible flow vector solutions, F, that satisfies the constraints (1) to (4) given in section 2.1.4, we run the inner GA more than one time. So, the value of $R_s\left(\mathcal{C}\right)$ is corresponding to the optimal components and the optimal set of lower vectors.

To the best of our knowledge, solving the CAP considering system reliability and assignment budget is never studied or discussed before.

In addition, this study is different from [19] that solved the CAP to maximize a single capacity vector. Furthermore, authors in [20] studied the system reliability optimization subject to transmission cost. Therefore, there is no comparison available here.

Table 2. Capacity vectors generated at the first generation.

Table 3. Obtained Results for different values for ℬ.

*The value of cost that corresponding to Max Rs.

Table 4. Available components with capacities, costs and probabilities.

Table 5. Lower vectors for Figure 5 network.

Figure 5. The best $R_s\left(\mathcal{C}\right)$ values at each generation for $\mathcal{B}=170$.

Figure 6. Network with three sources and two sinks.

5. Conclusions

In this paper, the multi-source multi-sink stochastic flow networks system reliability optimization problem assignment budget is studied and formulated. A GA-based approach is presented to solve it. The presented approach based on GA is used to determine the optimal components that could be assigned to a multi-source multi-sink flow network in order to maximize system reliability while minimizing total assignment cost.

The multi-source multi-sink flow networks are used to represent many real-life systems, such as computer systems, manufacturing systems, and logistics systems, to evaluate their performance by considering one or more constraints. Therefore, this research presented GA-based approach to optimize the reliability subject to an assignment budget.

In future work, one may extend the problem by considering multiple constraints, such as, system reliability, lead-time, and budget.

Appendix

N Number of nodes.

MPs Minimal paths.

A Set of arcs.

S Set of source nodes.

T Set of sink nodes.

M $\left\{M_1,M_2,\cdots ,M_n\right\}$, where M_e maximum capacity of a_e and M_e is an integer.

$d_{w,j}$ The demand of resource w at sink node tj.

$r_{w,i}$ Maximum quantity for resource w which source node si can supply.

𝒫 Population size.

𝒢 Maximum generation.

𝒸𝓇 Crossover rate.

𝓂𝓇 Mutation rate.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Chu, P.C. and Beasley, J.E. (1997) A Genetic Algorithm for the Generalised Assignment Problem. Computers & Operations Research, 24, 17-23. https://doi.org/10.1016/S0305-0548(96)00032-9
[2]	Lin, Y.K. (2011) Network Reliability of a Time-Based Multistate Network under Spare Routing with p Minimal Paths. IEEE Transactions on Reliability, 60, 61-69. https://doi.org/10.1109/TR.2010.2103594
[3]	Lin, Y.K. and Yeh, C.T. (2010) Evaluation of Optimal Network Reliability under Components-Assignments Subject to a Transmission Budget. IEEE Transactions on reliability, 59, 539-550. https://doi.org/10.1109/TR.2010.2055920
[4]	Lin, Y.K. and Yeh, C.T. (2010) Optimal Resource Assignment to Maximize Multistate Network Reliability for a Computer Network. Computers & Operations Research, 37, 2229-2238. https://doi.org/10.1016/j.cor.2010.03.013
[5]	Lin, Y.K. and Yeh, C.T. (2011) Computer Network Reliability Optimization under Double-Resource Assignments Subject to a Transmission Budget. Information Sciences, 181, 582-599. https://doi.org/10.1016/j.ins.2010.09.036
[6]	Lin, Y.K. and Yeh, C.T. (2011) Multistate Components Assignment Problem with Optimal Network Reliability Subject to Assignment Budget. Applied Mathematics and Computation, 217, 10074-10086. https://doi.org/10.1016/j.amc.2011.05.001
[7]	Lin, Y.K. (2011) Stochastic Flow Networks via Multiple Paths under Time Threshold and Budget Constraint. Computers & Mathematics with Applications, 62, 2629-2638. https://doi.org/10.1016/j.camwa.2011.08.002
[8]	Hassan, M.R. (2015) Solving a Component Assignment Problem for a Stochastic-Flow Network under Lead-Time Constraint. Indian Journal of Science and Technology, 8, 5 p. https://doi.org/10.17485/ijst/2015/v8i35/70455
[9]	Hassan, M.R. and Abdou, H. (2018) Multi-Objective Components Assignment Problem Subject to Lead-Time Constraint. Indian Journal of Science and Technology, 11, 9 p. https://doi.org/10.17485/ijst/2018/v11i21/100080
[10]	Aissou, A., Daamouche, A. and Hassan, M.R. (2019) Optimal Components Assignment Problem for Stochastic-Flow Networks. Journal of Computer Science, 15, 108-117. https://doi.org/10.3844/jcssp.2019.108.117
[11]	Hamdy, H., Hassan, M.R., Eid, M. and Khalifa, M. (2019) Solving Optimal Components Assignment Problem for a Multistate Network Using Fuzzy Optimization. International Journal of Mobile Network Communications & Telematics (IJMNCT), 9, 1-22.
[12]	Hassan, M.R., Hamdy, H., Alkhalaf, S., Eldin, A.M.B., Ahmed, M. and Hemeida, A.M. (2021) Optimal Components Assignment Problem for a Flow Network with Node Failure Using Fuzzy Optimization. Ain Shams Engineering Journal, In Press. https://doi.org/10.1016/j.asej.2021.09.028
[13]	Aissou, A., Daamouche, A. and Hassan, M.R. (2021) Components Assignment Problem for Flow Networks Using MOPSO. IAENG International Journal of Computer Science, 48, 96-108.
[14]	Hsieh, C.C. and Lin, M.H. (2003) Reliability-Oriented Multi-Resource Allocation in a Stochastic-Flow Network. Reliability Engineering & System Safety, 81, 155-161. https://doi.org/10.1016/S0951-8320(03)00082-6
[15]	Hsieh, C.C. and Chen, Y.T. (2005) Reliable and Economic Resource Allocation in an Unreliable Flow Network. Computers & Operations Research, 32, 613-628. https://doi.org/10.1016/j.cor.2003.08.008
[16]	Hsieh, C.C. and Lin, M.H. (2006) Simple Algorithms for Updating Multi-Resource Allocations in an Unreliable Flow Network. Computers & Industrial Engineering, 50, 120-129. https://doi.org/10.1016/j.cie.2006.01.003
[17]	Liu, Q., Zhang, H., Ma, X. and Zhao, Q. (2007) Genetic Algorithm-Based Study on Flow Allocation in a Multicommodity Stochastic-Flow Network with Unreliable Nodes. Eighth ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing (SNPD 2007), Qingdao, 30 July-1 August 2007, 576-581. https://doi.org/10.1109/SNPD.2007.261
[18]	Hassan, M.R. (2016) Solving Flow Allocation Problems and Optimizing System Reliability of Multisource Multi Sink Stochastic Flow Network. International Arab Journal of Information Technology (IAJIT), 13, 477-483.
[19]	Liu, Q., Zhao, Q. and Zang, W. (2008) Study on Multi-Objective Optimization of Flow Allocation in a Multi-Commodity Stochastic-Flow Network with Unreliable Nodes. Journal of Applied Mathematics and Computing, 28, 185-198. https://doi.org/10.1007/s12190-008-0093-9
[20]	Hassan, M.R. (2021) System Reliability Optimization of Multi-Source multi-Sink Stochastic Flow Networks with Budget Constraint. International Journal of Reliability Quality and Safety Engineering, 28, Article ID: 2150025. https://doi.org/10.1142/S021853932150025X
[21]	Hassan, M.R. (2021) Maximizing Reliability of the Capacity Vector for Multi-Source Multi-Sink Stochastic-Flow Networks Subject to an Assignment Budget. Journal of Industrial & Management Optimization, 17, 1253-1267. https://doi.org/10.3934/jimo.2020020
[22]	Lin, Y.K. (2001) A Simple Algorithm for Reliability Evaluation of a Stochastic-Flow Network with Node Failure. Computers & Operations Research, 28, 1277-1285. https://doi.org/10.1016/S0305-0548(00)00039-3
[23]	Yeh, W.C. (1998) A Revised Layered-Network Algorithm to Search for All d-Min Paths of a Limited-Flow Acyclic Network. IEEE Transactions on Reliability, 47, 436-442. https://doi.org/10.1109/24.756087
[24]	Janan, X. (1985) On Multistate System Analysis. IEEE Transactions on Reliability, 34, 329-337. https://doi.org/10.1109/TR.1985.5222178