The stochastic job shop problem was solved using two genetic algorithms. The first was a stochastic constrained genetic algorithm to minimize total tardiness and to evaluate chromosomes using probability Gantt charting. The second was a stochastic constrained genetic algorithm to minimize total tardiness and to evaluate chromosomes using simulation. In these two algorithms, the fitness function was altered to a utility function defined as follows: Probability {total tardiness of a chromosome ≤ target total tardiness}. When comparing the two chromosome evaluation methods, the probability Gantt charting deviated from the true mean for both the makespan and the average flow time by 3% and 1.7% respectively. Also, all averages estimated for both the makespan and the average flow time fall within the 90% confidence interval. Furthermore, using probability Gantt charting reduced the CPU time needed by 554.9% when compared to the CPU time needed by simulation. When the results obtained by the two stochastic constrained genetic algorithms were compared, the second algorithm reduced the actual expected total tardiness, the actual worse case total tardiness, and the risk by 30.3%, 56%, and 18% respectively.

The standard genetic algorithm has been modified to address the job shop problem by constraining the genes in the chromosomes during the genetic operators implementations to match general theoretical sequencing constraints.

When comparing the deterministic constrained and unconstrained genetic algorithms to minimize makespan, the constrained algorithm improved the average percentage error by 27.44%. Also, when the deterministic constrained and unconstrained genetic algorithms to minimize total tardiness were compared, the constrained algorithm improved the average percentage errors by 248.77%.