RCPSPR

RCPSPR resolution from an RCPSP solution

This web page provide a full description of an RCPSPR example and the results introduced in:

Philippe Lacomme, Aziz Moukrim, Alain Quilliot, Marina Vinot. A New Shortest Path Algorithm to Solve the Resource-Constrained Project Scheduling Problem with Routing from a Flow Solution. Engineering Applications of Artificial Intelligence, Volume 66, Issue C, Pages 75-86.

Detailed Example...

Instances.

Widget Instances

30 Activities Instances

Instances informations For the widget instances with 6 activities, the location of the activities in the instances can be divided into 2 configurations:

Uniform configuration LMQV_U	Cluster configuration LMQV_C

For the instances with 30 activities, the location of the activities in the instances can be divided into 3 configurations:

Uniform configuration LMQV_U	Cluster configuration LMQV_C	Cluster Center configuration LMQV_CC

Detailed Solutions.

Sum up of all results for the widget instances BSF: the best found solution
TT: the total CPU time in seconds
Nb_opt: the number of optimal solution reach over the 10 flows
Gap: the gap in percent between the BFS of CPLEX and the BFS of CPLEX

	CPLEX		Shortest path algorithm
Instances	BFS	TT	BFS	Nb_opt	TT	Gap
LMQV_U1	101.5	46.6	101.5	10/10	10.6	0.00
LMQV_U2	198.5	37.2	198.7	9/10	10.2	0.09
LMQV_U3	246.6	29.0	246.6	10/10	11.9	0.0
LMQV_U4	123.3	31.0	123.3	10/10	3.6	0.0
LMQV_U5	247.1	32.3	247.1	10/10	4.3	0.0
LMQV_U6	288.1	34.5	288.1	10/10	7.0	0.0
LMQV_U7	128.4	9.9	128.4	10/10	2.2	0.0
LMQV_U8	261.1	9.3	261.1	10/10	2.4	0.0
LMQV_U9	276.1	9.2	276.1	10/10	2.5	0.0
LMQV_C1	78.6	11.1	78.6	10/10	0.0	0.0
LMQV_C2	135.6	9.0	135.6	10/10	0.0	0.0
LMQV_C3	160.6	10.0	160.6	10/10	0.0	0.0
LMQV_C4	45.2	10.5	45.3	9/10	21.1	0.0
LMQV_C5	92.0	12.2	92.3	9/10	25.8	0.0
LMQV_C6	94.6	12.2	94.8	9/10	24.6	0.0
LMQV_C7	66.4	5.6	66.4	10/10	6.3	0.0
LMQV_C8	132.6	5.2	132.6	10/10	10.2	0.0
LMQV_C9	136.7	5.7	136.7	10/10	5.2	0.0
Average:		17.8		9.99/10	8.2	0.04

	Shortest path algorithm
Instances	BFS φ₁	BFS φ₂	BFS φ₃	BFS φ₄	BFS φ₅	BFS φ₆	BFS φ₇	BFS φ₈	BFS φ₉	BFS φ₁₀	Avg BFS
LMQV_U1	95	115	87	117	96	99	86	105	102	113	101.5
LMQV_U2	187	228	170	232	188	192	167	204	197	222	198.7
LMQV_U3	227	262	228	269	245	238	235	270	233	259	246.6
LMQV_U4	115	115	137	120	116	112	121	131	127	138	123.3
LMQV_U5	228	229	274	242	234	224	246	261	254	279	247.1
LMQV_U6	263	272	319	280	262	264	284	299	292	346	288.1
LMQV_U7	111	111	111	127	139	138	151	124	137	135	128.4
LMQV_U8	225	225	225	261	282	280	307	253	279	274	261.1
LMQV_U9	258	258	258	279	284	292	306	270	266	290	276.1
LMQV_C1	89	89	89	83	70	82	72	71	71	70	78.6
LMQV_C2	156	156	156	145	118	142	123	121	120	119	135.6
LMQV_C3	181	181	181	170	143	167	148	146	145	144	160.6
LMQV_C4	44	45	40	46	44	45	45	44	49	51	45.3
LMQV_C5	92	93	81	92	87	89	90	92	100	107	92.3
LMQV_C6	94	95	82	96	91	93	94	94	101	118	94.8
LMQV_C7	60	66	66	71	58	65	77	78	62	61	66.4
LMQV_C8	125	135	135	140	112	128	153	152	122	124	132.6
LMQV_C9	128	138	138	145	117	133	158	157	127	126	136.7

Each Solution link gives access to one file composed of 4 parts, the example below corresponds to the solution of the instance LMQV_C2:
The first part gives the makespan of the solution, the number of activities and the number of available resources of the resource.

The second part contains the information on the scheduling with for each activity the resource requirement, the duration and the earliest starting time ES in the solution.

The third part concerns the flow with the transfer from an activity (row) to another (column) and the quantity of resources associated.

The fourth part gives all the details of the routing of the solution with the number of transport operation in each trip Nb_Op_T_Trip x and the details of each trip.
Each trip is detailed with all the transport operation from one activity (origin) to another (destination), with the quantity of resources transported, the duration of the transport operation and the pickup / delivery dates.

All solution of the widget instances in a .zip file:

Sum up of all results for the 30 activities instances

		Shortest path algorithm
Instances	RCPSP Solution	BFS	TT	Solution
LMQV_J30_U1	96	250	80.4
LMQV_J30_U2	105	276	697.0
LMQV_J30_U3	82	129	5.3
LMQV_J30_C1	113	221	729.0
LMQV_J30_C2	81	231	336.9
LMQV_J30_C3	83	139	32.9
LMQV_J30_CC1	103	271	270.3
LMQV_J30_CC2	108	270	305.6
LMQV_J30_CC3	100	158	89.9
Average:			283.0

All solution of the instances with 30 activities in a .zip file: