# Assignment Problem with Decreasing Costs

Problem: I have $$i$$ jobs that I can assign to $$j$$ workers. Each job has a cost. Each worker can perform up to an arbitrary max number of jobs. However, there is a cost efficiency for each job that is assigned to the worker. For example, if two jobs are assigned then the cost of the jobs is multiplied by $$0.95$$. Three jobs, by $$0.90$$. This function can also be linear.

Are there any examples of this in literature? I've been able to implement this if the multiplicative cost function is a step function. I'm not exactly sure how to proceed if the value that I multiply against the number of jobs is a function.

• Do you mean objective function: $\sum \limits_j f(\sum \limits_ix_{i,j})$ with f beeing your cost function? Jul 9 '19 at 13:48
• This sounds a lot like the set-union knapsack problem. Maybe there are ideas in that problem that help you to define the función because in the end, that fact that the number of jobs is finite, allows you have the value of the function for all bundles. Jul 9 '19 at 15:02
• Georgios, I think that looks like what it could be. Have you see any methods of implementing it so that it can be solved? Jul 9 '19 at 16:34
• Daniel, the number of jobs and combinations may start to get extremely large so I'm not sure if recomputing it will work or not. I will look into it though! Jul 9 '19 at 16:35

Here's a formulation that may be rather large but I think is correct.

### Indices:

• $$i=$$ job;

• $$j=$$ worker;

• $$k=$$ discount factor;

• $$n=$$ job count for a worker

### Parameters:

• $$c_{i}=$$ undiscounted cost of job $$i$$;

• $$d_{k}=$$ discount factor for doing $$k$$ jobs ($$d_{1}=1.0,d_{2}=0.95,\dots$$);

• $$N=$$ total number of jobs to be assigned

### Binary variables:

• $$x_{ijk}=1$$ if job $$i$$ is assigned to worker $$j$$ at discount rate $$k$$;

• $$y_{jn}=1$$ if worker $$j$$ gets $$n$$ jobs

### Continuous variables:

• $$z_{i}=$$ ultimate cost of job $$i$$

## Objective function: $$\min\,\sum\limits_{i}z_{i}$$

### Constraints:

• Assign every job once: $$\sum\limits_{j}\sum\limits_{k}x_{ijk}=1\;\forall i$$
• Compute cost of each job: $$z_{i}=\sum\limits_{j}\sum\limits_{k}(d_{k}c_{i})x_{ijk}\ \forall i$$
• Compute $$y$$ variables: $$\sum\limits_{i}\sum\limits_{k}x_{ijk}=y_{j1}+2y_{j2}+\dots+Ny_{jN}\ \forall j$$
• Make sure discounts are earned: $$x_{ijk}\le y_{jk}\ \forall i,j,k$$

If there are limits on how many jobs a worker can take, that's easily incorporated.

• Thank you for the mathematical formulation! This is basically what I have now. Do you think there is a way to do this but with the discount factor being a function of the number of jobs? Or would this make the problem intractable? Jul 9 '19 at 23:58
• In this formulation, the discount factor is a function of the number of jobs (but not of the total time for all the jobs, although I think that is doable with a modification). Jul 10 '19 at 20:58

This reminds me a little of the maximum expected covering location model (MEXCLP) by Daskin (1983). The objective function depends nonlinearly on the number of facilities that cover each customer. Binary decision variables are used to count these assignments, similar to the $$y_{jn}$$ variables in @prubin's answer, and (again like in @prubin's answer), the binary variables are added, with appropriate coefficients, in order to calculate the nonlinear cost.

It's a neat trick, and quite general, basically allowing you to model a nonlinear function of the sum of some binary variables.

• Thank you for that. So what if each job took a certain number of minutes. And the discount rate is based on the sum of the minutes of all the jobs assigned to each worker. For each additional minute the cost decreases by a multiplier of 0.01. Is there anyway to do this without having to create a binary variable for each minute (as this could explode the number of variables)? Jul 10 '19 at 0:36
• I don't think this trick will work in that case -- I agree, you'd need to create a binary variable for each minute. However, if the total cost is a concave function of the number of minutes assigned, then maybe some of the ideas in the paper by Shen, Coullard, and Daskin (2003) might help? Jul 10 '19 at 2:08