Page - 81 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 68 the three taskswillbereadyat thesametimetobeassignedindividually tomachinesavailable in the nextstage,until the last (6th) stage. Inthepost-secondstages, thetasks thatarereadytobeassignedare intheprocessbuffer. Thetask thathas the longestprocessingtimeisassignedfirst toanavailablemachine. Thecalculationof the total completion timeCmax is as follows. The timeCi,p for completing taskp in stage i is calculated accordingto the formula Ci,p= min 1≤ l≤m {max { Ci,p+Sil,qp; Ci−1,p } +pil,q}. (3) Themaximumcompletiontimeofall tasksand jobs iscalculatedas Cmax=max Q p=1 { C7,p } . (4) Q indicates the totalnumberof tasks forall jobs.Cm,p is thecompletion timeof task p∈Tj in the last stage7∈S.The totalenergyconsumptionEopof theexecutionofall tasks iscalculatedas Eop= Q ∑ q=1 pil,q ·Eil. (5) whereEil indicates the electrical power consumptionofmachine l in stage i, andpil,q refers to the processingtimeof the taskq∈T. 5.Bi-ObjectiveGeneticAlgorithm 5.1.NondominatedSortingGeneticAlgorithmII (NSGA-II) TheNSGA-IIalgorithmisusedtoassigntasks tomachinesso thatCmax andEop areminimized. NSGA-II is amultiobjective genetic algorithm characterized by elitism and stacking distance to maintain thediversityof thepopulation tofindasmanyPareto-optimal solutions aspossible [24]. It generates apopulationofN individuals,whereeach represents apossible solution. Individuals evolvethroughgeneticoperators tofindoptimalornear-optimalsolutions. Threeoperatorsareusually applied: tournament selection (usinga stacking tournamentoperator), crossover, andmutation to generateanotherN individualsorchildren. Fromthemixtureof these twopopulations,anewpopulationofsize2N is created. Then, thebest individualsare takenaccordingto theirfitnessvaluebyorderingthepopulationonnondominated fronts. Individuals fromthebestnondominatedfrontsarefirst taken,onebyone,untilN individuals areselected. Thecrowdingdistance is thencomparedtopreservediversity in thepopulation. Thisoperator compares twosolutionsandchoosesa tournamentwinnerbyselectingthesettingthat is locatedon thebestPareto front. If theparticipating tournamentconfigurationsareonthesamefront, thebest crowdingdistance (highest) todetermine thewinningsetting isused. Later, thealgorithmapplies the basicgeneticoperatorsandpromotes thenextgenerationcyclewith theconfigurations thatoccupythe best fronts,preservingthediversity throughthecrowdingdistance.A job isassignedtoamachine at agiven stageby taking into considerationprocessing speeds, setup times,machine availability, andenergyconsumption. Eachsolution isencodedinapermutationof integers. 5.2. CrossoverOperators Crossoveroperatorsallowtheobtainingofnewsolutions (children)bycombiningindividuals (parents)of thepopulation. Thecrossoveroperator isappliedunderacertainprobability. In thispaper, weconsider twooperators: thepartiallymappedcrossoverandtheordercrossover. 81