The topic of this paper is the on-line trajectory tracking control on a sliding horizon of Timed Event Graphs with specications dened by a P-time Event Graph. Making the most of the specic structures of the systems, the CPU time of the on-line procedure is drastically reduced with two techniques: The use of specic algorithms of the graph theory instead of generic algorithms; an o-line preparation which avoid the useless repetition of the same calculations. As a consequence, the approach can deal with long horizons and important systems and the application eld of the trajectory tracking control is expanded.