OR Spektrum (1995) 17:87-92 9 Springer-Verlag 1995 A generalized permutation approach to job shop scheduling

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 representa-tion technique- mathematically known as "permutation with repetition " is presented. The main advantage of this single chromosome r presentation is- in analogy to the permutation scheme of the traveling salesman problem (TSP)- that it cannot produce illegal operation se-quences. 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 experi-ments show, that GOX passes the information from a couple of parent solutions efficiently to offspring solu-tions. Together, the new representation a d GOX sup-port the cooperative aspect of genetic search for schedul-ing problems trongly. Znsammenfassung. Im vorliegenden Beitrag wird ein neuer Ansatz zur genetischen Repr/isentation des Ma-schinenbelegungsproblems vorgestellt. Der Ansatz ba-siert auf dem bekannten Konzept der Repr/isentation von Rundreiseproblemen durch Permutationen. In Erweite-rung dieses Konzepts werden,,Permutationen mit Wie-derholung " zur Kodierung von L6sungen eingesetzt. Die zentrale Schwierigkeit vorangegangener Ans/itze, n/im-lich die Behandlung unzul/issiger Genotypen, entf'~illt vollst/indig. Permutationen mit Wiederholung reprfisen-tieren grunds/itzlich zul/issige Ltsungen des betrachteten Problems. Aus einer Generalisierung der permutations-bewahrenden Order-Crossover Technik (OX) wird de