How to solve this variant of RCPSP

Question

We have $m$ projects in parallel that require shared resources the resources has time varying capacities (i.e $B_{rt}$ is the units of resource $r$ available in period $t$). For each project there is $n_j$ jobs to be scheduled. Within each project there is a generalized precedence constraints (i.e of type $S_{kj} \geq S_{ki} + v_{kij} \forall (i,j) \in E_k$ where $S_{ki}$ and $S_{kj}$ denote the starting times of jobs $i$ and $j$ of project $k$, $v_{kij}$ is a time lag that can be non-negative or non positive and $E_k$ the precedence graph associated to project $k$) There is no precedence relations between jobs belonging to different projects. The objective function is the weighted sum of time completion (makespan) of each project.

Any ideas on how to solve the problem? I can't find papers that treat all of these constraints simultaneously.

I tried to think of a local search but I am struggling to define a neighborhood (the classical swip etc does not work here).

I am also thinking of how to decompose the problem, to deal with every project independently, but how to reassemble the solutions in order to get a feasible solution for the original problem ?

Edit : I modeled the problem, I am looking for solution methods other than simply and only to write the model. The point is I have large instances and solvers are not that good for scheduling problems.

Answer 1

There are broadly 2 approaches for obtaining feasible solutions to your problem, namely (1) Local search, and (ii) exact approaches (i.e. using solvers).

If you prefer to solve using exact approaches i.e. model the problem using a solver, then your best bet may be to model the problem using a Constraint Programming solver. At least from what I gather (so take it with a pinch of salt), CP tends to be more preferable over MIP approaches for scheduling problems, especially for problems that are more complicated than a single machine scheduling problem.

For local search methods, it would be helpful if you precisely define which approaches you have tried. I have to admit I have no personal experience working with the time-varying capacity of resources and have not all that frequently encountered problems (in papers) of the type you mention. Below I suggest a reasonably straightforward approach to try for your problem:

Approach 1:

1. Model the problem using a disjunctive graph (just as it is done in Job Shop Problems (JSPs)), or alternative graph (if you have blocking constraints).

2. Assuming you have a feasible solution to your problem and that it is represented graphically on the disjunctive graph, now formulate some simple swap moves using the critical path of the current solution. Resources that may be helpful to you here are swap neighborhoods for JSPs, and problems that have buffers with capacities. Another interesting neighborhood to look at is the Job Insertion neighborhood.

3. Generate new neighbors in your neighborhood with those swap moves. For each neighbor, compute a schedule using the longest path algorithm with the help of a graphical representation of the solution. Suppose the new solution violates any resource capacity, then check whether inserting wait times can make your problem feasible to the resource constraints. This is perhaps doable as a simple LP. Suppose inserting wait times does not help, then a common strategy in local search is to accept the solution, but the way you measure the quality of the infeasible solution is to make it the sum of it's completion time plus some penalty terms to indicate the degree of resource violation of the solution. You can implement this simple strategy using a meta-heuristic such as late acceptance, but alternatives exist.

In summary ( perhaps more directly answers your question on decomposing the problem), implement a local search procedure that decomposes the problem into 2 stages: (1) Resource allocation and sequencing phase, which allocates and establishes the sequence in which each resource gets allocated to the different jobs within those projects and (2) compute a schedule using say Depth-first search (DFS) or exact solver such that the solution is feasible w.r.t time-varying nature of the availability of resources. With this approach, you can iterate from one solution to another (in a local search manner) by only worrying about the way in which resources are allocated to those projects, the scheduling portion can be given to an exact solver or computed heuristically using a search procedure like DFS.

In my personal experience for scheduling problems with complicated constraints, the above approach seems to outperform the best primal solution returned by CP solvers within practical time limits (like 30 mins). However bear in mind that, considerable effort may be needed on part of the heuristic designer for optimizing the many sub-components with the approach I suggested.