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.

@Stradivari I think you are right. I'll just test your suggestion. — Georgios, Oct 14 '19 at 14:38
Check this objective function. You wrote $\frac{x_{e,j}}{y_e}$ but If $y_e=0$ you will have a division by zero. Thus, there is no possible linearization. I guess your objective function is: (maximize workload per employee)
$$\max \frac{\sum_{e}\sum_{j} x_{e,j} }{\sum_{e}y_e}$$

And you should add a constraint to guarantee more than zero employees.

$$\sum_{e}y_e \geq 1$$

This problem needs more constraints yet. Probably, you need to describe constraints for work capacity per employee. — Alexandre Frias, Oct 14 '19 at 18:12
@AlexandreFrias This case will never occur since I already mentioned in the description that all projects $j$ should get fully covered. Thus, a constraint is implicitly implemented and not mentioned here avoiding the case of $\sum\limits_e y_{e} = 0$. — Georgios, Oct 15 '19 at 10:25
@Georgios, $y_e = 0$ for certain index $e$. Thus, your objective function has this problem yet. The term of the summation $\frac{x_{e,j}}{y_e}$ can be undefined. — Alexandre Frias, Oct 15 '19 at 16:11

score 5 · Answer 1 · edited Oct 14 '19 at 19:23

5

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$$

edited Oct 14 '19 at 19:23

ə̷̶̸͇̘̜́̍͗̂̄︣͟

5,412
5
22
55

answered Oct 14 '19 at 15:34

Oguz Toragay

8,652
2
13
41

When the question defines the profits, $d_e$ and $c_{e,j}$, associated to the variables $y_e$ and $x_{e,j}$ I agree with you. But, I do not understand the meaning of this objective function. In this case, what are you maximizing? – Alexandre Frias Oct 14 '19 at 16:29
I feel that in his case maybe $\sum_{e,j} x_{e,j}$ is constant. – Stradivari Oct 14 '19 at 19:59
@Stradivari , maybe $\sum_{e} x_{e,j} =1 \forall j$ but, only Georgios knows that. – Alexandre Frias Oct 15 '19 at 04:40
I want to say " All project $j$ must be completed." – Alexandre Frias Oct 15 '19 at 04:44
@AlexandreFrias yes this is exactly what I meant. I will add that to the description. – Georgios Oct 15 '19 at 10:30
This is brilliant! Short yet effective to implement. – Georgios Oct 15 '19 at 10:41

score 4 · Accepted Answer · answered Oct 14 '19 at 21:06

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).

score 4 · Answer 3 · edited Oct 15 '19 at 07:43

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

Linearization of a scheduling objective function

3 Answers3