LP Objective function for distributing workload

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

• 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? Mar 20 at 10:55
• @A.Omidi maximin is one approach for balancing, but here I think it could artificially inflate the overall workload. I recommend minimax instead. Mar 20 at 14:03
• @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. Mar 20 at 19:23
• @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. Mar 20 at 19:28
• @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. Mar 20 at 20:00

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.