Assign jobs to least people with multiple job constraints

Question

Assume I have an infinite number of staff/supply. I have a table of how much time in hours needs to be spent on certain tasks:

Task	Demand
A	0.75
B	0.8
C	0.65
D	0.7
E	0.6
F	0.65

And the tasks can either be assigned to staff separately - i.e. 1 person does A (thus contributing 1 towards the demand for task A), or B, C, D, E, F - or they can be assigned in certain combinations, specified below:

Combination
A
B
C
D
E
F
A; B; C
A; B
B; C
A; C
D; E
D; F

If I assign a task like (A; B; C), there is no rule as to how much time must be spent on each task, just as long as the total time spent is 1. For example, in assigning task (A; B; C) to somebody, I may tell them to do 0.75hrs of A, 0.15hrs of B, and 0.1hrs of C, or I may tell them to do 0.5hrs of A, 0.3hrs of B, and 0.2hrs of C.

If it was the case that the demand for A+B+C <=1, D+E <= 1 and D+F <=1 then this would be a simple linear optimisation problem, solved here https://stackoverflow.com/questions/72982423/task-assignment-to-least-possible-people/72983289?noredirect=1#comment128972545_72983289.

But it is not. And I cannot simply ignore the combinations for which this is not true and proceed with linear optimisation, because then only the one-task-to-one-person assignments (e.g. 1 person on A, 1 on B, etc.) are permissible. Hence I would end up assigning 6 people to meet the demand, whereas I ought to have given, for example, (A; B; C) to 2 people, A to 1 person, (D; E) to 1 person and (D; F) to 1 person, making up 5 < 6 people in total.

I'm very confused as to how to optimise this. I have tried to find a way around it via for loops but things get very messy and I still don't get any closer to a problem.

Answer 1

Let $I$ be the set of available persons (you can set this value to an upper bound, e.g. 6 in your case),and $J$ be the set of jobs. $S$ is the set of shifts. $R_j$ is the amount of hours a job needs to be finished. The parameter $Y_{sj}$ is $1$ if shift $s$ contains job $j$.

DECISION VARIABLES

$x_{ijs}$ Amount of hours person $i\in I$ spend on job $j \in J$ in shift $s \in S$

$u_{is}$ Binary variable: $1$ if person $i \in I$ is working in shift $s \in S$ and $0$ if not.

Linear Program \begin{align} \ & \min z = \sum_{i \in I}\sum_{s \in S} u_{is} \; \\ \textit{S.t.}\\ \\ & \sum_{j \in J}\sum_{s \in S} x_{ijs} \leq 1 & \forall i \in I \tag1\\ & \sum_{j \in J} x_{ijs} \leq u_{is} & \forall s \in S ,i \in I \tag2\\ & \sum_{s \in S} u_{is} \leq 1 & \forall i \in I \tag3\\ & \sum_{i \in I}\sum_{s \in S} x_{ijs} \geq R_j & \forall j \in J \tag4\\ & \sum_{i \in I} x_{ijs} \leq Y_{sj} & \forall j \in J, s \in S \tag5\\ & x_{ijs} \geq 0 & \forall i \in I, j \in J, s \in S \tag6\\ & u_{is} \in \{0,1 \} & \forall i \in I, s \in S \tag7 \end{align}

The objective is to limit the number of persons working. Constraint (1) states that every person cannot work more than one hour (delete it if this constraint is not needed). Constraint (2) states that if any job is performed by person $i$ in shift $s$, then the person must be assigned to that shift, i.e. $u_{is}$ must be 1 (multiply $u_{is}$ by big constant M in case a person can work more than one hour). Constraint (3) states that each person is assigned to a maximum of one shift. Constraint (4) states that the requirement of a job in terms of working hours needs to be met. Constraint (5) states that if a job is not in a shift, i.e. $Y_{sj}=0$, no person can be assigned to fulfill this shift/job combination.

Answer 2

There are two things that should be taken into account in your problem. First, the number of staff/resources, and the second the compilation time of all tasks. (The second one already can be changed to other objects, but in this case, I am assuming this). The mentioned problem can be formulated as a parallel machine scheduling problem for which the preemption would be allowed.

\begin{align} \ & \text{Minimize} \quad z = C_{max} \; \\ & \textit{S.t.}\\ \\ & \sum_{i \in I} x_{ij} = 1 & \forall j \in J \tag1\\ & \sum_{i \in I} p_{j}x_{ij} \leq C_{max} & \forall j \in J \tag2\\ & \sum_{j \in J} p_{j}x_{ij} \leq C_{max} & \forall i \in I \tag3\\ & x_{ij} \geq 0 & \forall i \in I, j \in J \tag4\\ \end{align}

The variable $x_{ij}$ represents the total time task $j$ spends on resource $i$. $p_{j}$ is the processing time of task $j$ and $C_{max}$ is Makespan. In this case, you can analyze how many resources are actually needed to minimize $C_{max}$ to make the optimal sequence.

For example, with the above data and assuming $3$ resources in the first scenario, the Makespan would be $83$ and within $5$ resources it is around $50$. Also, the optimal sequence for the first scenario is as follows:

----     41 VARIABLE x.L  the total time task j spends on resource i

            j1          j2          j3          j4          j5          j6

m1                   0.083                   0.095       1.000       1.000
m2                   0.917       1.000
m3       1.000                               0.905