Redundancy allocation has been widely used in many fields to enhance system reliability. In practice, it is essential to take component reliability uncertainties into consideration and find smart configuration for system design. In this article, a redundancy allocation problem for k-out-of-n series-parallel system is employed, and the optimization problem considering interval valued uncertainty and non-identical component mixing is presented. The Min-Max regret and the coefficient of deviation are respectively introduced to improve existing order relation criterion for interval analysis and two associated optimization models are established. The general objective is to obtain high system reliability with small deviation. Then, an appropriate genetic algorithm based on the characteristic of proposed models is developed. Finally, several numerical cases are conducted to demonstrate the validity and efficiency of proposed approach. This work may contribute to more flexible design for redundancy allocation.