Two Combinatorial Algorithms for the Constrained Assignment Problem with Bounds and Penalties
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 th...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-12-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/11/24/4883 |
| _version_ | 1797380213894545408 |
|---|---|
| author | Guojun Hu Junran Lichen Pengxiang Pan |
| author_facet | Guojun Hu Junran Lichen Pengxiang Pan |
| author_sort | Guojun Hu |
| collection | DOAJ |
| description | 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 <i>edge computing</i>, 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. |
| first_indexed | 2024-03-08T20:34:05Z |
| format | Article |
| id | doaj.art-a6367654898944eea0ac4f0e676e133b |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-08T20:34:05Z |
| publishDate | 2023-12-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-a6367654898944eea0ac4f0e676e133b2023-12-22T14:23:11ZengMDPI AGMathematics2227-73902023-12-011124488310.3390/math11244883Two Combinatorial Algorithms for the Constrained Assignment Problem with Bounds and PenaltiesGuojun Hu0Junran Lichen1Pengxiang Pan2School of Mathematics and Statistics, Yunnan University, Kunming 650504, ChinaSchool of Mathematics and Physics, Beijing University of Chemical Technology, No. 15, North Third Ring East Road, Beijing 100190, ChinaSchool of Mathematics and Statistics, Yunnan University, Kunming 650504, ChinaIn 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 <i>edge computing</i>, 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.https://www.mdpi.com/2227-7390/11/24/4883cloud–edge collaborativeconstrained assignmentboundspenaltiescombinatorial algorithms |
| spellingShingle | Guojun Hu Junran Lichen Pengxiang Pan Two Combinatorial Algorithms for the Constrained Assignment Problem with Bounds and Penalties Mathematics cloud–edge collaborative constrained assignment bounds penalties combinatorial algorithms |
| title | Two Combinatorial Algorithms for the Constrained Assignment Problem with Bounds and Penalties |
| title_full | Two Combinatorial Algorithms for the Constrained Assignment Problem with Bounds and Penalties |
| title_fullStr | Two Combinatorial Algorithms for the Constrained Assignment Problem with Bounds and Penalties |
| title_full_unstemmed | Two Combinatorial Algorithms for the Constrained Assignment Problem with Bounds and Penalties |
| title_short | Two Combinatorial Algorithms for the Constrained Assignment Problem with Bounds and Penalties |
| title_sort | two combinatorial algorithms for the constrained assignment problem with bounds and penalties |
| topic | cloud–edge collaborative constrained assignment bounds penalties combinatorial algorithms |
| url | https://www.mdpi.com/2227-7390/11/24/4883 |
| work_keys_str_mv | AT guojunhu twocombinatorialalgorithmsfortheconstrainedassignmentproblemwithboundsandpenalties AT junranlichen twocombinatorialalgorithmsfortheconstrainedassignmentproblemwithboundsandpenalties AT pengxiangpan twocombinatorialalgorithmsfortheconstrainedassignmentproblemwithboundsandpenalties |