Seite - 83 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 68 of tasks;eachset isassignedaprocessingorder (Proc.Order). Thesesetsare formedaccordingto the processingcompatibility. ݉ͳ ݉ʹ Ordered 1 2 1 2 Proc. Order 2 3 13 15 5 6 7 8 1 4 9 10 11 12 14 16 Batch 1 4 2 1 3 4 Jobs Figure7.Chromosomerepresentationexamplewith twomachinesperstage. ݉ͳ ݉ʹ ݉͵ ݉Ͷ Ordered 1 2 1 1 Proc. Order 2 3 6 7 3 15 5 8 10 11 12 16 1 4 9 14 Batch 1 4 2 1 4 2 3 4 1 3 4 Jobs Figure8.Chromosomerepresentationexamplewith fourmachinesperstage. The tasksof Jobs1,3,and4canbeprocessed in thesamesetat thesametime. Thetasksof Job2 areput intoaseparatesetbecause theyarenotcompatiblewitheachother. Forexample, inFigure7, the first two tasks (1-1, 4-1) are processed byMachine 1, then the second setwith one task (2-1). InMachine2, twotasksof thefirst set (1-2and3-1)areprocessed,assumingthat themachinehasonly thecapacity toprocessupto6batches (60kg). Thesecondsetwill thenbefollowedbyonetask (4-1). Figure8showsfourmachinesperstage. Fourbatchesareassignedtoeachmachine.Machines1 and2process twosetsof tasks.Machines3and4processonlyoneset.Uponcompletionof the tasks processed insets inStep1, in the laterstages, theywillbeprocessed individually. Ordercrossover (OX) [32,34–37]: Twocutpointsareselectedrandomly; thepartof thefirstparent locatedbetween these twocutpoints is copied to the child. Thechild’sother spacesare left blank. Thevaluescopiedto thechildaredeleted inthesecondparent. Thefollowingpositions in thechild arefilledstarting in theblankspacesandconsideringtheorder foundin thesecondparent (Figure9). Figure9.Ordercrossover (OX)operator. 5.3.MutationOperators Mutationoperatorsproducesmallchanges inindividualsaccordingtoaprobability. Thisoperator helps to prevent falling into local optima and to extend the search space of the algorithm. Three mutationoperatorsareconsidered:Displacement,Exchange,andInsertion. Displacement isageneralizationof the insertionmutation, inwhich insteadofmovingasingle value, severalvaluesarechanged(Figure10). Theexchangeoperatorselects tworandompointsand thesepositionvaluesareexchanged(Figure11). In insertion,avalue is selectedrandomlyandwillbe insertedatanarbitraryposition(Figure12). 83