Seite - 80 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 68 Batchesare listedaccordingto the jobtowhichtheybelong. Table7showsanexample thefive jobs. If Job1hasninebatches, theyare listedfrom1to9. If Job2has12batches, theyare listedfrom10 to21.ReachingJob5,wehaveaccumulated62batches. Table7.Exampleofenumerationofbatches for jobs. Job 1 2 3 4 5 Batches 9 12 16 15 10 Batch index 1–9 10–21 22–37 38–52 53–62 Figure3showsanexampleof theproductionrepresentation.Groupsarecomposedaccordingto thenumberofmachines in thestage (mi). Thebatchesofeach jobarerandomlydistributedbetween thegroups. Toobtain thenumberofbatchespergroup(a),wedivide the totalamountofbatchesby thenumberofmachinesperstage. Machine 1 Machine 2 Machine ݉୧ 56 23 ڮ 19 16 1 55 ڮ 62 27 ڮ 11 24 ڮ 37 17 1 2 ڮ ܽെͳ ܽ 1 2 ڮ ܽെͳ ܽ 1 2 ڮ ܽെͳ ܽ Figure3.Exampleof therepresentationof thechromosomeformimachinesperstage. Letusconsidersixstageswithm1= 4machinesperstage. Thechromosomeiscomposedof4 groups. Letusassumethatwehave62batches for5 jobs. This isequal to62 (batches)/4(machines perstage)=15.5 (batchespergroup). Theresult is roundedto thenearesthigher integer, endingwith a=16batchespergroup.AnexampleofprocessingtasksonMachine1 is showninFigure4. Machine 1 Original Sequence 56 23 38 35 1 42 61 14 51 11 5 59 48 15 19 16 Batches Ordered Sequence 1 2 3 Proc. Order 1 5 23 35 38 42 51 48 56 61 59 14 11 15 19 16 Batches 1 3 4 4 5 2 Jobs Figure4.Exampleof tasksonMachine1. In the ordered sequence, “Jobs” indicate jobs towhich the batches belong according to their enumeration. These groups indicate thenumber of total tasks for each job from left to right. For example, in theorderedsequence, Job4has twotasks; thefirstone“4-1”has threebatches (38,42,51) andthesecondone“4-2”hasonebatch(48). “Proc.Order” indicates theorderofprocessingof the taskgroups.Assumingthatamachine in Stage1hastoprocessupto70kg(7batches),Group1iscomposedofsetsof tasks1-1 (1,5),3-1 (23,35), 4-1 (38,42,51)withsevenbatches.Whenthecapacityof themachine isfilled,Group2is formedfor the tasks4-2 (48)and5-1 (56,61,59).Assumingthat thebatchesof Job2arenotcompatiblewithany of theremainingfour jobs, thebatchesareprocessedseparately fromtheother twogroups, forming the task2-1withfivebatches (14, 11, 15, 19, 16).Whenthefirstgroup’s taskshavecompleted their processing in themachine, thesecondgroupisprocessed,andsoon. Thetasksprocessedinthegroupareassignedtothemachinesof thefollowingstages individually according to their orderof completion in thefirst stage. When the tasksof agroup—for example, Group1 (1-1, 3-1, 4-1)—areprocessed together, the completion time is the same for all. Therefore, 80