This paper presents a new mathematical model for a redundancyallocation problem (RAP) withcold-standby redundancy strategy and multiple component choices. The applications of the proposed model arecommon in electrical power, transformation, telecommunication systems, etc. Manystudies have concentrated onone type of time-to-failure, butin thispaper, two components of time-to-failures which follow hypo-exponential and exponential distributionare investigated. The goal of the RAP is to select available components and redundancy level for each subsystem for maximizing system reliability under cost and weight constraints. Sincethe proposed model belongs to NP-hard class, we proposed two metaheuristic algorithms; namely, simulated annealing and genetic algorithm to solve it. In addition, a numerical example is presented to demonstrate the application of the proposed solution methodology.