Algorithms for the Constrained Assignment Problems with Bounds and Maximum Penalty

As a result of the substantial increase in mobile data traffic that has placed a lot of pressure on cloud computing centers, it is necessary to select the network edge servers for data processing, this process is called edge computing. In order to use the network edge servers more efficiently, it is usually expected that the number of objects served by any edge server will exceed a certain number and also be controlled within a certain number. In order to efficiently solve the aforementioned problem, motivated by the Cloud-Edge Collaborative Computing Framework, we model the task offloading problem as a constrained assignment problems with bounds and maximum penalty (CA-BMP). Specifically, given m machines and n independent jobs, the machine \(g_{i}\) receives at least \(l_i\) and at most \(u_i\) jobs to execute, and each job must be either continuously executed on some machine with its processing time, or rejected with its penalty that we must pay for. We consider the CA-BMP problem and its important variant. (1) The CA-BMP problem is to find an assignment scheme of jobs to satisfy the constraints as mentioned-above, and the objective is to minimize the total processing times of executed jobs plus maximum penalty of rejected jobs; (2) The penalized assignment problem with bounds (the PA-B problem) is to find an assignment scheme of jobs to satisfy the constraints as mentioned-above, the objective is to minimize the total processing times of executed jobs plus maximum penalty of executed jobs. As our main contributions, we design two exact combinatorial algorithms to solve the CA-BMP problem and the PA-B problem, respectively. In addition, we give numerical examples to illustrate the execution processes of the two algorithms we proposed.