Due to constant fluctuations in market demands, nowadays scheduling of flexible manufacturing systems is taking great importance to improve competitiveness. Coloured Petri Nets (CPN) is a high level modelling formalism which have been widely used to model and verify systems, allowing representing not only the system’s dynamic behaviour but also the information flow. One approach that focuses in performance optimization of industrial systems is the one that uses the CPN formalism extended with time features (Timed Coloured Petri Nets) and explores all the possible states of the model (state space) looking for states of particular interest under industrial scope. Unfortunately, using the time extension, the state space becomes awkward for most industrial problems, reason why there is a recognized need of approaches that could tackle optimization problems such as the scheduling of manufacturing activities without simplifying any important aspect of the real system. In this paper a timed state space approach for properties verification and systems optimization is presented together with new algorithms in order to get better results when time is used as a cost function for optimizing the makespan of manufacturing systems. A benchmarking example of a job-shop is modelled in CPN formalism to illustrate the improvements that can be achieved with the proposed implementations.