graph LR
A["Suppliers"] --> B["Factories"]
B --> C["Warehouses"]
C --> D["Retailers"]
Overview
This chapter is a collection of sequencing examples that are as close as possible to the CDT, without all the details. The objecive is to prepare a library on which more realistic, and eventually forward-looking examples can be based. Our intention is not only to address today’s scheduling problems, but also to prepare the ground for scheduling challenges of the next 5 to 10 years, where data and compute volumes will increase by several orders of magnitude—outstanding examples are SKA and CERN’s FCC.
The chapter is divied into deterministic (D1 to D4) and stochastic (S1 to S3) scenarios. Realistic cases are presented in the Use-Cases chapter.
D1. Simplified Supply Chain Examples
Putting together:
- primal problem,
- dual problem,
- sensitivity analysis.
See Example D1 and Example D1a
These supply chain examples have the following structure.
%%{init: {'flowchart': {'curve': 'linear'}}}%%
flowchart LR
subgraph SUP["Suppliers"]
S1["$$S_1$$"]
S2["$$S_2$$"]
S3["$$S_3$$"]
end
subgraph FAC["Factories"]
F1["$$F_1$$"]
F2["$$F_2$$"]
F3["$$F_3$$"]
end
subgraph WAR["Warehouses"]
W1["$$W_1$$"]
W2["$$W_2$$"]
W3["$$W_3$$"]
end
subgraph RET["Retailers"]
R1["$$R_1$$"]
R2["$$R_2$$"]
R3["$$R_3$$"]
end
S1 --> F1
S1 --> F2
S1 --> F3
F1 --> W1
F1 --> W2
F1 --> W3
W1 --> R1
W1 --> R2
W1 --> R3
style SUP fill:#EEEDFE,stroke:#AFA9EC,color:#3C3489
style FAC fill:#E1F5EE,stroke:#5DCAA5,color:#085041
style WAR fill:#FAEEDA,stroke:#EF9F27,color:#633806
style RET fill:#FAECE7,stroke:#F0997B,color:#993C1D
classDef purple fill:#EEEDFE,stroke:#AFA9EC,color:#3C3489
classDef teal fill:#E1F5EE,stroke:#5DCAA5,color:#085041
classDef amber fill:#FAEEDA,stroke:#EF9F27,color:#633806
classDef coral fill:#FAECE7,stroke:#F0997B,color:#993C1D
class S1,S2,S3 purple
class F1,F2,F3 teal
class W1,W2,W3 amber
class R1,R2,R3 coral
graph LR
A["Instruments"] --> B["HPC centres"]
B --> C["Data centres"]
C --> D["End-users"]
D2. Simplified Scheduling Examples
The scheduling Example D2 covers a lot of ground. We study a classical scheduling problem, where we are given a set of jobs, their release times, their durations and their due times. The objective is to optimize the makespan, or total duration of all the jobs. We also introduce the total past due, or lateness/tardiness as an additional objective.
We study:
- empirical scheduling (LIFO, EDD, SPT);
- key performance indicators (KPI);
- single-machine and multiple-machine scheduling;
- disjunctive scheduling using Big-M and convex hull approaches.
D3. Simplified RCPSP Example
We are now in a position to add:
- resource constraints, and
- precedence relations described by a DAG
to the scheduling problems above. This problem is known as the Resource Constrained Project Scheduling Problem, or RCPSP.
The optimization is now more complex, since the resource constraints have to be simultaneously satisfied while minimizing the makespan, or any function of the makespan, while satisfying all precedences described by the Directed Acyclic Graph of the complete workflow.
In Example D3 we combine:
- resource constraints,
- precedence relations,
- time-indexed formulation,
- disjunctive approach.
The formulation is taken from Section Mathematical Formulation - Deterministic Model.
D4. Simplified MRCPSP Example
The final extension is to add multiple modes, or machines, for the execution of each task in the workflow. In other words, there is an additional choice to be made between, say, a fast but expensive machine, and a slower but cheaper one. This is the connection between the resource schedule and the supply chain viewpoint that best characterizes cross-facility workflows in the CDT context.
In this example we have 4 jobs, 2 possible modes, 1 renewable resource and no non-renewable resources. Jobs 2 and 3 can be executed in mode 1 or in mode 2.
graph LR
A["$$J_0$$"] --> B("$$J_1$$")
A --> C("$$J_2$$")
B --> D("$$J_3$$")
C --> E("$$J_4$$")
D --> F["$$J_5$$"]
E --> F
The project instance, shown above, is detailed in Table 1, where \(S_j\) is the successor list of job \(j,\) \(m\) is the mode, \(d_{jm}\) is the duration of job \(j\) in mode \(m,\) \(k^{\rho}_{jm1}\) is the renewable resource requirement, \(R^{\rho}\) is the renewable resource list, \(K^{\rho}\) is the renewable resource limit, and \(R^{\nu}\) is the non-renewable resource list, taken as empty. In other words we have 4 jobs, 2 possible modes, 1 renewable resource and no non-renewable resources. Jobs 2 and 3 can be executed in mode 1 or in mode 2. Jobs 0 and 5 are the source and sink respectively, with zero duration and zero resources.
\[\begin{aligned} & \text {Table 1. Multi-mode RCPSP for a 4-job, 2-mode workflow. }\\ &\begin{array}{cccccccc} %\begin{tabular}{|c|c|c|c|c|c|c|c|} \hline j & S_{j}& m & d_{jm} & k^{\rho}_{jm1} & R^{\rho} & K^{\rho}_{1} & R^{\nu}\\ \hline 0 & \left\{ 1,2\right\} & 1 & 0 & 0 & \left\{ 1\right\} & 3 & \emptyset \\ 1 & \left\{ 3\right\} & 1 & 2 & 2 & & & \\ 2 & \left\{ 4\right\} & 1 & 2 & 2 & & & \\ & & 2 & 3 & 1 & & & \\ 3 & \left\{ 5\right\} & 1 & 1 & 3 & & & \\ & & 2 & 2 & 1 & & & \\ 4 & \left\{ 5\right\} & 1 & 2 & 3 & & & \\ 5 & \emptyset & 1 & 0 & 0 & & & \\ \hline %\end{tabular} \end{array} \end{aligned}\]
Input File
The simplest input file is a direct transcription of the table of variables.
{
"0":{"suc":("1","2"),"mod":"A","drt":0, "rsc":0},
"1":{"suc":"3","mod":"A", "drt":2, "rsc":2},
"2":{"suc":"4","mod":("A","B"),"drt":[2,3],"rsc":[2, 1]},
"3":{"suc":"5","mod":("A","B"),"drt":[1,2],"rsc":[3, 1]},
"4":{"suc":"5","mod":"A", "drt":2, "rsc":3},
"5": {"suc":"","mod":"A", "drt":0, "rsc":0 }
}import json
with open("input.json", "r") as jsonfile:
TASKS = json.load(jsonfile)Though, for interoperability, we should privilege the data model format, described above in Section CDT Implementation.
MRCPSP Benchmark using CPLEX
In Example I1 of the Implementation section, we solve a 30-task example with 3 modes, 2 renewable resources and 2 non-renewable resources. This is certainly a bit beyond actual CDT use-cases, but illustrates the capability of good optimization codes to address far more complex workflows with relative ease.
Stochastic Cases
Here we present a very complete range of pedagogical examples covering
- Single-Stage cases, based on expectations with comparison of EVM, EVSS and EVPI.
- Two-Stage cases, with recourse decisions.
- Multi-Stage cases.
These examples are based on the excellent presentations of Postek et al. (2025) and its associated website. We have tried to adapt these examples, as far as possible, to the CCDS context.
S0. Single-Stage Stochastic
Before embarking on two- and multi-stage cases, it is very instructive to study the context of a single stage, without a preceding deterministic stage as was presented in the theoretical section Stochastic, multistage programming. This context brings out the important concepts of the following scenarios: Expected Value for the Mean (EVM), Expected Value of the Stochastic Solution (EVSS), and Expected Value with Perfect Information (EVPI). Then, we can fully appreciate the importance of different stochastic models, and their comparison with deterministic ones.
The most basic way of accounting for randomness is to consider the average, or expected value, of a given uncertain quantity. For constraints, expectations are not useful, because protection against the average outcome generally produces a low level of protection. For that reason, we consider problems in which the expectation appears only in the objective, \[ \min_x \mathbb{E}_z \left[ f(x,z) \right], \tag{1}\] where \(x\) is the decision variable, and \(z\) is a random variable.
S0a. Single-Stage Newsvendor Problem
The newsvendor problem is a cornerstone of stochastic optimization and can be applied to many different contexts. We suppose that a product (e.g. newspapers) can be purchased for a given cost, \(c,\) but the sales at price \(r\) depend on some uncertain demand \(d_s,\) where \(s\) is a possible scenario, and finally there may be a salvage value \(w\) that is refunded for unsold items.
The problem is to determine how many items to purchase. The dilemma is that the scenario (say, weather) will not be known until after the order is placed. Ordering enough items to meet demand for a good scenario (weather) results in a financial penalty on returned goods if the scenario (weather) is poor. On the other hand, ordering just enough items to satisfy demand on a poor scenario (weather) leaves “money on the table” if the scenario (weather) is good.
In terms of the CCDS, we can reformulate the newsvendor as an optimal inventory problem, where we need to allocate \(x\) to satisfy (uncertain) demand \(d\) with three associated costs:
- \(c\) allocation cost,
- \(b\) back penalty (shortage) cost,
- \(h\) holding (surplus) cost.
The objective here is to minimize the total cost, \[ G(x,d) = cx +b[d-x]_+ + h[x-d]_+ \] where \([\cdot]_+ \doteq \max(\cdot\, , 0).\)
Note, if \(d\) is considered to be a random variable, then we obtain the objective of Equation 1.
First, we will consider a single-stage formulation, which will be generalized below to a two-stage case. Here we consider a discrete distribution for the sales (demand)—see Example S0a.
S0b. Allocation Optimization for a Data or Compute Center
This is another example of an inventory optimization (newsvendor) problem, where we want to buy an optimal quantity of stock, to cover an uncertain (future) demand.
In Example S0b we compare different, continuous distributions for the demand (sales).
S1. Two-Stage Stochastic
Scenario Tree
When the probability distributions for the random parameters (events) are discrete, there are only a finite number of outcomes in each stage. With each random parameter fixed to one of its possible outcomes, one can create a scenario representing one possible realization of the future. Enumeration of all possible combinations of outcomes allows us to represent all scenarios in a tree, with each scenario being a path from the root of the tree to one of its leaves. The nodes visited by each path correspond to values assumed by random parameters in the model.
SAA
In Example S1a we use the statistical average approximation (SAA) to sample from continuous distributions in a 2-stage stochastic optimization for the design or allocation of computing resources. This is another example of an inventory optimization (newsvendor) problem, where we want to invest in an optimal number of resources, to cover an uncertain (future) demand.
S2. Multi-Stage Stochastic
We illustrate the construction of a multi-stage scenario tree with another stochastic version of the Newsvendor inventory problem. In this case, we must decide how much to order initially and then at a later time, how much of any unsold product to return before the end of the planning horizon. There is a shortage penalty when there are lost sales and a carrying cost for leftover (unsold) units. The decision process takes place under uncertain demand and uncertain price per returned item. This is a three-stage. problem.
- In stage 0, the order quantity has to be decided (under uncertain demand).
- In stage 1, at the beginning, the demand is revealed. A recourse decision, at the end of stage 1, is the number of units to be returned to the publisher (for an uncertain refund price).
- In stage 2 at the beginning, the refund price is announced by the publisher. The price per returned item can be either:
- Positive (i.e. publisher accepts them at a high price which covers the cost of shipping and handling) or
- Negative (i.e. publisher accepts them at a low price which doesn’t cover the cost of shipping and handling).
- The objective is to maximize the total expected profit at the end of planning horizon (stage 2).
S3. Risk Measures
As presented in the Risk Measures section, there are various ways to include risk in the cost function. In this example, we analyze a stochastic energy dispatch problem, and compare the following risk measures:
- mean,
- CVaR,
- mean-variance,
- exponential.