## 4 The Proposed Hybrid Method
Also, the \(P\)[p\({}_{i}\)] records when the processor p\({}_{i}\) will be free. Moreover, \(|P|\) and \(|T|\) stand for the number of processors and tasks, respectively. The value of communication_time (\(t_{i}\), \(t_{j}\)) also indicates the cost of communication between the processor executing \(t_{i}\) and the processor executing \(t_{j}\). It should be noted that if both processors are same, the communication cost will be zero. Finally, the maximum \(P[\text{p}_{i}]\) for all processors is considered to determine the makespan of the schedule. ```
Schedule-Initialization (schedule [1... 2][1... n], \(V\), \(P\)) // \(V\) is the set of tasks, //P is the set of processors For all Tasks \(t_{i}\in V\) in task graph  ParentsCount [\(t_{i}\)] = number of \(t_{i}\) parents in task graph  ReadyTasks = {\(t_{i}\in V\) | ParentsCount [\(t_{i}\)] = 0} // Prepare the ready tasks to execute \(j=1\) While (ReadyTasks set is not Empty)  Choose a Task \(t_{k}\) from the ReadyTasks set randomly  Add \(t_{k}\) to Schedule [1][\(j\)]  Choose a Processor p from the ProcessorList randomly  Add p to Schedule [2][\(j\)] \(j=j+1\) For all Children \(t_{i}\in\{\text{Successors of }t_{k}\}\)  ParentsCount [\(t_{i}\)] = ParentsCount [\(t_{i}\)] - 1  if (ParentsCount [\(t_{i}\)] == 0)  Add \(t_{i}\) to ReadyTasks set
```  
**Algorithm 1**Schedule Initialization Algorithm  
The dominance rank of each solution is determined in the following phase, where s is the number of solutions that are dominating it. The lower rank value indicates the better quality of the answer. Dominance rank values are used in roulette wheel selection, in which good solutions are more likely to be selected than poor solutions. The roulette wheel selection mechanism selects the solutions according to the size of the region they occupy on the wheel. Hence, the value of dominance ranks is changed in such a way that big values show better ranks. To do this, all dominance ranks are subtracted from the biggest dominance rank. Later on, the archive is updated with recently found non-dominated solutions, according to the flowchart in Figure 4. This phase also uses dominance rank values, in which it inserts all solutions with dominance rank zero into the archive and then removes all solutions in the archive dominated by the newly inserted one. ```
Makespan-Calculation (Schedule [1... 2][1... n], ExecutionTime [], CommunicationTime []) //ExecutionTime is the tasks execution time //CommunicationTime is the cost of edges between task pairs \(P\) [1 | \(P\) | = [0], AT [1... | \(\Gamma\) | = [0], FT [1... | \(\Gamma\) | = [0] // \(\Gamma\) | and \(\Gamma\)] are the number of processors and number of tasks respectively //P[pi] is the time at which processor pi becomes idle //AT[\(t_{i}\)]is the time that ti would be ready to execute //FT[\(t_{i}\)]is the finish time of task\(t_{i}\) for \(i=0\) to \(1\) \(t_{i}\) = Schedule [0][\(i\)] \(P\) [Schedule [1][\(i\)]] = max (AT [\(t_{i}\)], \(P\) [Schedule [1][\(i\)]] + ExecutionTime(\(t_{i}\)))  FT[\(t_{i}\)] = \(P\) [schedule [1][\(i\)]]  for all Tasks \(t_{j}\in\text{Successors}(t_{i})\) in the task graph  temp = FT [\(t_{i}\)];  if (schedule [1][\(i\)] is not same as processor assigned to \(t_{i}\))  temp = temp + Communication_time (\(t_{i}\), \(t_{j}\))  AT [\(t_{j}\)] = max (temp, AT [\(t_{j}\)])  Makespan = Max (\(P\) [1... | \(P\) | ])
```  
**Algorithm 2**Makespan CalculationIn the next step, the VNS method is used across archives to further leverage the greatest solutions so far discovered. In this manner, the non-dominated solutions in the archive are modified and improved. Algorithm 3 shows the pseudocode for the VNS algorithm. The suggested hybrid method applies the VNS methodology over a maximum of 10 solutions in the archive and iterates the inner loop 10 times to prevent time-consuming VNS. The definition of the neighborhood structure N in the VNS algorithm results in a moderately significant alteration of the solution. Figure 4: Proposed Hybrid Method.