Finding heuristics for cumulative
I have several other questions ( Using Cumulative , Expression of Installation Time with Cumulative ), got great feedback on usage cumulatives
and how to help the search to reach an optimal solution.
However, I only used a simplified toy example in these questions.
When I get down to lager problems, I still try to reach optimal solutions.
In short, I have scheduled tasks on a set of commands where the following applies:
- Each task has a random duration from 1 to 1000
- About 20% of tasks can consume a global resource, which means that no other task using the same resource can be scheduled at the same time.
- About 20% of tasks cannot be completed on all available machines.
Example:
Task| Dur | Exe on | Resources
------+------+----------+----------
t1 | 318 | All |
t2 | 246 | All |
t3 | 797 | m4 m3 |
t4 | 238 | m2 m3 | r1 r2 r3
t5 | 251 | m1 |
t6 | 279 | All |
t7 | 987 | m2 m5 m1 | r1
t8 | 847 | All |
t9 | 426 | All |
t10 | 787 | All |
t11 | 6 | All |
t12 | 681 | All |
t13 | 465 | All |
t14 | 46 | All |
t15 | 3 | All | r1 r3 r2
t16 | 427 | All | r3 r2
t17 | 956 | All | r3
t18 | 657 | All |
t19 | 113 | All |
t20 | 251 | All | r3 r2
In this small example, we have 20 tasks planned to be scheduled on 5 machines. t4, t7, t15 use resource r1 may not run concurrently, even if they are scheduled on different machines. t4, t15, t16, t20 use r2 etc. t3 can only work on m3 and m4, t4 only on m2 and m3, etc.
Here's the complete model:
:- use_module(library(clpfd)).
:- use_module(library(lists)).
s1(Ss, Es, Ms, Maxspan, Timeout ) :-
Ss = [S1,S2,S3,S4,S5,S6,S7,S8,S9,S10,S11,S12,S13,S14,S15,S16,S17,S18,S19,S20],
Es = [E1,E2,E3,E4,E5,E6,E7,E8,E9,E10,E11,E12,E13,E14,E15,E16,E17,E18,E19,E20],
Ms = [M1,M2,M3,M4,M5,M6,M7,M8,M9,M10,M11,M12,M13,M14,M15,M16,M17,M18,M19,M20],
Ds = [318, 246, 797, 238, 251, 279, 987, 847, 426, 787,6, 681,465,46, 3, 427,956,657,113,251],
Ds = [D1,D2,D3,D4,D5,D6,D7,D8,D9,D10,D11,D12,D13,D14,D15,D16,D17,D18,D19,D20],
domain(Ss, 1, 10000),
domain(Es, 1, 10000),
domain(Ms, 1, 5),
%task( StartTime, Duration, EndTime, ResourceCons, MachineId)
Tasks = [
task( S1, D1, E1, 1, M1),
task( S2, D2, E2, 1, M2),
task( S3, D3, E3, 1, M3),
task( S4, D4, E4, 1, M4),
task( S5, D5, E5, 1, M5),
task( S6, D6, E6, 1, M6),
task( S7, D7, E7, 1, M7),
task( S8, D8, E8, 1, M8),
task( S9, D9, E9, 1, M9),
task(S10, D10,E10, 1,M10),
task(S11, D11,E11, 1,M11),
task(S12, D12,E12, 1,M12),
task(S13, D13,E13, 1,M13),
task(S14, D14,E14, 1,M14),
task(S15, D15,E15, 1,M15),
task(S16, D16,E16, 1,M16),
task(S17, D17,E17, 1,M17),
task(S18, D18,E18, 1,M18),
task(S19, D19,E19, 1,M19),
task(S20, D20,E20, 1,M20)
],
%machine( Id, ResourceBound ),
Machines = [
machine( 1, 1),
machine( 2, 1),
machine( 3, 1),
machine( 4, 1),
machine( 5, 1)
],
%Set up constraints where task can only run on spesific machines:
%t3 can only run on m3 and m4
%t4 can only run on m2 and m3
%t5 can only run on m1
%t7 can only run on m1, m2 and m5
%all other can run on any machine
list_to_fdset( [3,4], T3RunOn ),
list_to_fdset( [2,3], T4RunOn ),
list_to_fdset( [1], T5RunOn ),
list_to_fdset( [1,2,5],T7RunOn ),
M3 in_set T3RunOn,
M4 in_set T4RunOn,
M5 in_set T5RunOn,
M7 in_set T7RunOn,
%Set up constraints of tasks using global resources:
%t4 use r1,r2,r3
%t7 use r1
%t15 use r1,r2,r3
%t16 use r2,r3
%t17 use r3
%t20 use r2,r3
%r1:
cumulative(
[
task( S4, D4, E4,1,4),
task( S7, D7, E7,1,7),
task( S15,D15,E15,1,15)
],
[limit(1)]),
%%r2:
cumulative(
[
task( S4, D4, E4,1,4),
task( S15,D15,E15,1,15),
task( S20,D20,E20,1,20)
],
[limit(1)]),
%r3:
cumulative(
[
task( S4, D4, E4,1,4),
task( S15,D15,E15,1,15),
task( S16,D16,E16,1,16),
task( S17,D17,E17,1,17),
task( S20,D20,E20,1,20)
],
[limit(1)]),
maximum( Maxspan, Es ),
cumulatives(Tasks, Machines, [bound(upper), task_intervals(true)] ),
%Plain order (M1,M2,...M20)
%MOrder=Ms,
%Order by task using many resources first, then task only runnon on some machines, then rest
MOrder=[M4, M15, M16, M20, M7, M17, M5, M3, M10, M1, M2, M6, M8, M9, M11, M12, M13, M14, M18, M19],
%Order by duration
%MOrder=[M15, M11, M14, M19, M4, M2, M20, M5, M6, M1, M9, M16, M13, M18, M12, M10, M3, M8, M17, M7],
%This order (discovered my misstake) gives optimal sollution in less then a second:
%MOrder=[M4, M15, M20, M16, M17, M5, M3, M7, M10, M1, M2, M6, M8, M9, M11, M12, M13, M14, M18, M19],
append([MOrder, Ss ], Vars),
labeling([ minimize(Maxspan), time_out( Timeout, _LabelingResult) ], Vars).
My best heuristic so far has been to order the MachineId variable in the following order: First by job, using a lot of resources, then by job only executable on some machine, then others.
| ?- s1(Ss, Es, Ms, Maxspan, 5000 ). Ss = [1,319,1,1635,1635,798,565,1,848,1077,1552,1,1274,1558,1886,1,428,682,1739,1384], Es = [319,565,798,1873,1886,1077,1552,848,1274,1864,1558,682,1739,1604,1889,428,1384,1339,1852,1635], Ms = [2,2,3,2,1,3,2,4,4,3,2,5,4,2,1,1,1,5,4,1], Maxspan = 1889 ?
Any suggestions for better heuristic search and / or symmetry breaking that might behave better?
source to share
No one has answered this question yet
See similar questions:
or similar: