4
$\begingroup$

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?

$\endgroup$
1

1 Answer 1

6
$\begingroup$

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}

$\endgroup$
4
  • $\begingroup$ It is OK, But how can I continue solving this problem? $\endgroup$
    – llVll
    Sep 20, 2019 at 9:03
  • $\begingroup$ @IIVII Your question seems to be asking for a way to handle your model, which has disjunctive ("or") constraints. This answer tells you how to handle the disjunctive constraints. If this answer does not sufficiently answer your question, please provide more details about why it is insufficient. $\endgroup$ Sep 20, 2019 at 12:30
  • $\begingroup$ By using this answer, I write or condition in linear constraint. I am looking for comments about solving my optimization problem. $\endgroup$
    – llVll
    Sep 20, 2019 at 19:07
  • $\begingroup$ Now that you have a mixed integer linear programming (MILP) formulation, you can use a MILP solver to solve your problem. $\endgroup$
    – RobPratt
    Sep 20, 2019 at 19:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.