Suppose, there exists a scheduling problem $S$, in this case a single resource, with the following descriptions:
$$ \text{conv(S)} = \{x \in \mathbb{R}^n \ | \ \forall \lambda_{i} \in \mathbb{R}^{n+}, \ x = \sum_{i=1}^{|s|} \lambda_{i} S_{i}, \ \sum_{i=1}^{|s|} \lambda_{i} = 1 \} $$
where conv(s) is the convex hull of $S$. Now, the set of feasible schedules for a set of jobs $J$ with release dates would be:
$$ S^{SRR} = \{S \in \mathbb{R}^J \ | \ S_{j} \geq r_{j}, \ (S_{i} \geq S_{j} + l_{i,j}) \lor (S_{j} \geq S_{i} + l_{j,i}), \ \forall i,j \in J: i \not = j \} $$
In such a case, Prof. Balas derived facet-defining inequalities for a subset of jobs $K \subseteq J$ induces also a facet for $J$. Now, the following inequality is a nontrivial facet inducing inequality for $P( \{ i,j\} )$, if and only if $(-d_{j,i} \lt L_{j} - L_{i} \lt d_{i,j})$:
$$ (d_{i,j} + L_i − L_j )S_i + (d_{j,i} + L_j − L_i )S_j \geq d_{i,j} d_{j,i} + L_i d_{j,i} + L_j d_{i,j} $$
where, $d_{i,j}$ is a processing time, and $L_{j}$ is a release date. In some cases, I have seen the above inequality has been written as:
$$ (l_{i,j} + r_i − r_j )S_i + (l_{j,i} + r_j − r_i )S_j \geq d_{i,j} d_{j,i} + L_i d_{j,i} + L_j d_{i,j} $$
Now, my questions are:
- If this is a valid inequality for such a problem, is it possible to use that directly in the above-mentioned set of feasible schedules? If so, is there any paper or other references to illustrate this?
- Why, in some cases, the parameters are different in the LHS and RHS?
- Is it possible to apply this inequality in the general form? I mean e.g. in the parallel resource schedule?
ON THE FACIAL STRUCTURE OF SCHEDULING POLYHEDRA - Egon BALAS