Seite - 77 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 68 Table4showscharacteristicsof the jobs.Weconsideraworkloadwithfive jobs forproduction of thefive types of tortillasmost demandedby industry: Regular, Integral, Class 18pcs, Taco 50, andMegaBurro. Each job is characterizedby its type, group, andbatches required forproduction. Ithasseveralassignedbatches. Thisquantitymustbewithinacertainrange that isobtainedfromthe standarddeviationsof theaveragemonthlyproduction inkilogramsof tortillas forayear. Table4. Jobcharacteristics. Job j Name Type Group BatchLimits 1 Regular 1 1 356–446 2 Integral 2 2 34–61 3 Class18pcs 3 1 7–10 4 Taco50 4 1 13–22 5 MegaBurro 5 1 12–20 Thebatch indicates thenumberof10kgtasks thathave tobeprocessed in the job.A jobwithone batch indicatesprocessing10kg,andwithfivebatches indicatesprocessing50kg. Thegroupindicates thecompatibilityof the job tasks. Job tasksbelongingto thesamegroupmay beprocessedsimultaneously. For instance, theycanbeprocessedonallunrelatedmachinesofStage2, if their sizesare less thanorequal to thecapacity inkilogramsof themachines (Table1). The job tasks of thesametypeofdoughcanbecombined, formingcompatibilitygroups. In this case, the jobsof Types1,3,4,and5belongtoGroup1,and jobsofType2belongtoGroup2. Table5 showsprocessing times inminutes for every10kgof tortilla fora job type. The10kg representsa task.Wesee that inStages2and4,allmachinesprocess jobs for thesamedurationsof1 and45min, respectively,dueto the fact that the timedoesnotdependonthe job type. Table5.ProcessingtimePik,jof job jatmachinek instage i foreach10kg. Stage 2 3 4 5 6 7 Machines 1–6 1–6 1–6 1–3 4–6 1–6 1–6 Jobs 1 1 1.25 45 1.43 1.07 12.15 17.25 2 1 1.25 45 1.48 1.11 12.15 17.25 3 1 4.38 45 3.69 2.77 21.38 26.48 4 1 3.13 45 3.00 2.25 24.50 29.60 5 1 0.42 45 2.28 1.14 18.24 23.34 Table6showsthesetuptimeofmachinesateachstage.Atstages from3to7, thesetuptimeis independentof the tasksequence, job type,andweight. Table6.Sequencesetuptimeforallmachines instage i. Stage 2 3 4 5 6 7 Setuptime st2 0.7 0.7 0.5 0 0 AtStage2, thesetuptimeiscalculatedas follows: st2= ( 35+ ( tw 10×5 )) 60 (1) where tw is the totalweight inkilogramsof the tasks tobeprocessedbymachines in thesametime period. These taskshavetobelongto jobsof thesamegroup. 77