2

Goal:

My goal is to come up with a Resource-Constrained Project Scheduling (RCPS) model where the resource capacity constraints are aggregated and verified on time buckets, which can be of varying size. This allows the use of more detailed planning in the near future and more aggregated planning further away.

To be more specific, instead of enforcing that at all times, the resource requirement is not more than the resource availability, I would like to only look at the total resource requirement in a bucket and compare that to the total resource availability in that bucket. This introduces questions such as: what if an operation overlaps multiple buckets?

As an example, assume that we have two consecutive buckets [3,6] and [6,9]. Suppose that an activity is scheduled on [5,8], resource A is required for the entire activity lead time and is available at any time (yielding 3 units of resource availability per bucket). Would we then assign 1 unit of resource requirement (e.g. hour) to the first bucket and 2 units to the second bucket?

Literature example:

As part of literature research for this problem, I came across this publication from Rom et al. 2002. It is about MRP in a job shop environment and uses RCPS models to do so.

The model is a continuous-time model, as it allows lead times of activities to be non-integral. Interestingly, it uses time-buckets for checking resource capacity violations. The procedure is as follows:

  • The time-horizon is divided into time milestones $T_i, i = 1, 2, \ldots, N$.
  • Binary variable $y^j_i$ equals 1 IFF activity $j$ completes in bucket $i: [T_i, T_{i+1}]$.
  • Parameter $a_{jk}$ is the amount of resource $k$ needed by activity $j$.
  • Parameter $R_{i,k}$ is the availability of resource $k$ (resources that are similar are pooled) in bucket $i$.

The resource constraints are then given by $$\sum_{j=1}^{N} a_{j k} y_{i}^{j} \leqslant R_{i k} \quad \forall k, i$$

To me, this seems a bit odd because this equation says that for all activities that end in bucket $i$, we look at the total resource amount required by those activities (not necessarily in that bucket) and restrict this quantity to be less than the resource availability in a bucket. The main issue is that whenever an activity starts in e.g. bucket $i-1$ but ends in bucket $i$, the resource consumption seems only to be allocated to bucket $i$. Continuing the example mentioned above, this means that all three units of resource requirement are assigned to the second bucket, meaning that the resource is not available anymore in that bucket as its availability was 3 units.

Question:

I wonder whether my observation is correct and if anyone knows some good approaches to using time buckets in an RCPS setting. Any publications from literature would be highly appreciated.

Rutger
  • 115
  • 4
  • 1
    Welcome to OR.SE. Would you please, more elaborate to understand the problem a bit better by a numerical simple example? What exactly do you mean by if an operation overlaps multiple buckets?? As a simple explanation, suppose a task has consumed $2$ days to be performed on the specific resource and the time bucket is daily. – A.Omidi Feb 23 '22 at 10:46
  • If you define the available time in each time bucket around $24$ hours, the tasks should be performed in $2$ days without any extra resources. (actually if the resource is being available in $24$ hours). Indeed, for achieving more resources you would need to pay violation penalties. – A.Omidi Feb 23 '22 at 10:47
  • Also, you can use $\sum_{j\in J}\sum_{t_2=t-p_{j}+1}^{t} u_{(j,r)}x_{(j,t_2)} \leq c_{r} ,,, \forall t\in \mathcal{T}, r \in R$ resource capacity constraints instead of what you mentioned to mirror what you are trying to do better. Where $j$ referred to tasks and $t$ referred to time bucket. – A.Omidi Feb 23 '22 at 10:52
  • @A.Omidi I added a small example. Could you maybe elaborate a bit more on the last inequality that you mention? Does $x_{j,t_2}$ refer to the resource usage of activity $j$ in bucket $t_2$, or what does the index $t_2$ exactly represent – Rutger Feb 23 '22 at 12:23
  • 1
    this is a variant of the RCPSP with the time-index formulation. Where $J$ is the set of the jobs, $R$ is the set of the resources, $T$ is the planning duration, $P_j$ is the processing time of job $j$, $U_{(r,j)}$ is the amount of resource $r$ required for processing job $j$, $C_r$ is the capacity of renewable resource $r$. – A.Omidi Feb 23 '22 at 13:12
  • For more details please, see this and this links. – A.Omidi Feb 23 '22 at 13:13
  • Thanks for the provided example. It seems with defining a subset of the planning horizon to capture overlap, [5,8], and also declaring the related variable to use the resource exactly on the subset by adding the appropriate penalties would work. Do you try that? – A.Omidi Feb 23 '22 at 13:19
  • A bit late and probably not that relevant but it seems quite similar to event-based models: Tesch (2020) (original papers cited within). – David Torres Oct 13 '22 at 15:34

1 Answers1

1

There is a general PPT presentation on multi-period planning at

https://www.lindo.com/library/MultiPeriodPlan43.pdf

It has several slides on how to choose period length, how to (and how not to) represent resource capacity constraints and precedence constraints.

It also has several dozen references at the end on multi-period optimization models.

LINDO Systems
  • 509
  • 2
  • 2