Task Quota Assignment¶

Definition¶

In task quota assignment, each task is assigned to exactly one agent and agent $i$ must receive exactly $q_i$ tasks. For binary assignment variables $x_{ij}$ and times or costs $c_{ij}$ , the model is

\min\sum_i\sum_jc_{ij}x_{ij},\qquad \sum_ix_{ij}=1,\qquad \sum_jx_{ij}=q_i,\qquad x_{ij}\in\{0,1\}.

The quotas sum to the number of tasks.

Interpretation¶

Task quota assignment divides tasks among agents when each agent has a fixed workload: every task is done by exactly one agent, and agent $i$ does exactly $q_i$ tasks. Among all divisions that respect these numbers, the objective picks one with the least total cost or time.

Two bipartite diagrams: agent A1 with a quota of two tasks and agent A2 with one, and the same problem with A1 split into two identical copies, giving a one-to-one assignment.

In the left diagram $A_1$ has quota $q_1=2$ and $A_2$ has $q_2=1$ $1$ . The thick edges give $A_1$ the tasks $T_1,T_2$ and $A_2$ the task $T_3$ : each task has one thick edge, and each agent as many as its quota. The right diagram replaces $A_1$ by two copies $A_1'$ and $A_1''$ with the same costs; each copy takes exactly one task, so the quota model becomes a one-to-one pairing.

The model is a binary integer program with two families of equations. For each task $j$ , $\displaystyle \sum_ix_{ij}=1$ says the task is done once; for each agent $i$ , $\displaystyle \sum_jx_{ij}=q_i$ fixes the workload. Adding the task equations and adding the agent equations both count all assignments, so the model is feasible only when the quotas add up to the number of tasks.

The objective adds up all task times, so it minimizes total effort, not the time at which the last person finishes. With every quota equal to $1$ the model becomes the one-to-one case that returns later as the assignment problem, and the copying trick reduces the quota version to it.

Key Results¶

In the later Hungarian-method treatment, duplicate each agent row $q_i$ times to represent its available task slots.
Each task remains assigned exactly once.
Minimizing summed execution time is different from minimizing the latest completion time.

Examples¶

Eve receives marketing and dishwashing; Steven receives cooking and laundry, totalling 18.4 hours.
In week 5 practice 3, two identical rows per machine represent its two required jobs.

Prerequisites¶

Binary Integer Program

Sources¶

OR Modelling · Week 2

Keywords: Household activities Symbols: element of, sum

Last updated: 22 October 2026 19:04