# Scheduling Optimization Problem

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?

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