In this paper, the focus is on mechanical systems that, like a ship or a submarine, perform risky missions and that must remain operating for the whole mission time. Missions take place far from the operational base and so, in case of failures, although repairs are possible, spares parts cannot be resupplied. Hence, given space constraints, the problem is to define the optimal set of spare parts that should be taken aboard, to maximize the probability to complete the mission. To solve this problem, we propose a constructive algorithm that generates the Pareto Optimal Frontier of all the non-dominated solutions, in terms of the system’s reliability and of required space. At first, the algorithm is formulated in a generic way; next, it is contextualized to the common case of Weibull distributed failure times. In this condition, the underlying equations of the model cannot be solved in closed form and an approximated procedure is proposed and validated through extensive numerical simulation.