11
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Do you mean objective function: $\sum \limits_j f(\sum \limits_ix_{i,j})$ with f beeing your cost function? $\endgroup$
    – Georgios
    Jul 9, 2019 at 13:48
  • $\begingroup$ 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. $\endgroup$
    – Daniel Duque
    Jul 9, 2019 at 15:02
  • $\begingroup$ Georgios, I think that looks like what it could be. Have you see any methods of implementing it so that it can be solved? $\endgroup$
    – David
    Jul 9, 2019 at 16:34
  • $\begingroup$ 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! $\endgroup$
    – David
    Jul 9, 2019 at 16:35

2 Answers 2

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – David
    Jul 9, 2019 at 23:58
  • $\begingroup$ 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). $\endgroup$
    – prubin ♦
    Jul 10, 2019 at 20:58
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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)? $\endgroup$
    – David
    Jul 10, 2019 at 0:36
  • $\begingroup$ 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? $\endgroup$
    – LarrySnyder610
    Jul 10, 2019 at 2:08

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.