Linearization of a scheduling objective function

Question

I am trying to maximize the workload per employee.

An example:

• $e$ the index of an employee
• $j$ the index of a project
• decision variable: $x_{e,j} \in \mathbb{Z}$ and $0 \leq x_{e,j} \leq 100$ deciding with how much percent an employee may work on a project. (Yes it is possible that an employee works on a project with 40%. The remaining 60% should get covered from someone else and all projects should get covered but this is not a part of this problem.)
• decision variable: $y_e \in \{0,1\}$ deciding if employee e is working

I had in mind something like the following as a part of the objective function $$ \max\sum\limits_{e,j}\frac{x_{e,j}}{y_e}$$

The problem is that this is not linear.

Example: $\frac{160}{3} < \frac{160}{2}$ thus 2 employees whould be preferred instead of 3.

Note:

The following constraint has to hold,

$$ \sum\limits_e x_{e,j} = 1 \ \ \forall \ \ j $$

implying that all projects have to get covered.

Answer 1

You can linearize the objective function, but at the cost of more binary variables and big-M type constraints.

Let's assume that we know a priori that the number of employees used will be between 0 (or maybe 1) and $N$. Introduce binary variables $z_0, \dots, z_N$ with the constraint $$\sum_{k=0}^N z_k = 1.$$The $z$ variables will determine how many employees are being used, via the constraint $$\sum_e y_e = \sum_k kz_k.$$

Next, introduce a continuous variable $W$ representing the objective value (to be maximized) and continuous variables $S_0, \dots, S_k$, along with the linear constraints $$S_k =\frac{1}{k}\sum_{e,j} x_{e,j}\quad \forall k$$(so that $S_k$ is the objective value you want if $k$ employees are used) along with the constraints $$S_k - \underline{M}_k (1-z_k) \le W \le S_k + \overline{M}_k (1-z_k)\quad \forall k,$$where $\underline{M}_k$ and $\overline{M}_k$ are sufficiently large constants (the sizes of which, as the notation suggests, may vary as $k$ varies). This ensures that $W$, the thing you are maximizing, equals $S_k$ if and only if $z_k=1$ (i.e., you are using $k$ workers).

Answer 2

Another approach to model the objective function could be the following where $M$ is a big number that forces the model to choose as few as possible numbers of operators.

$$\max \sum_{e,j} x_{e,j}-M\times \sum_e y_e$$

Answer 3

Suppose that, the following non-linear objective arises (MAX/MIN): \begin{equation} \max\frac{\sum\limits_{j} a_{j} x_{j}}{\sum\limits_{j} b_{j} x_{j}} \end{equation}

1) Replace the expression $\dfrac{1}{\sum\limits_{j} b_{j} x_{j}}$ by a variable $t$.

2) Represent the products $x_{j} t$ by variables $w_{j}$. The objective now becomes:

\begin{equation} \max \sum_{j} a_{j} w_{j}. \end{equation} Introduce a constraint: \begin{equation} \sum_{j} b_{j} w_{j}=1 \end{equation} in order to satisfy condition 1.

Convert the original constraints of the form: \begin{align} \sum_{j} d_{j} x_{j} &\leqq e \\ \sum_{j} d_{j} w_{j}-e t &\leqq 0 \end{align} It must be pointed out that this transformation is only valid if the denominator $\sum\limits_{j} b_{j} x_{j}$ is always of the same sign and non-zero. If necessary (and it is valid), an extra constraint must be introduced to ensure this. If $\sum\limits_{j} b_{j} x_{j}$ always be negative the directions of the inequalities in the constraints above must, of course, be reversed.

Reference: Model Building in Mathematical Programming