0
$\begingroup$

I am trying to distribute 15 tasks to two people. Each task can only be assigned to one person and each person has a time budget.

I want to express this problem as a linear program (ultimately in the standard linear form) so that I can write a computer program to solve it. \begin{array}{|c|c|c|c|c|} \hline Workers& Task 1 & Task2 & Task3 & ... & Time budget \\ \hline Jack& 0.5& 0.25& 0.25 & & 9\\ \hline John& 0.75& 1.0 &0.75 & & 8\\ \hline \end{array}

I can find plenty of examples how to do it without a budget constraint. Without it, it is an Assignment Problem that can be solved with The Hungarian Method.

$\endgroup$
  • $\begingroup$ or.stackexchange.com $\endgroup$ – Rodrigo de Azevedo Nov 6 '19 at 8:50
  • $\begingroup$ @RodrigodeAzevedo : Do you think or.stackexchange.com should handle all questions with the "operations-research" tag ? $\endgroup$ – Kuifje Nov 6 '19 at 10:22
  • $\begingroup$ @Kuifje I merely think that the OP should be aware of the existence of OR SE. Naturally, people over there are much more enthusiastic about it than people here. $\endgroup$ – Rodrigo de Azevedo Nov 6 '19 at 10:25
  • $\begingroup$ The question is tagged "linear-programming", but I think it will require integer linear programming. $\endgroup$ – prubin Nov 6 '19 at 23:19
  • $\begingroup$ If you want help have to give a reply to the comments/answers. $\endgroup$ – callculus Nov 7 '19 at 16:14
0
$\begingroup$

Hints: Let binary decision variable $x_{i,j}$ indicate whether person $i$ is assigned task $j$. Now you need a constraint that each task gets assigned to exactly one person, as well as a time budget constraint for each person.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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