# Research on Cloud Task Scheduling Algorithm with Conflict Constraints Based on Branch-and-Price
## 1 Introduction  
With the increasing development of cloud computing technology, the huge energy consumption in cloud computing has attracted wide attention. The proportion of energy consumption in cloud data centers is estimated as 1.4% of the global energy consumption, which increases by approximately 12% annually [1]. Currently, many studies in cloud computing focus on task scheduling algorithms with the goal of reducing energy consumption [2, 3]. Most of the existing works use heuristic algorithms, random algorithms, and intelligent algorithms to solve the approximate optimal solution of the problem [4, 5]. To reduce the energy consumption of cloud computing systems, an effective and common method is to schedule tasks to as few virtual machines (VMs) as possible [6]. However, the existing studies lack research on the stability of cloud computing system, especially without considering the antiaffinity constraints between tasks. Kubernetes [7] first introduced the new feature of node antiaffinity. This feature can improve the usability and robustness of the applications. Similarly, OpenStack [8] has antiaffinity scheduler filter. In a cloud computing system, the antiaffinity constraint refers to the existence of interference factors between two tasks in the system. When these two tasks are deployed on the same VM, their performance may be influenced by each other. For example, [PERSON] et al. [9] experimentally verified that deploying a disk-intensive task to a physical machine with multiple disk-intensive tasks will lead to resource contention and serious performance degradation. Therefore, when scheduling tasks, it is necessary to avoid the deployment of mutually interfering tasks on the same VM. This problem can be equivalent to the multidimensional bin packing problem with conflicts (MDBPPC). The MDBPPC model originates from the classic bin packing problem model, but due to its difficulty in solving, research on this problem is very few. The existing research focuseson the bin packing problem with conflicts (BPPC) of single-dimension resources. [PERSON] [10] first introduced the conflict relationship in the traditional bin packing model, and represented the conflict relationship in the form of a graph structure. [PERSON] et al. [11] studied the bin packing problem with stability, which is a variant of BPPC. Note that previous works have focused on algorithm design for single-dimension resource requirements without considering the situation of multidimension resource requirements. Therefore, this paper studies the cloud computing task scheduling problem with antiaffinity constraints, and aims to minimize the number of cloud computing VMs to reduce the energy consumption of the cloud computing system. The main contributions of this work are summarized as follows:  
* We formulate the low-energy task scheduling problem with antiaffinity constraints in cloud computing as an MDBPPC problem. To reduce the solution difficulty, we decompose the problem by Lagrange relaxation principle and Dantzig-Wolfe decomposition principle. * To obtain the optimal integer solution, we design an efficient branch-and-price algorithm with several improvements. First, we introduce the idea of the dominant resource proportion into the process of initial solution generation. Second, we use an efficient branch rule based on multiple pattern. Third, we use the hot start and upper bound strategy to improve the branch-and-price algorithm. * We conduct numerical simulations on three scales to evaluate the correctness and effectiveness of our proposed algorithm. Moreover, we verify the effectiveness of the initial solution strategy and the branching strategy. The remainder of this paper is organized as follows. Section 2 summarizes the related work. Section 3 describes the cloud computing task scheduling problem with conflict constraints, Section 4 decomposes the original model. Section 5 proposes a task scheduling algorithm based on branch-and-price, and Section 6 gives the experimental results. Section 7 summarizes the work of the full text.