This section details all the practical aspects of the optimal CDT scheduling. We intentionally provide a very general framework, but illustrate it with several simple examples.
Basic pyomo Linear Programming Example
As an introduction we load the necessary pyomo packages and solve an ultra-simple linear programming example. \[
\begin{array}{ll}
\min & 2 x_1 + 3 x_2\\
\mathrm{s.t.} & 3 x_1 + 4 x_2 \geq 1\\
& x_1, x_2 \geq 0
\end{array}
\]
pyomo.environ provides the framework for building the model
SolverFactory allows to call the solver used to solve the optimization problem
import pyomo.environ as pyo from pyomo.opt import SolverFactory model = pyo.ConcreteModel("Simple Linear")# Decision variables and domainsmodel.x = pyo.Var([1,2], domain=pyo.NonNegativeReals)# Objective functionmodel.OBJ = pyo.Objective(expr =2*model.x[1] +3*model.x[2])# Constraint(s)model.Constraint1 = pyo.Constraint(expr =3*model.x[1] +4*model.x[2] >=1)solver ='appsi_highs'SOLVER = pyo.SolverFactory(solver)assert SOLVER.available(), f"Solver {solver} is not available."# Solve and print solutionSOLVER.solve(model)print(f"x = ({pyo.value(model.x[1]):.2f}, {pyo.value(model.x[2]):.2f})")print(f"optimal value = {pyo.value(model.OBJ):.2f}")
x = (0.33, 0.00)
optimal value = 0.67
We can print out
the complete model;
a full trace of the optimization process.
Disjunctions
The decisions encountered in the CDT involve discrete, Boolean choices. These can take the following forms:
Sequencing decisions, where \(A\) ends before \(B,\) or \(B\) ends before \(A.\)
Switching decisions, where a facility is used or not.
Alternative selection among a set of pricing policies, for example for alternative energy sources.
The general disjunctive problem is formulated as
\[
\begin{align}
\min \quad & z=f(x) + \sum_{k \in K} c_k & \text{objective}\\
\text{s.t.} \quad & r(x) \le 0 & \text{global constraint} \\
& \underset{j\in J_{k}}{\vee}\left[\begin{array}{c}
Y_{jk}\\
g_{jk}(x)\le 0\\
c_{k}=\gamma_{jk}
\end{array}\right] & \text{disjunctions} \\
& \underset{j\in J_{k}}{\veebar} Y_{jk} & \text{disjunctions} \\
& 0\le x \le U, \; c_k \in \mathbb{R}, \; Y_{jk} = \{\text{True, False}\}
\end{align}\] If the Boolean variable is True both the inequalities and the cost equation are enforced; if the Boolean variable is False they are both ignored.
For sequencing decisions, between two tasks \(i\) and \(j,\) the disjuction is written as \[
\left[\begin{array}{c}
Y_{k}\\
s_i + d_i \le s_j\\
\end{array}\right] \vee
\left[\begin{array}{c}
\neg Y_{k}\\
s_j + d_j \le s_i\\
\end{array}\right] ,
\] where \(s_i,\)\(d_i\) are the start and duration of task \(i.\)
The disjunctive formulations will always increase the number of variables and constraints of the optimization problem. Thus, they are usually only profitable for long time horizon problems.
Note
For the CDT, in addition to sequencing constraints, the resource constraints must also be satisfied. This is important for jobs that can in theory be executed in parallel, but might in practice have a resource conflict and will need to be executed sequentially.
Big-M Method
The big-M method converts the logical disjunction “\(i\) before \(j\)” OR “\(j\) before \(i\)” into a system of linear inequalities with binary variables. The formulation is
\[
\begin{align}
S_j & \geq S_i + d_i - M(1 - y_{ij}), \\
S_i & \geq S_j + d_j - My_{ij},
\end{align}\] where \(S_i\) is the starting time, \(d_i\) the duration and \(M\) is a large enough positive constant, usually set to the upper bound on the makespan. When activity \(i\) precedes \(j,\) then \(y_{ij} =1\) and the first inequality ensures that \(j\) starts after \(i\) has finished, whereas the second inequality is trivially satisfied and has no effect. On the other hand, if activity \(j\) precedes \(i,\) then \(y_{ij} =0\) and the first inequality is inoperant, whereas the second ensures that \(i\) starts after \(j\) has finished.
GDP OPT
Disjunctive programming is useful in certain situations since it is better than “forcing” a given constraint into a MI(N)LP form through complicated tricks.
PYOMO includes a generalized disjunctive programming pack, GDP.opt, that accepts pure disjunctions and then uses specialized logic-based decomposition methods to solve the problem, without the need for prior conversion to MI(N)LP, as discussed above. The benefit of using a disjunctive programming formulation lies in its ability to preserve and leverage the intrinsic logical framework of the problem at hand, thereby mitigating its combinatorial complexity.
Tight Formulations
Basically all MILP problems are solved by branch-and-bound methods. The performance of a branch-and-bound method can greatly improve by having a tight problem formulation, that is, one where the gap between the feasible region of the original problem and its linear relaxation is small. Such a tight formulation typically leads to better bounds and, therefore, more pruning of subproblems, speeding up computation. The extreme case is to use the convex hull for the formulation.
Finding a tight formulation for a specific problem is an art that requires experience with mathematical modeling. Some “rules of thumb” here are:
to have as few as possible big-M constraints with the large constants \(M,\)
to avoid having superfluous decision variables, and
to avoid formulating as an inequality, a relation that should hold with equality for the optimal solution.
