2
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ (a) have you looked at the rcpsp_sat.py example ? (b) can you describe what a partially renewable resource is ? $\endgroup$ Aug 10, 2021 at 12:03
  • $\begingroup$ @David Torres, would you see this link? $\endgroup$
    – A.Omidi
    Aug 10, 2021 at 13:29
  • $\begingroup$ Hi @LaurentPerron (a) yes, it is a great example, but the partially renewable case isn't covered. (b) I've added a small explanation at the top and an example constraint. Partially renewable resources "are renewed after a subset of time-periods, as opposed to standard renewable resource which are renewed after every time period." So we need to add the variables to different resource constraints depending on the start time. Kindoff enforcing the cumulative constraint for the different domains. $\endgroup$ Aug 10, 2021 at 16:31
  • $\begingroup$ Thanks @A.Omidi! I am aware of the two versions of the precedence constraints, the one I've written is the weaker. $\endgroup$ Aug 10, 2021 at 16:36

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks! :) 1. I think I understand as it seems similar to the multi-mode case of the RCPSP example. 2. I don't get. $\endgroup$ Aug 12, 2021 at 12:51
  • $\begingroup$ Fleshed out solution 2. $\endgroup$ Aug 12, 2021 at 13:06

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.