2
$\begingroup$

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.

$\endgroup$

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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
$\endgroup$
2
  • $\begingroup$ The question calls for minimizing the number of people assigned, not the makespan. $\endgroup$
    – prubin
    Aug 6 at 15:24
  • $\begingroup$ @prubin, dear prof. Rubin the questioner wants to assign the tasks to the staff within a combination of the fractional sequence. Also, for each task, there is a corresponding processing time that allowed being a fraction. Assigning the task to the staff without considering the optimal sequence may cause a longer execution time. The above formulation allows playing around with the number of staff and execution time w.r.t the optimal sequence. Also, I pointed out one of the objective that can be used is Makespan and one can actually pick another. $\endgroup$
    – A.Omidi
    Aug 6 at 19:05

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.