Based on the worst-case response time (WCRT) schedulability analysis for hard real-time systems, a new scheduling algorithm called extended fault-tolerant fixed-priority with preemption threshold (FT-FPPT*) is proposed in the software fault-tolerant model. This algorithm can be used, together with the schedulability analysis, to effectively enhance the fault-tolerant capability when the traditional fault-tolerant fixed-priority preemptive (FT-FPP) scheduling and fault-tolerant fixed-priority scheduling with preemption threshold (FT-FPPT) are no longer appropriate. At length, an optimal priority assignment search algorithm (PASA) is presented. PASA is optimal in the sense that the fault resilience of task sets is maximized for the proposed analysis. The effectiveness of the proposed approach is also evaluated by simulation.