Abstract: Chetto and Chetto [3] presented an algorithm for the on-line admission control and run-time scheduling of aperiodic real-time jobs in preemptive uniprocessor environments that are executing systems of periodic hard-real-time tasks. This algorithm requires a significant degree of preprocessing of the system of periodic tasks?in general, this preprocessing takes time exponential in the representation of the periodic task system. In this paper, we develop techniques for speeding up the preprocessing phase of the Chetto and Chetto algorithm, by adapting it for implementation in parallel environments. We validate the effectiveness of our parallelization both by theoretical results, and through simulation experiments.