As an important aspect of reliability theory, availability has now been considered a very meaningful design criterion of repairable system. This paper investigates the availability evaluation and design optimization of the multi-state k-out-of-n: G systems considering random weight threshold. The system availability is evaluated by extending the recursive algorithm (RA) and universal generating function (UGF) technique. Based on the traditional recursive algorithm, the total probability theorem is used to solve the discrete random weight threshold. Another better UGF method combines a new stochastic joint operator, which is suitable for both continuous and discrete random weight thresholds. Furthermore, we constructed two system design optimization models under availability or cost constraint respectively, and genetic algorithm (GA) programming can be applied to obtain the optimal state probability distribution and weight distribution of multi-state components of the suggested system. Finally, through numerical examples, the flexibility and effectiveness of the proposed methods for design optimization are demonstrated. In addition, two evaluation methods are compared to show that the customized UGF method features higher generality than RA in the case of continuous stochastic weight threshold, and higher operational efficiency in the case of increasing component quantity and state. The results can be helpful for engineers to optimize the design of complex systems.