This paper concerns the variation tolerance in signal processing integrated circuits. Motivated by the fact that variation-induced timing faults at different locations in signal processing circuits have different effects on the sig- nal processing performance, we developed an importance- aware clock skew scheduling technique, called soft clock skew scheduling, that can realize system-level tolerance to variation-induced timing faults. With state-parallel Viterbi decoders as test vehicles, we demonstrated its effectiveness on increasing the achievable clock frequency in presence of significant variation-induced timing faults, while maintain- ing good decoding performance.