Algorithms for the Constrained Assignment Problems with Bounds and Maximum Penalty

doi:10.1007/978-981-97-7801-0_3

	Algorithms for the Constrained Assignment Problems with Bounds and Maximum Penalty
	Hu, Guojun 1,2; Pan, Pengxiang 1; Lichen, Junran 3; Cai, Lijian4
	2024
会议名称	18th International Conference on Algorithmic Aspects in Information and Management, AAIM 2024
会议录名称	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
卷号	15180 LNCS
页码	27-39
会议日期	September 21, 2024 - September 23, 2024
会议地点	Virtual, Online
出版者	Springer Science and Business Media Deutschland GmbH
摘要	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 gi receives at least li and at most ui 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. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2024.
关键词	Cloud platforms Combinatorial mathematics Computation offloading Constraint satisfaction problems Mobile edge computing Assignment problems Bound Cloud-edge collaboration Combinatorial algorithm Constrained assignment Edge server Maximum penalty Mobile data traffic Network edges Total processing time
DOI	10.1007/978-981-97-7801-0_3
收录类别	EI
语种	英语
EI入藏号	20244117152414
EI分类号	1105.1 ; 1201.8
原始文献类型	Conference article (CA)
文献类型	会议论文
条目标识符	http://ir.lzufe.edu.cn/handle/39EH0E1M/38342
专题	信息工程与人工智能学院
通讯作者	Cai, Lijian
作者单位	1.School of Mathematics and Statistics, Yunnan University, Kunming; 650504, China; 2.School of Mathematics, Yunnan Normal University, Kunming; 650504, China; 3.School of Mathematics and Physics, Beijing University of Chemical Technology, Beijing; 100190, China; 4.School of Information Engineering, Lanzhou University of Finance and Economics, Lanzhou; 730020, China
通讯作者单位	兰州财经大学
推荐引用方式 GB/T 7714	Hu, Guojun,Pan, Pengxiang,Lichen, Junran,et al. Algorithms for the Constrained Assignment Problems with Bounds and Maximum Penalty[C]:Springer Science and Business Media Deutschland GmbH,2024:27-39.