# What is the appropriate algorithm for bipartite matching with constraints?

I have a problem that is a bit complex, and I don't know what method/model I should use to express it (much less solve it).

Let's say we have a lot of employees and a few jobs to be done. Each employee ranks the jobs they want most.

Easy. Bipartite matching, with weighted edges. Or Hungarian algorithm. Right?

Now things become more complicated. Instead of one job each day, an employee has to do 4 jobs in a day. The same single ranking they gave will be taken into account for the other 3 jobs they receive (no repetitions).

Since each employee must have 4 jobs, and there are many more employees than jobs, each job can have multiple people assigned to it for each period.

More complicated: each job has a maximum of employees it can accommodate (different for each job).

More complicated. Now jobs are skill based. Each employee has not only a preference ranking, but a skill class they belong to, low, med, or high. So each job has a phase for the low-skilled, the medium-skilled, and the high-skilled, with a skill level repeated for the fourth phase, as needed.

The objective is to make sure every employee ends up with the most of their highest ranked choices.

Does there exist some framework for solving such problems? Is there a way to adapt bipartite matching for all of these constraints?

• I think what you need is many-to-many matching. The answer by D.W. here: cs.stackexchange.com/q/161149/1342 shows how to solve such problems efficiently, using flow networks. Jul 18, 2023 at 11:21