One-batch preempt deterioration-effect multi-state multi-rework network reliability problem and algorithms

Zhifeng Hao, Wei-Chang Yeh, Shi-Yi TanReliab. Eng. Syst. Saf 2021 · OpenReview

TL;DR

This paper introduces a more realistic model for "rework networks" found in manufacturing, incorporating factors like batch processing, preemptive resource use, and product deterioration. They propose a novel algorithm using two new Binary Addition Tree (BAT) variants to efficiently calculate the reliability of these complex systems, offering a significant improvement over existing methods.

What Problem Does This Paper Address?

Real-world industrial manufacturing systems often involve rework processes to fix defective products and improve overall utility and productivity. However, existing models for analyzing the reliability of these "rework networks" are often too simplistic, imposing impractical limitations. This paper addresses this gap by proposing a more comprehensive model that accounts for:

  • Multi-state components: Nodes (machines, stations, etc.) can operate in multiple states, not just functional or failed.
  • Multi-rework processes: Products might undergo multiple rework cycles.
  • One-batch policy: Perfect and reworked items are processed together in batches.
  • Preempt strategy: Resources are consumed by items as they arrive, regardless of their rework status.
  • Deterioration effect: The quality or number of products can decrease as they move through the system.

The challenge is to develop an efficient algorithm that can accurately calculate the reliability of such complex networks, which is crucial for optimizing production and resource allocation.

Methods

The core of this paper's contribution lies in its novel algorithmic approach based on Binary Addition Tree (BAT) algorithms.

  • Problem Decomposition: The complex rework network is first broken down into smaller, manageable subproblems based on "production lines" (paths from input to output) and "split nodes" (points where rework processes begin).
  • Top-Down Deterioration-Effect Multi-State BAT: A new BAT variant is introduced to generate feasible multi-state vectors for each subproblem, specifically incorporating the deterioration effect. This algorithm generates vectors in a top-down manner, ensuring that the number of items decreases or stays the same as they progress.
  • Nested Multi-State BAT: Another novel BAT is proposed to combine the feasible vectors obtained from the subproblems. This algorithm, along with node and split constraints, ensures that the combined solutions are feasible for the overall rework network.
  • Reliability Calculation: The probability of each feasible solution is calculated and then summed to determine the overall network reliability.

This approach aims to be more efficient than traditional methods by systematically generating only feasible solutions and avoiding the need to filter a vast number of infeasible ones.

Datasets

The paper uses several benchmark rework networks from existing literature ([23, 27, 28]) for validation. These networks are adapted and presented as Figures 3, 4, and 5. The state distribution (D) for these networks is also defined.

Key Insights and Ideas

  • Realism in Rework Modeling: The paper highlights the importance of incorporating multiple practical aspects (batching, preemption, deterioration, multiple reworks) for a more accurate representation of industrial rework processes.
  • BAT as a Foundation: The Binary Addition Tree algorithm proves to be a flexible and powerful tool for generating state vectors, which can be extended to handle multi-state and deterioration effects.
  • Efficiency through Decomposition: Breaking down the complex problem into subproblems and then intelligently combining solutions is key to managing computational complexity.
  • Deterioration as a Constraint: The deterioration effect isn't just a phenomenon to be observed; it's actively modeled and used to constrain the generation of feasible state vectors, leading to more accurate reliability calculations.

Key Results

The proposed algorithm was tested on several rework network examples. The key findings include:

  • Efficiency: The proposed algorithm, particularly the top-down deterioration-effect multi-state BAT, significantly reduces the number of feasible vectors compared to traditional multi-state BATs, saving computational time.
  • Scalability: The algorithm demonstrates efficiency even for larger rework networks, with average runtimes less than 4 seconds for the tested scenarios.
  • Accuracy: The algorithm successfully calculates the reliability of complex rework networks, as validated against benchmark problems. For the example in Figure 1, the calculated reliability is 0.00928509734192486950.
  • Impact of Network Size: As expected for NP-hard problems, the runtime and number of solutions increase exponentially with network size and the number of rework processes.

Limitations and Future Work

  • NP-Hardness: The authors acknowledge that rework network reliability is an NP-hard problem, meaning computational difficulty increases exponentially with network size.
  • Future Work: The paper suggests extending the algorithm to handle other real-world complexities such as fuzzy logic for uncertainty and multi-objective functions beyond just reliability. The current framework is presented as a foundation for these future extensions.

Summary updated

Abstract

– A rework network is a distinct multi-state network that exists in many real-life industrial manufacturing systems for fixing defective products using rework processes to improve the utility and productivity of the systems. To provide a more general model of rework networks, a novel one-batch preempt multi-state multi-rework network is proposed to achieve real-life applications without numerous impractical and unreasonable limitations. Accordingly, a new algorithm based on two different multi-state types of binary addition tree algorithms (BATs) is proposed to calculate the reliability of the proposed rework. Furthermore, the proposed BAT-based algorithm is applied to four rework problems to validate its effectiveness and performance for the rework reliability problem.•An novel one-batch preempt multi-state multi-rework network model•Based on the novel binary addition tree algorithms (BATs)•the novel top-down deterioration-effect multi-state BAT•the novel nested multi-state BAT s•Helps decision makers make better decisions regarding the rework process
BibTeX
@inproceedings{hao2021one,
  author = {Zhifeng Hao and Wei-Chang Yeh and Shi-Yi Tan},
  title = {{One-batch preempt deterioration-effect multi-state multi-rework network reliability problem and algorithms}},
  booktitle = {Reliab. Eng. Syst. Saf},
  year = {2021},
  url = {https://openreview.net/forum?id=QwfSFjRkOQ},
}
Figure