This paper concerns the variation tolerance in applicationspecific digital signal processing (DSP) integrated circuits. Motivated by the fact that variation-induced timing faults at different locations in DSP circuits may have (largely) different effects on the overall signal processing performance, we developed an importance-aware clock skew scheduling technique, referred to as 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 (by more than 10%) while maintaining acceptable decoding performance in presence of significant variation-induced timing faults.