A specific case of a resource constrained project scheduling problem with partially renewable resources (RCPSP/$\pi$) - OR-Tools

Question

I've been trying solve a specific case of the resource constrained project scheduling problem with partially renewable resources (RCPSP/$\pi$ in the literature e.g. this paper). These resources are renewed after a subset of time-periods, as opposed to standard renewable resource which are renewed after every time period.

Notation

Sets

• $I$ - set of activities. $I=\{0,1,\dots,n+1\}$ ($0$ and $n+1$ are dummy activities);
• $T$ - set of time periods;
• $R$ - set of partially renewable resources;
• $E$ - set of precedences. If $(i,j) \in E$ then activity $j$ must be processed after activity $i$;
• $\Pi_r$ - set of subset of periods for resource $r$. $\Pi_r=\{P_{r1},\dots,P_{rU}\}$ where $P_{ru}\subset T$ ($u=1,\dots,U$).

Parameters

• $b_{ri}$ - parameter ($\mathbb{R}^+$) that denotes the consumption of resource $r$ for activity $i$;
• $B_{r}$ - parameter ($\mathbb{R}^+$) that denotes the resource $r$ available.
• $p_{i}$ - parameter ($\mathbb{Z}^+$) that denotes the duration (in time periods) of activity $i$;

Formulation

Let $x_{it}$ be a binary variable which takes value $1$ if activity $i$ starts at time $t$, $0$ otherwise.

With this, we can formulate the IP,

\begin{align} &\min \sum_{t}t x_{n+1,t} & & \\ &\textbf{st.} \sum_{t} x_{it}=1 & \forall i \\ & \sum_{i} b_{ri} \sum_{s\in P_{ru}} x_{is}\leq B_r & \forall r, P_{ru}\in \Pi_r \\ & \sum_{t} tx_{jt} - \sum_t tx_{it} \geq p_i & \forall (i,j)\in E \\ & x_{it}\in\{0,1\} & \forall i,t \end{align}

Minimise the makespan subject to: unique start time for each activity, partially renewable resource constraints, and precedence.

Simplifications and Initial approach

In our case we have several simplifications.

• The duration is unitary for all activities, $p_i=1, \forall i$
• The resource demand is either $0$ or $1$, $b_{ri}\in\{0,1\}, \forall r,i$
• Each subset $P_{ru}$ as a fixed size $D_r\geq1$. The number of these is the feasible times that don't exceed the planning horizon, $U=|\{t\in T: t\leq|T|-D_r + 1\}|$. And $P_{ru} = \{t\in T: u\leq t < u+D_r\}$ (set of processing times for a given start time $u$).

Example

For example, consider an instance with $T=\{1,2,3,4\}$, and one resource with $D_r=3$. We have $U=|\{1,2\}|$, $P_{r1}=\{1,2,3\}$ and $P_{r2}=\{2,3,4\}$. For a single activity, the resource constraints look like (letting $b_{r1}=1$), \begin{align} x_{11}+&x_{12}&+x_{13} & &\leq B_r\\ & x_{12}&+x_{13}&+x_{14} &\leq B_r \end{align}

As an approximation for large instances, we are translating the problem to a standard renewable resource case and solving it using the cumulative constraint in OR-Tools. For this, we force to the subsets to contain a single element (a single time period) and the upper bound on resources $B_r$, $\left\lfloor\frac{B_r}{D_r}\right\rfloor$, obtaining the standard constraint,

$$ \sum_i b_{ri} \sum_{s=\max\{0,t-p_i+1\}}^t x_{is}\leq \left\lfloor\frac{B_r}{D_r}\right\rfloor, \forall r, t $$

Since, $p_i=1$, we have $$ \sum_i b_{ri} x_{it}\leq \left\lfloor\frac{B_r}{D_r}\right\rfloor, \forall r, t $$

Questions

My questions are:

1. Using OR-Tools, is there an efficient formulation that doesn't require a BoolVar for each binary variable? E.g. enforcing the cumulative constraint for the subsets?

2. Also, with the simplifications mentioned, does anyone recognise the problem or some potential ways of attacking it?

Answer 1

To have resources being released at given time points, you have two options.

1. Have one optional interval per time interval. This interval always ends at the end of the interval. For a given demand, one of the optional intervals must be selected. And the presence literal of the optional interval implies that the start of the main interval is equal to the start of the optional interval, same thing for the end, and duration if needed.
2. Restrict the end variable of the interval to be only and the end of the time period. Have the duration variable and greater than the processing time. The trick is to make sure the interval does not cross one of the time points. Either restrict the duration to be smaller to the distance between two time points (in case this is regular), of have one boolean var per time interval, and have this boolvar implies that the end is the end of the interval, and that the start in included in the interval.

More details on 2:

Imagine the task must end at 10, 20, 30. You can restrict the domain of the end_var to be {10, 20, 30}. If the duration of the task is <= 10, you have nothing else to do. If duration is > 10, the problem is infeasible.

In the second case, task must end at 20, 30, or 50. You can still restrict the domain of the end_var to {20, 30, 50}. But with a duration of 15, a start of time of 15 is not valid. You have two solution for this:

• If the duration is fixed, you can always restrict the start to [0..5] U [30..35].
• If the duration is variable (i.e. in [5, 15]), this is not valid. So you create 1 boolean per time interval ([0..20], [20..30], and [30..50]) and add the implication:

   b1 => end == 20
   b1 => start in [0..20]

   b2 => end == 30
   b2 => start in [20..30]

   b3 => end == 50
   b3 => start in [30..50]

   b1 + b2 + b3 == 1

I hope this is clear enough.