3
$\begingroup$

In this example, we have a group of students that each needs to be paired with a teacher. Each student has a different number of questions to ask the teacher, and each student-teacher pairing has a different difficulty for their interactions.

The workload for a teacher for a student-teacher pairing is given by the number of questions that the student has $Q_s$ multiplied by the interaction difficulty $\beta_{s,t}$

$$ Q_s(\beta_{s,t}) $$

How can we define the LP model for evenly distributing the workload across the teachers?

Tried an objective function that minimizes

$$ \sum_{s=1}^{S} \sum_{t=1}^{T} Q_s(\beta_{s,t}) X_{s,t} \\ $$

where $Q_s$ is the number of questions a student $s$ has,

$\beta_{s,t}$ is the difficulty of interaction between student $s$ and teacher $t$,

$X_{s,t}$ is a binary variable that shows whether student $s$ is assigned to teacher $t$.

However, the results does not suggest that the workload for each teacher $\sum_{s=1}^{S} Q_s(\beta_{s,t}) X_{s,t}$ is evenly distributed.

Is there a better objective function to achieve this?

Note: I'm doing this in Python with PuLP and Scipy

$\endgroup$
6
  • $\begingroup$ I am not aware of how the rest of the model is formulated, but for uniform dispatching workload one possible way would be trying $Max \quad z = Min(\sum(...))$ as the objective function. Do you try that? $\endgroup$
    – A.Omidi
    Mar 20, 2022 at 10:55
  • $\begingroup$ @A.Omidi maximin is one approach for balancing, but here I think it could artificially inflate the overall workload. I recommend minimax instead. $\endgroup$
    – RobPratt
    Mar 20, 2022 at 14:03
  • $\begingroup$ @RobPratt, thanks for your comments Dr Pratt. Would you say please, what you mean by artificially inflate? As a practical sense, if one would like to maximizing resource utilization, maximin would be interesting. Actually, as you mentioned too, there are other ways to do that. $\endgroup$
    – A.Omidi
    Mar 20, 2022 at 19:23
  • 1
    $\begingroup$ @A.Omidi By "artificially inflate" I mean that the maximin objective encourages making the minimum workload large, which tends to make the total workload large. $\endgroup$
    – RobPratt
    Mar 20, 2022 at 19:28
  • 1
    $\begingroup$ @A.Omidi After either minimax or maximin as primary objective, you might consider introducing an objective cut and using min total as a secondary objective. Or reverse the roles of primary and secondary. $\endgroup$
    – RobPratt
    Mar 20, 2022 at 20:00

1 Answer 1

3
$\begingroup$

There are a number of ways to approach this. One would be to minimize the sum of absolute deviations from the overall average load. To do this, add variables $L_t \ge 0$ and $d_t$ ($t=1,\dots,T$) plus one more variable $\bar{L}\ge 0.$ New constraints are $$L_t = \sum_{s=1}^S \beta_{s,t}Q_sX_{s,t}\quad \forall t\in \lbrace1,\dots,T\rbrace$$ (making $L_t$ the load on teacher $t$), $$\bar{L}=\frac{1}{T}\sum_{t=1}^T L_t$$ (making $\bar{L}$ the average load across all teachers), and $$d_t \ge L_t - \bar{L}\quad \forall t$$$$d_t \ge \bar{L} - L_t\quad \forall t.$$The last two constraints ensure that $d_t \ge \vert L_t - \bar{L} \vert.$ Now minimize $\sum_t d_t$ to get a solution that minimizes the sum of absolute deviations from mean load.

Other possibilities include minimizing the sum of squared deviations (i.e., use $L_2$ norm instead of $L_1$ norm) or the single biggest deviation from mean ($L_\infty$ norm). It is worth noting that the solution using any of these objectives (or others proposed in comments) may be inefficient in that the total time spent by all teachers might be higher than necessary, in order to get closer to parity.

$\endgroup$
2
  • $\begingroup$ Thanks! Concerning your final comment, is there a way to adjust the trade-offs between getting better workload parity and minimizing total time spent? $\endgroup$ Mar 20, 2022 at 23:52
  • $\begingroup$ You can treat it as a bi-objective problem, where one objective is minimizing disparity (however you measure that) and the other is minimize total time. There are quite a few approaches to multiobjective problems. One would be to minimize a weighted combination of the two measures (where you would need to come up with weights that made sense to you). Another would be to generate a set of nondominated ("Pareto efficient") solutions, show them to the decision maker, and let them pick. A solution is nondominated if no other solution is better on both dimensions. Yet another is goal programming. $\endgroup$
    – prubin
    Mar 21, 2022 at 0:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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