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:
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?Also, with the simplifications mentioned, does anyone recognise the problem or some potential ways of attacking it?