Scheduling Optimization Problem

Question

I want to solve below optimization problem. This is scheduling problem where I seek to complete as many of the jobs $\xi_l$ (objective function and constraint 1), with $T_C$ being the last time until I can finish them (constraint 2). Constraint 3 to disallow any parallel activities. Also, each job can wait $t_l$ to start in scheduling (waiting time that it's maximum is $T_c$). $T_{r,l}$ is time that job $l$ is registered, and $T_{e,l}$ is time that job $l$ is completed (if $\xi_l=1$, and $t_l=0$). The optimization problem is:

\begin{align} \underset{t_l,\xi_l}{\max}\quad& \sum_{l=1}^{L}\xi_l\\ \text{s.t.}\quad&\xi_l \in \{0, 1\}\\ &\xi_l t_l\leq T_c~~~~~~\forall l,\\ &\begin{cases}T_{r,l}+t_l\geq (\xi_l+\xi_{l^\prime}-1)(T_{e,l^\prime}+t_{l^\prime})\\\hspace{3cm}\text{or}\\T_{r,l^\prime}+t_{l^\prime}\geq (\xi_l+\xi_{l^\prime}-1)(T_{e,l}+t_{l})\quad\forall l\neq l^\prime\end{cases} \end{align}

How can I solve above optimization problem and find closed form for $\xi_l$ and $t_l$ (as function of $T_c$, $L$, $T_{r,l}$, $T_{e,l}$)?, OR how can I find an algorithm to solve this optimization problem?

To have an idea for the general solution for $\xi_l$ and $t_l$ in optimized solution, I solve this problem for two job ($L=2$), by using Lagrangian method (I can't import one of OR constraints): \begin{align} L= \xi_1+\xi_2+\lambda_1(T_c-\xi_1t_1)+\lambda_2(T_c-\xi_2t_2)+\alpha_1(1-\xi_1)+\alpha_2(1-\xi_2)\\+\gamma_1t_1+\gamma_2t_2+\beta(T_{r,2}+t_2-(\xi_1+\xi_2-1)(T_{e,1}+t_1)) \end{align} where $L=L(\xi_1,t_1,\xi_2,t_2,\lambda_1,\lambda_2,\alpha_1,\alpha_2,\gamma_1,\gamma_2,\beta)$.

Then, $\frac{\partial L}{\partial ...}$, I have these equations: \begin{align} &1-\lambda_1 t_1 -\alpha_1-\beta(T_{e,1}+t_1) = 0\\ &1-\lambda_2 t_2 -\alpha_2-\beta(T_{e,1}+t_1) = 0\\ &-\xi_1 \lambda_1-\beta\xi_1-\beta-\xi_2+\gamma_1+\beta=0\\ &-\lambda_2\xi_2+\gamma_2+\beta=0\\ &\xi_1 = 1, \xi_2=1\\ &t_1 = 0, t_2 = 0\\ &\xi_1t_1= T_c\\ &\xi_2t_2= T_c\\ &T_{r,2}+t_2= (\xi_1+\xi_{2}-1)(T_{e,1}+t_{1}) \end{align}

How can I continue this to find $\xi_1, \xi_2, t_1$, and $t_2$? and how can I generalize this solution for my optimization problem?

Answer 1

You can model the disjunction by introducing binary variables $x_{l,l^\prime}$ and the following linear constraints: \begin{align} \xi_l+\xi_{l^\prime}-1 &\le x_{l,l^\prime} + x_{l^\prime,l}\\ T_{r,l}+t_l&\geq x_{l^\prime,l}(T_{e,l^\prime}+t_{l^\prime}) \\ T_{r,l^\prime}+t_{l^\prime}&\geq x_{l,l^\prime}(T_{e,l}+t_{l}) \\ \end{align} The first constraint can be derived by rewriting the desired logical proposition in conjunctive normal form as follows: \begin{equation} (\xi_l \land \xi_{l^\prime}) \implies (x_{l,l^\prime} \lor x_{l^\prime,l}) \\ \neg(\xi_l \land \xi_{l^\prime}) \lor (x_{l,l^\prime} \lor x_{l^\prime,l}) \\ \neg \xi_l \lor \neg \xi_{l^\prime} \lor x_{l,l^\prime} \lor x_{l^\prime,l} \\ (1 - \xi_l) + (1 - \xi_{l^\prime}) + x_{l,l^\prime} + x_{l^\prime,l} \ge 1 \\ \xi_l+\xi_{l^\prime}-1 \le x_{l,l^\prime} + x_{l^\prime,l} \end{equation}