Is there a name for this variation of the generalized assignment problem?

Question

All the input variables are positive float (x > 0). We have $M$ agents with limited amount of time $t_1,\dots,t_M$, $N$ tasks $task_1,\dots,task_N$ associated with duration $d_1,\dots, d_N$. Cost for assigning agent $i$ to task $j$ is $c_{ij}$. Time assigning agent $i$ to task $j$ is $x_{ij}$.

We define task as satisfied if the sum of of time allocated to it, by the agents, equals to its duration (binary value): $$SAT(task_j) = 1 \iff d_j=\sum_{i=1}^Mx_{ij}$$

We want to find the $x_{ij}$ that get the maximum number of satisfied tasks while minimizing the cost: $$MIN\sum_{j=1}^N \sum_{i=1}^Mc_{ij}x_{ij}$$ While $$\sum_{j=1}^N \left(SAT(task_j)\right) = MAX-SATISFIED$$

The main idea is to find the solution with lowest cost in the set of solutions with maximal number of satisfied tasks (The satisfied tasks is the most important objective).

Is there a name for this variation of the assignment problem? Also is there an known efficient algorithm?

Answer 1

It's similar to knapsack problem. I am referring to wiki links here from here you can refer to other additional academic papers. Also check this general wiki as well on general assignment problem.
Algorithms will be what most solvers will use for MIP (branch-bound or branch-cut, dynamic column generation). You can also use dynamic programming but search space may be pretty large.

Modern solvers (like Gurobi) will have conditional/indicator constraints and under-the-hood will linearize these.

As for SAT$(t_j$) you can use @RobPratt's formulation from here.

Define 3 binary variables $ y_j^+,y_j,y_j^-$ for each of the tasks.
Then apply constraints
$ Ly_j^- + (d_j+\epsilon)y_j^+ + d_j y_j \le \sum_i x_{ij} \le (d_j - \epsilon)y_j^- + d_jy_j + Yy_j^+$
$ y_j^- + y_j + y_j^+ = 1 \quad \forall j$
where $ U,L$ could be max & min for $ d_j$ & $0 \le \epsilon$ is very small number

Then in the objective use $ \sum_jy_j$ instead of SAT.
You can also assign priority values to the separate objectives. Solvers like Gurobi provide multiple ways to prioritize objectives.

Answer 2

The problem sounds like a parallel resource scheduling problem with preemption. One of the efficient way to solve the problem (as an LP) is to define that as a bipartite graph in which the first group is related to the agents with the limited capacity and the second group is referred to the tasks with their associated duration. Now, each task can be connected to each agents to ensure allowing preemption and already satisfying the duration of each task. In this way the decision variable $x_{n,m}$ is a fractional duration of the processing tasks on the agents. Also, another constraint would be something like a knapsack one to capture each agent capacity. The first objective function is to minimize the assignment costs. Again, by this way, you can achieve the optimal allocation of the tasks on the agents with the minimum cost. You can already define other objective functions to capture what you want. E.g. minimizing the total duration of the tasks processing on the agents. B.T.W this problem has a limitation when the total duration of the tasks being greater than the agents capacity. In this situation you will need to define an auxiliary variable with an appropriate penalties in the objective function to capture the capacity violations.

I tried solving the problem by the following data:

agents = [m1, ..., m4];
tasks  = [n1, ..., n6];
taskduration(n) = [
n1 10,
n2 15,
n3 08,
n4 12,
n5 10,
n6 05
];
agentcapacity = [
m1 20,
m2 30,
m3 10,
m4 20
];
cost:
        m1          m2          m3          m4
n1      25.000      46.000      37.000      29.000
n2      29.000      26.000      30.000      46.000
n3      22.000      35.000      50.000      37.000
n4      50.000      43.000      24.000      39.000
n5      24.000      27.000      40.000      33.000
n6      31.000      30.000      24.000      24.000

and the solution would be:

The first objective: totalprocessing 23.000
The second objective: costs: 1541.00
VARIABLE x.L

            m1          m2          m3          m4
n1      10.000
n2                  15.000
n3       8.000
n4                              10.000       2.000
n5       2.000       8.000
n6                                           5.000

Answer 3

This sounds like a lexicographic optimization problem with two objectives: "maximize the number of tasks satisfied" is the high-priority objective while "minimize the cost" is the low priority objective. You may formulate the problem as a maximum-covering-like problem: Introduce binary variables $y_j$ for each task taking the value 1 iff task $j$ is satisfied. Also, rename the variables $x_{ij}$ to be the proportion of task $j$ assigned to agent $i$. The the problem becomes \begin{align} \text{lex}\max\ &\{\sum_{j=1}^Ny_j,-\sum_{i=1}^M\sum_{j=1}^Nd_jc_{ij}x_{ij}\}\\ \text{s.t.:}\ & \sum_{i=1}^Mx_{ij}\geq y_j,&&\forall j=1,...,N\\ \ & \sum_{j=1}^Nd_jx_{ij}\leq T_i,&&\forall i=1,...,M\\ \ & y_j\in\{0,1\},&&\forall j=1,...,m \end{align} You can solve this by scalarizing the objectives into $\max \mu\sum_{j=1}^Ny_j-\sum_{i=1}^M\sum_{j=1}^Nd_jc_{ij}x_{ij}$ where $\mu$ is a large constant. This will often lead to numerical problems, however, to include such a large constant in the objective. A more practical approach is to first maximize $\sum_{j=1}^Ny_j$. Then add a constraint of the form $\sum_{j=1}^Ny_j\geq z^*$ where $z^*$ is the number of satisfied tasks found while maximising. Next, you change the objective function to $\min\sum_{i=1}^M\sum_{j=1}^Nd_jc_{ij}x_{ij}$ and solve this new ILP with the added constraint.