On Permutation Representations for Scheduling Problems

In this paper we concentrate on Job Shop Scheduling as a representative of constrained combinatorial problems. We introduce a new permutation representation for this problem. Three crossover operators different in tending to preserve the relative order, the absolute order, and the position in the permutation, are defined. By experiment we observe the strongest phenotypical correlation between parents and offspring when respecting the absolute order. It is shown that a genetic algorithm using an operator which preserves the absolute order also obtains a superior solution quality.