他のいくつかの質問 (累積の使用 、累積によるセットアップ時間の表現) を通じて、 の使用に関する優れたフィードバックcumulativesと、最適なソリューションに到達するための検索を支援する方法について得ました。
ただし、これらの質問では、単純化されたおもちゃの例のみを使用しました.
より大きな問題に移ると、最適解にたどり着くのに苦労します。
要するに、以下が適用される特定のマシンセットでスケジュールするタスクがあります。
- 各タスクには 1 ～ 1000 のランダムな期間があります
- タスクの約 20% はグローバル リソースを消費できます。つまり、同じリソースを使用する他のタスクを同時にスケジュールすることはできません。
- タスクの約 20% は、使用可能なすべてのマシンで実行できません。
元：
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
この小さな例では、5 台のマシンで 20 個のタスクをスケジュールします。したがって、t4、t7、t15 使用リソース r1 は、異なるマシンでスケジュールされていても、同時に実行することはできません。t4、t15、t16、t20 は r2 などを使用します。t3 は m3 と m4 でのみ実行でき、t4 は m2 と m3 でのみ実行できます。
完全なモデルを次に示します。
:- 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).
これまでのところ、私の最善のヒューリスティックは、MachineId 変数を次の順序で並べることです。最初に多くのリソースを使用するタスクごとに並べ替え、次に特定のマシンでのみ実行可能なタスクごとに並べ替え、最後に残りを並べ替えます。
| ?- 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 ?
より良い動作をする可能性のある、より良い検索ヒューリスティックおよび/または対称性の破れの提案はありますか?