This paper addresses stochastic optimization of a multi-component maintenance system. In particular, we present a novel phantom gradient estimator called CPhET. We compare the performance of the CPhET estimator with that of the general purpose method simultaneous perturbation (SP). Our results indicate that CPhET is more suitable than SP for sensitivity analysis of moderately sized systems. In addition, CPhET is preferable to SP for optimization of systems if the dimension of the vector of control parameters is small.