In this paper, we present a parallel genetic algorithm (pGA) with adaptive control parameters and permutation representation for weighted tardiness scheduling with sequence-dependent setups, an NP-Hard problem. This pGA provides a linear to slightly superlinear speedup relative to its sequential counterpart. As part of our research, we explore the effects of different random number generation algorithms on the runtimes of both sequential and parallel GAs. GAs and other forms of evolutionary computation rely so heavily on random number generation that our results show that we can obtain a 20% increase in the speed of a pGA, and an over 25% increase in the speed of a sequential GA, simply by careful choice of random number generator-both the underlying generator as well as algorithms for specific number types such as Gaussian often needed for mutating real-valued genes.