2
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ 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. $\endgroup$
    – A.Omidi
    Feb 23 at 10:46
  • $\begingroup$ 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. $\endgroup$
    – A.Omidi
    Feb 23 at 10:47
  • $\begingroup$ 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. $\endgroup$
    – A.Omidi
    Feb 23 at 10:52
  • $\begingroup$ @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 $\endgroup$
    – Rutger
    Feb 23 at 12:23
  • 1
    $\begingroup$ 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$. $\endgroup$
    – A.Omidi
    Feb 23 at 13:12

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.