In Part I (Rodriguez, Vecchietti, Harjunkoski, & Grossmann, 2013), we proposed an optimization model to redesign the supply chain of spare parts industry under demand uncertainty from strategic and tactical perspectives in a planning horizon consisting of multiple time periods. To address large scale industrial problems, a Lagrangean scheme is proposed to decompose the MINLP of Part I according to the warehouses. The subproblems are first approximated by an adaptive piece-wise linearization scheme that provides lower bounds, and the MILP is further relaxed to an LP to improve solution efficiency while providing a valid lower bound. An initialization scheme is designed to obtain good initial Lagrange multipliers, which are scaled to accelerate the convergence. To obtain feasible solutions, an adaptive linearization scheme is also introduced. The results from an illustrative problem and two real world industrial problems show that the method can obtain optimal or near optimal solutions in modest computational times.