We present a self-consistent charge density-functional tight binding (SCC-DFTB) parametrization for PtRu alloys, which is developed by employing a training set of alloy cluster energies and forces obtained from Kohn-Sham density-functional theory (DFT) calculations. Extensive simulations of a testing set of PtRu alloy nanoclusters show that this SCC-DFTB scheme is capable of capturing cluster formation energies with high accuracy relative to DFT calculations. The new SCC-DFTB parametrization is employed within a genetic algorithm to search for global minima of PtRu clusters in the range of 13-81 atoms and the emergence of Ru-core/Pt-shell structures at intermediate alloy compositions, consistent with known results, is systematically demonstrated. Our new SCC-DFTB parametrization enables computationally inexpensive and accurate modeling of Pt-Ru clusters that are among the best-performing catalysts in numerous energy applications.