Seite - 82 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 68 Partiallymappedcrossover (PMX)[32,33]: Thisoperatoruses twocutpoints (Figure5). Thepart of thefirstparentbetweenthe twocutpoints is copiedto thechildren. Then, the followingpartsof the childrenarefilledbyamappingbetweenthe twoparents, so that theirabsolutepositionsare inherited wherepossible fromthesecondparent. Figure5.Partiallymappedcrossover (PMX)operator. Figure 6 shows an example of the PMXcrossover. The cross points in bothparents serve to formthechildchromosome.The16 listed lotsof the4 jobsarerandomlydistributedoneachparent chromosome.Whencrossed, theyformthechildchromosomewith16 lots. Figure6.PMXcrossoveroperatorexamplewithbatch index. Thecrossparentsarecomposedof thebatchesof the jobs listed inTable8. Table8.Enumerationof thebatches for jobs. Job Batches BatchIndex 1 4 1–4 2 4 5–8 3 4 9–12 4 4 13–16 Figures7and8showrepresentationsof tasks for twoandfourmachinesperstage. Theoriginal sequence is ordered considering the enumeration of the jobs and their batches. Eachmachine is assignedbatches toprocess,whichformthe tasksofeach job. Eachmachinemustprocessacertainset 82