A Generalized Permutation Approach to Job Shop Scheduling with Genetic Algorithms
Christian Bierwirth
Abstract:
In order to sequence the tasks of a job shop problem (JSP) on a number of machines related to the technological machine order of jobs, a new representation technique -- mathematically known as "permutation with repetition" is presented. The main advantage of this single chromosome representation is -- in analogy to the permutation scheme of the traveling salesman problem (TSP) -- that it cannot produce illegal sets of operation sequences (infeasible symbolic solutions). As a consequence of the representation scheme a new crossover operator preserving the initial scheme structure of permutations with repetition will be sketched. Its behavior is similar to the well known Order-Crossover for simple permutation schemes. Actually the GOX operator for permutations with repetition arises from a Generalisation of OX. Computational experiments show, that GOX passes the information from a couple of parent solutions efficiently to offspring solutions. Together, the new representation and GOX support the cooperative aspect of the genetic search for scheduling problems strongly.
Bibliographical:
@misc{ bierwirth95generalized, author = "C. Bierwirth", title = "A generalized permutation approach to job shop scheduling with genetic algorithms", text = "Bierwirth, C., 1995, A generalized permutation approach to job shop scheduling with genetic algorithms, OR Spektrum, 17, 87-92.", year = "1995" }