Task Selection Problem

Question

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.

Answer 1

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.