Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

A novel approach to solve various resource-constrained

No description
by

José Coelho

on 7 April 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of A novel approach to solve various resource-constrained

A novel approach to solve various resource-constrained
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.

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.

using multi-mode
Full transcript