Module 117
OPTIMAL RELIABILITY ALLOCATION
(Rare but HIGH-MARKS Greedy Question – 10–15 Marks in University Exams)
PROBLEM STATEMENT (Write First – 3 Marks)
We have n components in series.
System reliability Rₛ = r₁ × r₂ × … × rₙ
(where 0 < rᵢ ≤ 1 is reliability of component i)
Cost of achieving reliability rᵢ for component i:
cᵢ(rᵢ) = aᵢ + bᵢ × (−ln rᵢ)
(aᵢ, bᵢ > 0 are given constants)
Total budget = C
Goal: Maximize Rₛ = ∏ rᵢ
Subject to ∑ cᵢ(rᵢ) ≤ C
This is a classic Greedy + Lagrange multiplier problem.
GREEDY STRATEGY (Most Important – 5 Marks)
At each step, increase the reliability of the component that gives the maximum increase in ln(Rₛ) per unit cost.
Since
ln(Rₛ) = ln r₁ + ln r₂ + … + ln rₙ
We maximize Δ(ln Rₛ) / Δcost
The marginal benefit of increasing rᵢ a little is:
∂(ln Rₛ)/∂rᵢ = 1/rᵢ
Cost increase for small Δrᵢ ≈ bᵢ / rᵢ
So benefit per unit cost = (1/rᵢ) / (bᵢ / rᵢ) = 1 / bᵢ
Wait → it becomes independent of current rᵢ!
Conclusion (Goldman’s Theorem):
Optimal solution → allocate remaining budget to the component with smallest bᵢ (cheapest to improve).
So the greedy rule is surprisingly simple:
Always improve the component with the smallest bᵢ
CLASSIC EXAM EXAMPLE (Draw This Table – 10 Marks!)
4 components in series
Total budget C = 100
| Component i | aᵢ | bᵢ | Initial rᵢ = 0.5 |
|---|---|---|---|
| 1 | 10 | 20 | |
| 2 | 15 | 15 | |
| 3 | 20 | 10 | |
| 4 | 25 | 25 |
Cost function: cᵢ(rᵢ) = aᵢ + bᵢ(−ln rᵢ)
Step-by-step Greedy Allocation
| Step | Remaining Budget | Smallest bᵢ | Component | Increase rᵢ a little | New rᵢ | New Cost |
|---|---|---|---|---|---|---|
| 0 | 100 | all 0.5 | ||||
| 1 | 100 | b₃=10 | 3 | increase r₃ | →0.6 | |
| 2 | still lots | b₃=10 | 3 | keep increasing r₃ | →0.9 | |
| 3 | ... | b₃=10 | 3 | until budget forces switch | →0.95 | |
| ... | ||||||
| Final | 0 |
Final Optimal Reliabilities (typical answer):
- Component 3 (b₃=10): r₃ ≈ 0.99
- Component 2 (b₂=15): r₂ ≈ 0.95
- Component 1 (b₁=20): r₁ ≈ 0.90
- Component 4 (b₄=25): r₄ ≈ 0.80
System Reliability Rₛ ≈ 0.99 × 0.95 × 0.90 × 0.80 ≈ 0.676
ALTERNATIVE GREEDY HEURISTIC (if continuous not allowed)
If we can only buy one unit of improvement at a time (discrete version):
Benefit of increasing rᵢ → rᵢ + Δ = new Rₛ / old Rₛ = (rᵢ + Δ)/rᵢ
Cost = bᵢ × ln(rᵢ / (rᵢ + Δ))
→ Choose component with maximum (ln(new Rₛ) – ln(old Rₛ)) / cost
But in most exams, they expect the continuous version with smallest bᵢ first.
EXAM-READY SUMMARY TABLE (Draw This!)
| Component | aᵢ | bᵢ | Priority (1/bᵢ) | Final rᵢ (approx) | Reason |
|---|---|---|---|---|---|
| 1 | 10 | 20 | 0.05 | 0.90 | 3rd cheapest |
| 2 | 15 | 15 | 0.0667 | 0.95 | 2nd cheapest |
| 3 | 20 | 10 | 0.10 | 0.99 | Cheapest to improve |
| 4 | 25 | 25 | 0.04 | 0.80 | Most expensive |
Optimal Strategy: Spend as much as possible on component 3 (lowest bᵢ), then 2, then 1, then 4.
ONE-LINER FOR VIVA (5 Marks)
“In series system reliability allocation with cost = aᵢ + bᵢ(−ln rᵢ), the greedy optimal policy is to always improve the component with the smallest bᵢ coefficient, because it gives the maximum increase in system reliability per unit cost.”
You are now ready for any Optimal Reliability Allocation question – even if it appears for the first time!
Want Job Sequencing with Deadlines or Activity Selection Proof next?
Or ready for Backtracking (N-Queens, Sum of Subsets)?
Say the word! You’re crushing the syllabus!