# How to solve assignment problem with type constraints?

There are $$n$$ jobs and $$m$$ machines. Assigning job $$i$$ to machine $$j$$ yields a profit of $$c_{ij}$$. Each job has a type $$t_i$$. Machine $$j$$ can take on up to $$a_j$$ jobs, but the number of job types must not exceed $$b_j$$. How should the jobs be assigned to the machines to maximize profit?

For example, in this case, it is optimal to assign job 1 to machine 1 and jobs 2 and 3 to machine 2.

This problem can be solved with an integer programming solver, but I would like to know of any algorithms or related papers that solve this problem.

• There are thousands of papers on this topic. Just run a search on Google Scholar for job-shop. Apr 21, 2022 at 13:52
• @Brannon where do you see a Job Shop here? For me, it looks like a variant of a Generalized Assignment or a Multiple Knapsack Problem Apr 21, 2022 at 14:49
• @sakuya, would you please, is it a homework problem? Apr 21, 2022 at 14:57
• @Brannon There are many papers on assignment problems, but I have not been able to find one that imposes a constraint on the number of types of job that can be assigned. I would like to know if there is a standard name or algorithm for this problem. Apr 22, 2022 at 3:01

Some articles dealing with constraints limiting the number of job types assigned to a given machine can be found with the keywords "class constrained" or "color constraints":

• "The multiple knapsack problem with color constraints" (Dawande et Kalagnanam, 1998) PDF
• "On Two Class-Constrained Versions of the Multiple Knapsack Problem" (Shachnai et Tamir, 2001) DOI
• "A Column-Generation Approach to the Multiple Knapsack Problem with Color Constraints" (Forrest et al., 2006) DOI (only two types on each machine)
• "The class constrained bin packing problem with applications to video-on-demand" (Xavier et Miyazawa, 2008) DOI
• "Class constrained bin packing revisited" (Epstein et al., 2010) DOI
• "A special case of Variable-Sized Bin Packing Problem with Color Constraints" (Crévits et al., 2019) DOI (only two types on each machine)

I'm not aware of any article studying the exact same problem as the one you describe.

I think your problem looks like a Multi-resource Generalized Assignment Problem. Here are two papers that describe it: Garvish and Pirkul (1991) and Mazzola and Wilcox (2001).

The amount of jobs $$a_j$$ that can be performed by a machine can be seen as available resource. And the amount of job types $$b_j$$ can also be seen as available resource. A job might consume both.

Adapting to their notation, you would have two resources, $$|K|=2$$. Then, machine $$j$$ consumes $$a_{ijk}$$ of resource $$k$$ when performing job $$i$$, and has $$b_{jk}$$ of resource $$k$$ available.

• Thank you for your answer. $b_j$ is a constraint on the number of different job types that can be assigned. That is, $b_j$ is consumed only when machine j is assigned a type of job that has never been assigned to it before. In the example above, 1. Assume that machine 2 is initially assigned no jobs. $a_2 = 2$, $b_2 = 1$. 2. Assign job 2 to machine 2. $a_2 = 1$, $b_2 = 0$. 3. Assign job 3 to machine 2. At this point, $b_2$ is already 0, but since a job of type B has already been assigned, it can be assigned to machine 2 without consuming $b_2$. As a result, $a_2 = 0$, $b_2 = 0$. Apr 22, 2022 at 5:36
• Oh, I see. I didn't realize that subsequent jobs of the same type become "free". Apr 22, 2022 at 5:54