**A novel approach to solve various resource-constrained**

project scheduling problems

project scheduling problems

**José Coelho* and Mario Vanhoucke****

* - Technical University of Lisbon, Lisbon (Portugal)

- Universidade Aberta, Lisbon (Portugal) Jose.Coelho@uab.pt

** - Faculty of Economics and Business Administration, Ghent University, (Belgium) mario.vanhoucke@ugent.be

- Technology and Operations Management Area, Vlerick Business School (Belgium) mario.vanhoucke@vlerick.com

- Department of Management Science and Innovation, University College London (United Kingdom) m.vanhoucke@ucl.ac.uk

Transformation of MRCPSP in SAT+RCPSP

**Changing of an AND-precedence relation into an OR-precedence relation, and Bi-directional relation**

**Tests and Results**

j103_4.mm instance, from PSPLIB

Conversion of non-renewable resources to SAT+RCPSP:

If all activity modes inside an activity, have the same value for a non-renewable resource, remove the activity from the non-renewable resource restriction and subtract the amount to the available resource amount

There are no activity and non-renewable resource in these conditions, except the null usage, activities 1, 4 and 12 in N1 and activities 1, 5, 6 and 12 in N2.

If an activity-mode have a null resource usage, increase one value in all activity-mode usage and in the resource availability

This is just to avoid having a zero in the clause (a zero is a clause ending)

N1: 60≤(11v2+10v3+1v4 )+(9v5+1v6+9v7 )+(8v11+4v12+6v13 )+(7v14+7v15+6v16 )+(1v17+9v18+1v19 )+(1v20+8v21+6v22 )+(8v23+9v24+1v25 )+(1v26+7v27+7v28 )+(1v29+1v30+10v31)

N2: 43≤(1v2+1v3+5v4 )+(1v5+11v6+1v7 )+(6v8+5v9+5v10 )+(6v17+1v18+4v19 )+(6v20+1v21+1v22 )+(1v23+1v24+9v25 )+(3v26+1v27+1v28 )+(10v29+9v30+1v31)

Delete impossible modes, due renewable resources (set them to false in SAT):

For R1, over the limit 7, exists the activities 20 and 26

For R2, over the limit 5, exists the activities 11, 18, 21, 24, 30 and 31

This results in the following clauses in sat:

12 1 -11 -18 -20 -21 22 -24 -26 29 -30 -31 32 0

The first clause has all assigned variables.

It means that 12 activity-modes have a forced assignment.

Activity 1 and 32 are the dummy start/end activity, with only one mode, so SAT will have its forced assignment to true;

Activity 11 correspond to activity 5, mode 1, is not realized due to R2 have only 5 units, and the activity requires 6.

Activities 22 and 29 have a forced value, since they are the only mode in each activity not assigned to false.

1 2 3 4 0

Clause forcing that 2, 3 or 4 is realized, to make sure activity 2 have one of the modes realized

2 -2 -3 -4 0

Clause forcing that in 2, 3 and 4, at least 2 are not realized, to make sure that in activity 2, no more than 1 activity mode is realized

The rest of the clauses of this type, force the activity mode logic:

1 5 6 7 0

2 -5 -6 -7 0

1 8 9 10 0

2 -8 -9 -10 0

1 12 13 0

1 -12 -13 0

1 14 15 16 0

2 -14 -15 -16 0

1 17 19 0

1 -17 -19 0

1 23 25 0

1 -23 -25 0

1 27 28 0

1 -27 -28 0

The nonrenewable resource clauses, need updates to remove the forced activity values. The false ones, is needed just to delete them, but the true ones is required to update the resource availability:

N1: 53≥(11v2+10v3+1v4 )+(9v5+1v6+9v7 )+(4v12+6v13 )+(7v14+7v15+6v16 )+(1v17+1v19 )+(8v23+1v25 )+(7v27+7v28 )

(maximal usage of N1 is now 11+9+6+7+1+8+7=49, that is less than 53)

N2: 32≥(1v2+1v3+5v4 )+(1v5+11v6+1v7 )+(6v8+5v9+5v10 )+(6v17+4v19 )+(1v23+9v25 )+(1v27+1v28 )

Only a restriction on N2 is required in SAT:

-1 32 2 3 4 5 6 7 8 9 10 17 19 23 25 27 28 1 1 5 1 11 1 6 5 5 6 4 1 9 1 1 2 2 2 3 3 3 4 4 4 7 7 9 9 10 10 0

-1 is just to identify a special clause made for nonrenewable resources;

32 is the resource amount;

The first set of numbers, from 2, 3, 4, … 27, 28 are the activity-modes numbers

The second set of numbers, from 1, 1, 5, …, 9, 1, 1 are the amount of each activity mode

The third set of numbers, from 2, 2, 2, … 9, 10, 10 are the numbers of original activities

Note that without the third set of numbers, the information of the original activity in this type of clause, the restriction N1 could not be removed using only the information on one clause.

Scheduling a SAT+RCPSP instance

Solution encoding:

Is an activity-mode-list (1, 2, 3, ..., 32), instead of an activity-list and a mode assignment, normally done in MRCPSP: ((1, 2, ..., 12),(1,1, ..., 1))

Activity-mode-list does not contain invalid solutions:

For instance, activity 5 cannot be realized in mode 1, so the solution presented for activity-list and mode assignment, is invalid.

In activity-mode-list the SAT will force the values of activity-modes that cannot be realized, or became impossible due previous assignments, turning all solutions into valid ones.

The SAT procedure is an exact one, based on DPLL, if the mode assignment is too complex, we stop the exact procedure and start an heuristic one, to try to find a mode assignment, for a while. If the mode assignment cannot be found, the schedule is done but with a penalty on the makespan.

Assignment with sequential activity-mode-list:

1, 2, -3, -4, 5, -6, -7, 8, -9, -10, -11, 12, -13, 14, -15, -16, 17, -18, -19, -20, -21, 22, 23, -24, -25, -26, 27, -28, 29, -30, -31, 32

N2, after variable 2 assigned:

31≥(1v5+11v6+1v7 )+(6v8+5v9+5v10 )+(6v17+4v19 )+(1v23+9v25 )+(1v27+1v28 )

(maximal value is 33)

N2, after variable 5 assigned:

30≥(6v8+5v9+5v10 )+(6v17+4v19 )+(1v23+9v25 )+(1v27+1v28 )

(maximal value is 22, is less than 30)

Rules:

Add OR-precedence relations to the activities that satisfy:

(act+K1)%K2==0

Add BI-directional we use an identical rule

Activity D have a OR-precedence relation:

Activity D is transformed to a dummy activity;

Activities DA, DB, DC are created, duplicating activity D;

The realization of activity D, implies to realize one and only one activity: DA, DB and DC.

Activities E and F have a Bi-directional relation:

Added 6 activities:

EF1/2 - is the changeover times activity;

E1, F1 - duplicate of activities E and F, with the order E » F;

E2, F2 - duplicate of activities E and F, with the order F » E.

Using (M)RCPSP instances to create OR-precede relations and BI-directional relations instances

In a RCPSP or MRCPSP instance:

1. Select a number of activities, to make all its precedence relations as OR precedence relations (like in activity D);

2. Select a number of activities with AND precedence relations, and select one of its preceding activity, and make it as a bi-directional precedence relation (like activity E and F).

Step 1 does not produce any violation, but is done only if the selected activity is not a dummy one. Step 2 does not produce any violation, if the activities are inserted between the maximal activity that is preceding activity B, and the minimal activity that is succeeding activity A, assuming a transformation of a precedence of A over B.

Example MRCPSP: j103_4.mm

Using: K1=1 and K2=16 » first activity transformed is 15

Three precedence relations, to activities 5, 6 and 7, three more activities are created: 15, 16, 17 (old activity 15 became activity 18)

The next activity that satisfy the condition (act+K1)%K2==0, with K1=1 and K2=16, is 31

The activity has 9 precedence relations, adding 9 activities.

The clauses forcing the original activity modes are maintain:

1 14 18 19 0

2 -14 -18 -19 0

1 30 40 0

1 -30 -40 0

The clauses forcing OR precedence relation in the new activity 18, are:

1 18 -15 0

1 18 -16 0

1 18 -17 0

1 -18 15 16 17 0

1 -18 -15 -16 0

1 -18 -15 -17 0

1 -18 -16 -17 0

The same set of clauses is done for activity 31, transformed in 40, but for 9 precedence relations:

1 40 -31 0

1 40 -32 0

1 40 -33 0

1 40 -34 0

1 40 -35 0

1 40 -36 0

1 40 -37 0

1 40 -38 0

1 40 -39 0

1 -40 31 32 33 34 35 36 37 38 39 0

1 -40 -31 -32 0

1 -40 -31 -33 0

1 -40 -31 -34 0

1 -40 -31 -35 0

1 -40 -31 -36 0

1 -40 -31 -37 0

1 -40 -31 -38 0

1 -40 -31 -39 0

1 -40 -32 -33 0

1 -40 -32 -34 0

1 -40 -32 -35 0

1 -40 -32 -36 0

1 -40 -32 -37 0

1 -40 -32 -38 0

1 -40 -32 -39 0

1 -40 -33 -34 0

1 -40 -33 -35 0

1 -40 -33 -36 0

1 -40 -33 -37 0

1 -40 -33 -38 0

1 -40 -33 -39 0

1 -40 -34 -35 0

1 -40 -34 -36 0

1 -40 -34 -37 0

1 -40 -34 -38 0

1 -40 -34 -39 0

1 -40 -35 -36 0

1 -40 -35 -37 0

1 -40 -35 -38 0

1 -40 -35 -39 0

1 -40 -36 -37 0

1 -40 -36 -38 0

1 -40 -36 -39 0

1 -40 -37 -38 0

1 -40 -37 -39 0

1 -40 -38 -39 0

**1. Run without OR-precedence relations and Bi-directional relations:**

Check if our procedure is close to the state-of-the-art in MRCPSP instance sets

2. Run with different density of OR-precedence relations:

Quantify the increase needed on the number of activities

Quantify the gain in makespan by consider OR-precedence relations, relative to treat those precedence relations as AND-precedence relations

3. Run with bi-directional relations.

Check if our procedure is close to the state-of-the-art in MRCPSP instance sets

2. Run with different density of OR-precedence relations:

Quantify the increase needed on the number of activities

Quantify the gain in makespan by consider OR-precedence relations, relative to treat those precedence relations as AND-precedence relations

3. Run with bi-directional relations.

**Conclusions and Future Work**

MMLIB results

Preliminary results:

Infeasibility:

MMLIB+: resource structure (cannot have resources with more than 127 units): solved.

MMLIB 50/100: SAT backtracks limit reached: solved.

Using an heuristic (GSAT);

If still not solved, using a penalty in the makespan.

New results:

OR-precedence relations results

Instance size increase

Instances greater than 900 activity-modes, are not processed due data structure restrictions.

Makespan variation

Results from V. Van Peteghem, M. Vanhoucke / European Journal of Operational Research xxx (2013) xxx–xxx

Solutions

**MRCPSP using RCPSP and SAT solvers**

Coelho, J. and Vanhoucke, M. (2011). Multi-mode resource-constrained project scheduling using RCPSP and SAT solvers. European Journal of Operational Research, 213:73–82.

Appendix A. A simple SAT instance with a conflict generation,

backtracking step and learning clause

GSAT

If the number of backtracks in SAT is too high, GSAT starts

This problem was verified in 17% of the MMLIB50 and MMLIB100 instances, but not in MMLIB+ neither in PSPLIB

It is a heuristic procedure, that try all swaps of activity-modes, in activities involved on non-renewable resource clauses;

Select the swap that results in a greater reduction of conflicts;

Options done, not optimized:

The assigned variables from SAT are kept;

Only one iteration is done in GSAT: even if the number of conflicts are reduced, there are no more iterations, the solution is returned;

When returning a solution with conflicts, the solution value have a penalty of 1000 plus the resource violation;

We assuming that the meta heuristic will reduce the penalty (number of conflicts), leading the search to the feasible space;

All instances in MMLIB50 and MMLIB100 are solved with 5000 schedules limit, with these options.

Transformation of RCPSP instance in SAT+RCPSP

j3010_8.sm

Optimal solution found:

Example RCPSP: j3010_8.sm

Add OR-precedence relations to the activities that satisfy: (act+K1)%K2==0, with K1=3 and K2=10

The first activity to satisfy the expression is activity number 7, since (7+3)%10==0

Only one precedence relation: nothing to do

The next activity that satisfies the expression, is activity 17, that have two precedence relations, to activity 7 and 14.

Inserted two new activities, 17 and 18 (old activity 17 became a dummy one: 19)

SAT causes inserted:

1 17 18 0

1 -17 -18 0

The next activity is now the activity 27, that have two precedence relations, to activities 13 and 20, so two new activities are also inserted, 27 and 28, and also the clauses in SAT:

1 27 28 0

1 -27 -28 0

Solution

makespan 54

makespan 52

MRCPSP results (MMLIB)

PSPLIB, RCPSP results

Number of total activities, pass in the worst case, from 120 to 338 activities;

Makespan with OR-precedence relations could improve up to 20%;

The number of instances that became worst, decrease with the increase of CPU time;

The SAT+RCPSP approach, can model these type of precedence relation for RCPSP instances.

BI-directional precedence relations results

PSPLIB, RCPSP results:

Number of total activities, pass in the worst case, from 120 to 470 activities;

Makespan with BI-directional precedence relations could improve also up to 20%;

The number of instances that became worst, decrease with the increase of CPU time;

The SAT+RCPSP approach, can model these type of precedence relation for RCPSP instances.

Error:

B precedes F, but in F1 it need to wait for the EF activity also

G is sucessor of E, but in the E1 it need to wait the EF activity also

Adding Bi-directional precedence relations

Using K1=2 and K3=10

First activity is 8, since (8+2)%10==0

It have a precedence relation with activity 4

There are added 6 activities (5 to 10):

The clauses added:

1 5 -7 0

1 -5 7 0

1 5 -9 0

1 -5 9 0

5, 7 and 9, will be equal

1 10 -8 0

1 -10 8 0

1 10 -6 0

1 -10 6 0

6, 8, and 10, will be equal

1 5 10 0

1 -5 -10 0

5 or 10 will be realized, the other not

makepsan 45

**Proposed an approach to solve the RCPSP with logical constraints:**

OR precedence relations;

BI-directional precedence relations;

The method uses an extension of multi-mode, where the realization of each activity-mode is controlled by SAT, with more flexibility over the MRCPSP procedures, and the schedule is done by a RCPSP procedure

The method, applied to MRCPSP instances, reveal to be competitive.

Future work we plan:

Study these type of logical constraints without resources, and with multiple mode;

Study mode identity constraints in multiple mode.

OR precedence relations;

BI-directional precedence relations;

The method uses an extension of multi-mode, where the realization of each activity-mode is controlled by SAT, with more flexibility over the MRCPSP procedures, and the schedule is done by a RCPSP procedure

The method, applied to MRCPSP instances, reveal to be competitive.

Future work we plan:

Study these type of logical constraints without resources, and with multiple mode;

Study mode identity constraints in multiple mode.

**using multi-mode**