I have through several other questions (Use of cumulatives, Expressing setup time with cumulatives) got excellent feedback on use of cumulatives, and how to help the search to achieve reach an optimal solution.
However in those questions I only used a simplified toy example.
When I move over to lager problems I still struggle to reach optimal solutions.
In short I have tasks to schedule on a give set of machines where the following applies:
- Each task has a random duration from 1-1000
- Around 20% of the tasks can consume a global resource which means that no other task using the same resource can be scheduled at the same time.
- Around 20% of the tasks can not be executed on all available machines.
Ex:
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 task to be scheduled on 5 machines. t4, t7, t15 use resource r1 can therefor not be executed at the same time even if they are scheduled on different machines. t4, t15, t16, t20 use r2 etc. t3 can only run on m3 and m4, t4 only on m2 and m3 etc.
A complete model is given here:
:- 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 heuristics so far has been to order the MachineId variable in the following order: First by task using many resources, then by task only executable on some machine, then the rest.
| ?- 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 of a better search heuristic and/or symmetry breaking that could behave better?
