Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
I have an interesting assignment problem in which I have a cost matrix for workers and tasks, and need to assign each worker to exactly one task to minimize the cost.
However, this is all subject to the constraint that there must be no more than $k$ tasks being performed overall, by any worker.
I have not been able to find any literature about this specific problem and was wondering if it is known, and how best to solve it?
You could formulate it as an Integer linear program (ILP), then implement it in e.g. Pythons pulp library and solve it with a standard solver such as the open source COIN solver.
Based on the comment given below this answer, the ILP could then look as follows:
Let $t \in T$ be a task and $w\in W$ be the workers. The costs of assigning a worker $w$ to a task $t$ are given by $c_{wt}$.
DECISION VARIABLES
$x_{wt}$ Binary variable: $1$ if worker $w \in W$ is working on task $t \in T$ and $0$ if not.
$y_{t}$ Binary variable: $1$ if task $t \in T$ is performed and $0$ if not.
Linear Program \begin{align} \ & \min z = \sum_{w \in W}\sum_{t \in T} x_{wt} \cdot c_{wt} \; \\ \textit{S.t.}\\ \\ & \sum_{t \in T} x_{wt} = 1 & \forall w \in W \tag1 \\ & x_{wt} \leq y_t & \forall t \in T, w \in W \tag2 \\ & \sum_{t \in T} y_{t} \leq 3 & \tag3 \\ & x_{wt} \in \{0,1 \} & \forall w \in W, t \in T \tag4 \\ & y_{t} \in \{0,1 \} & \forall t \in T \tag5 \end{align}
The objective is to minimize overall costs. Constraint (1) assures that each worker is assigned to exactly one task. Constraint (2) assures that the binary variable $y$ is set to 1 if a worker is assigned to it. Constraint (3) assures that no more than 3 tasks are performed.
