Abstract: Joint replacement of multiple parts is an optimization problem where the total cost is to be minimized by coordinating the timing of replacing various parts to share resources or setup costs. Searching for a good policy for such a multi-stage combinatorial optimization problem with uncertainty could be prohibitive complex. This paper provides a solution method for a joint replacement problem of engine parts. By utilizing the characteristics of the stochastic coupling constraints, a decomposable model and the corresponding opportunistic Lagrangian relaxation (OLR) method are developed. Numerical testing shows that OLR outperforms two prevalent rule-based methods which rely on priori knowledge of the problem.