Although the theory of failure diagnosis of discrete-event systems has been proved effective, one question remains open: assuming that the generated language is diagnosable, how long does the diagnosis system take to detect the failure occurrence? In this paper, although we still consider the DES as a dynamic system whose evolution is determined by the asynchronous occurrence of events, we add to each transition a weight that corresponds to the maximum time that takes for the event to occur since the moment it fires (the so-called time-weighted model), to propose an effective algorithm to determining the maximum time for failure diagnosis. This result was only possible because we derive a new necessary and sufficient condition for diagnosability verification and by the use of max-plus algebra to obtain a matrix representation for time-weighted automata.