1
$\begingroup$

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?

enter image description here

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ There are thousands of papers on this topic. Just run a search on Google Scholar for job-shop. $\endgroup$
    – Brannon
    Apr 21, 2022 at 13:52
  • 2
    $\begingroup$ @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 $\endgroup$
    – fontanf
    Apr 21, 2022 at 14:49
  • $\begingroup$ @sakuya, would you please, is it a homework problem? $\endgroup$
    – A.Omidi
    Apr 21, 2022 at 14:57
  • $\begingroup$ @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. $\endgroup$
    – user5966
    Apr 22, 2022 at 3:01

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$
    – user5966
    Apr 22, 2022 at 5:36
  • $\begingroup$ Oh, I see. I didn't realize that subsequent jobs of the same type become "free". $\endgroup$
    – Nara Begnini
    Apr 22, 2022 at 5:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.