Add explanation and example constraint
Source Link

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?

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).

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$).

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\}$.

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?

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?

edited title
Link

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

edited body
Source Link

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).

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}\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$).

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\}$.

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?

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).

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$).

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\}$.

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?

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).

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$).

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\}$.

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?

Source Link
Loading