# Research on Cloud Task Scheduling Algorithm with Conflict Constraints Based on Branch-and-Price
## 6 Experimental Results and Analysis
### Experimental Results  
To evaluate the efficiency of the BPTSC algorithm proposed in this paper, Table 2 summarizes the evaluation results of BPTSC. As the number of tasks increases, the difficulty of the problem increases exponentially. As the problem scale increases from 30 to 200, the number of nodes increases by approximately 15 times, the number of columns increases by more than 8 times, and the average execution time increases by 25 times. Notably, the model is the most difficult to solve when the conflict density is between 10% and 30%. In this case, the key constraint of the model is the multidimensional resource capacity constraint. This makes the solution space of the search tree very large, requiring the generation of a large number of branch nodes and columns. When the conflict density is between 70-90%, the model is the easiest to solve. In this instance, the key constraint is the task conflict constraint; thus, the solution space of the model is small. Only generating a small number of nodes and columns can obtain the optimal solution of the problem. On the other hand, as expected, the value of the optimal solution increases as the density of the conflict graph increases. When the conflict density is 10%, the value of the optimal solution is usually quite similar to the no-conflict constraint case. However, for high-density instances (90%), almost 90% of tasks are scheduled to different VMs. As shown in the fourth and fifth columns of Table 2, most feasible columns are generated at the root node. The number of columns generated by the root node accounts for more than 2/3 of the total number of columns, resulting in the root node accounting for more than half of the total execution time. From the sixth and seventh columns of Table 2, the Lagrange lower bound obtained by the root node is very close to the optimal solution, reaching over 98%. In addition, we also conduct ultra-large-scale (1000 tasks) experiments. The experimental results show that when the conflict density is high (70-90%), the execution time of BPTSC is still very short. In other cases, the execution time usually exceeds our set time (1 h). The BPTSC algorithm is an accurate algorithm, while the heuristic algorithms commonly used as the benchmark are approximation algorithms, and cannot obtain optimal solution. Thus, we use CPLEX as the benchmark to compare the efficiency of the algorithm. CPLEX directly solves the original model without using Lagrange relaxation principle and Dantzig-Wolfe decomposition principle. Meanwhile, to verify the effectiveness of the initial solution generation strategy of BPTSC, Figure 4a-c, respectively, show the comparison of the number of nodes, number of columns, and execution time between BPTSC and the branch-and-price algorithm using the descending first fit strategy, which is identified by FFBP in Figure 4. Figure 4c also provides a comparison between the two branch-and-price algorithms and CPLEX in terms of execution time. From Figure 4a,b, the initial solution generation strategy of BPTSC outperforms FFBP in terms of the number of nodes and number of columns, especially when the task size is large. From Figure 4c, it can be seen that when the number of tasks is small, the execution efficiency of all three algorithms is high. When the number of tasks is medium in scale, BPTSC is superior to FFBP in finding the initial solution. Both of them have much shorter execution time than the algorithm directly using CPLEX. When the number of tasks is large, since most of the execution times of the instances solved by CPLEX exceed our set time (1 h), only the two branch-and-prices are compared. The experimental result is similar to the medium-scale case, and BPTSC is superior to FFBP, which verifies the effectiveness of the initial solution generation strategy of BPTSC.