The classical assignment problem deals with assigning N agents to M jobs while minimising the time spent on each job. The problem has a solution in polynomial time, called the Hungarian algorithm, which has a cost matrix C as an input and returns the optimal list of assignments.
In my case, I got the same problem, but with one difference. Each job requires a pair of two works to be assigned to it. The number of agents are chosen such that N is an even number in order for this to be possible.
I am fairly new to assignment problem related questions, so I am not sure how to tackle this problem.
How would one solve this problem?
Edit: Note that a agent can be assigned to at most one task, it can not be assigned to multiple tasks. One can assume M(jobs) = 2N(agents) and otherwise introduce dummy agent or tasks.
Since there are twice as many tasks as workers, you need to double the number of tasks. Since each task requires two workers, you can double the number of tasks by duplicating each of them (ex. Task 1 becomes Task 1a and Task 1b). You would then have an equal number of workers and tasks, and after running the Hungarian Algorithm you can find your pairs of workers by looking at who was assigned to each split of each task.