Two Combinatorial Algorithms for the Constrained Assignment Problem with Bounds and Penalties

Guojun Hu, Junran Lichen and Pengxiang Pan ()
Additional contact information
Guojun Hu: School of Mathematics and Statistics, Yunnan University, Kunming 650504, China
Junran Lichen: School of Mathematics and Physics, Beijing University of Chemical Technology, No. 15, North Third Ring East Road, Beijing 100190, China
Pengxiang Pan: School of Mathematics and Statistics, Yunnan University, Kunming 650504, China

Mathematics, 2023, vol. 11, issue 24, 1-12

Abstract: In the paper, we consider a generalization of the classical assignment problem, which is called the constrained assignment problem with bounds and penalties (CA-BP). Specifically, given a set of machines and a set of independent jobs, each machine has a lower and upper bound on the number of jobs that can be executed, and each job must be either executed on some machine with a given processing time or rejected with a penalty that we must pay for. No job can be executed on more than one machine. We aim to find an assignment scheme for these jobs that satisfies the constraints mentioned above. The objective is to minimize the total processing time of executed jobs as well as the penalties from rejected jobs. The CA-BP is related to some practical applications such as edge computing , which involves selecting tasks and processing them on the edge servers of an internet network. As a result, a motivation of this study is to improve the efficiency of internet networks by limiting the lower bound of the number of objects processed by each edge server. Our main contribution is modifying the previous network flow algorithms to satisfy the lower capacity constraints, for which we design two exact combinatorial algorithms to solve the CA-BP. Our methodologies and results bring novel perspectives into other research areas related to the assignment problem.

Keywords: cloud–edge collaborative; constrained assignment; bounds; penalties; combinatorial algorithms (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/24/4883/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/24/4883/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:24:p:4883-:d:1294753

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().