使用逻辑编程调度具有共享资源的任务
Scheduling tasks with shared resources using logic programming
Time 5, 3, 8, 2, 7, 3, 9, 3, 3, 5, 7
你必须安排玩家（使用时间）去三个不同的淋浴。获得最佳解决方案。
到目前为止，我的解决方案是：
use_module(library(clpfd)).
shower(S, E, D, Done) :-
D = [5, 3, 8, 2, 7, 3, 9, 3, 3, 5, 7],
R = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
length(D, N),
length(S, N),
length(E, N),
domain(S, 0, 100),
domain(E, 0, 100),
Done in 0..100,
ready(E, Done),
tasks(S, D, E, R, Tasks),
cumulative(Tasks, [limit(3)]),
labeling([minimize(Done)], [Done|S]).
tasks([], [], [], [], []).
tasks([S|Ss], [D|Ds], [E|Es], [R|Rs], [T|Ts]) :-
T = task(S, D, E, R, 0),
tasks(Ss, Ds, Es, Rs, Ts).
ready([], _).
ready([E|Es], Done) :-
Done #>= E,
ready(Es, Done).
如果我运行程序：
?- shower(S,D).
它将打印：
D = 19,
S = [0,0,0,3,5,5,8,8,11,14,12]
Done是总时间（最大时间），S是每个任务的开始时间，E是每个任务的结束时间，D是任务的持续时间。
到目前为止，还不错。
但现在，我正在为其他事情苦苦挣扎。准确地说：
1) 我怎样才能同时打印哪个玩家正在使用哪个淋浴器？
2) 我怎样才能限制一次淋浴最多 运行 四名玩家？
我是 Prolog 的新手，这很可能是我用它编写的最后一个程序。到目前为止我设法做到了这一点，但我需要完成这个（你猜对了，这是一项任务）。这是我在这门课程中必须做的最后一件事，而且我之前从未做过任何约束逻辑编程。
感谢阅读并最终回复！
好问题，+1！
这里有一种解决方法：假设你已经找到满足资源限制的时间表。然后，您只需描述必须附加的内容，以便可以以所需的方式将任务分配给机器。
例如：
distribution(Starts, Ends, Machines) :-
pairs_keys_values(Pairs, Starts, Ends),
length(Ms0, 4),
maplist(=(0-[]), Ms0),
foldl(task_machines0_machines, Pairs, Ms0, Ms1),
pairs_values(Ms1, Machines0),
maplist(reverse, Machines0, Machines1),
msort(Machines1, Machines).
task_machines0_machines(Start-End, Ms0, [End-[Start|Starts]|Ms1]) :-
Start #>= OccupiedUntil,
select(OccupiedUntil-Starts, Ms0, Ms1),
L #=< 2,
length(Starts, L).
Machines 包含每台机器的一个列表，其中每个列表依次包含分配给该机器的任务的开始时间。
我将更准确地识别任务作为一个简单的练习。
示例用法及其结果：
?- shower(Starts, Ends, _, _), distribution(Starts, Ends, Machines).
Starts = [0, 0, 0, 1, 2, 3, 0],
Ends = [3, 3, 1, 2, 3, 4, 4],
<b>Machines = [[0], [0], [0, 1, 2], [0, 3]]</b> .
让我们看看在 4 个时隙的总持续时间内有多少独特的解决方案，由于资源限制，我们已经知道这是最小值：
?- setof(Ms, Starts^Ends^Ds^(shower(Starts, Ends, Ds, 4),
distribution(Starts, Ends, Ms)),
Mss),
length(Mss, L).
Mss = [[[0], [0, 1], [0, 3], [0, 3]], ...]
<b>L = 14.</b>
这是实际唯一解决方案数量的下限，如果我们考虑唯一任务标识符而不是开始时间，我们只能计算它。
我已经这样做并找到了 20 种方法 来分配受所有限制的任务，可互换地使用机器：
distributions([
[[1],[2,3],[4,5,6],[7]], [[1],[2,4],[3,5,6],[7]], [[1],[2,5],[3,4,6],[7]],
[[1],[2,6],[3,4,5],[7]], [[1,3],[2],[4,5,6],[7]], [[1,3],[2,4],[5,6],[7]],
[[1,3],[2,5],[4,6],[7]], [[1,3],[2,6],[4,5],[7]], [[1,4],[2],[3,5,6],[7]],
[[1,4],[2,3],[5,6],[7]], [[1,4],[2,5],[3,6],[7]], [[1,4],[2,6],[3,5],[7]],
[[1,5],[2],[3,4,6],[7]], [[1,5],[2,3],[4,6],[7]], [[1,5],[2,4],[3,6],[7]],
[[1,5],[2,6],[3,4],[7]], [[1,6],[2],[3,4,5],[7]], [[1,6],[2,3],[4,5],[7]],
[[1,6],[2,4],[3,5],[7]], [[1,6],[2,5],[3,4],[7]]
]).
如果您使用 cumulatives/[2,3] 约束而不是 cumulative/1 约束，那么您将获得为 'free' 分配的机器。
通过使用cumulatives，可以为每台机器分配单独的资源容量。
这表明您的问题已通过 cumulatives:
解决
:- use_module(library(clpfd)).
:- use_module(library(lists)).
go( Ss, Es, Ms) :-
Ss = [S1, S2, S3, S4,S5,S6,S7], %Starttimes
Es = [E1, E2, E3, E4,E5,E6,E7], %Endtimeds
Ms = [M1, M2, M3, M4,M5,M6,M7], %MachineIds
domain(Ss, 0, 10),
domain(Es, 0, 10),
domain(Ms, 1, 4),
Tasks = [
task( S1, 3, E1, 1, M1 ),
task( S2, 4, E2, 1, M2 ),
task( S3, 1, E3, 1, M3 ),
task( S4, 1, E4, 1, M4 ),
task( S5, 1, E5, 1, M5 ),
task( S6, 1, E6, 1, M6 ),
task( S7, 4, E7, 1, M7 )
],
%All machines has resource capacity = 1
Machines = [
machine( 1, 1 ),
machine( 2, 1 ),
machine( 3, 1 ),
machine( 4, 1 )
],
cumulatives(Tasks, Machines, [bound(upper)] ),
maximum( MaxEndTime, Es ),
%The variables to lable:
append([Ms, Ss ], Vars),
labeling( [minimize(MaxEndTime)], Vars).
启动后您将获得：
| ?- go( Ss, Es, Ms) .
Ss = [0,0,3,0,1,2,0],
Es = [3,4,4,1,2,3,4],
Ms = [1,2,1,3,3,3,4] ?
如您所见：
任务 1 分配给机器 1，开始时间为 0
任务 2 分配给机器 2，开始时间为 0
任务 3 分配给机器 1，开始时间为 3
.
.
@MortenM
我对你的代码做了一些修改，使它更适合我的限制（基本上，不同的任务花费时间 - 就像我在原始规范中添加的第四台机器 - 更重要的是，任务开始于时间 0，而不是时间 1）。代码现在看起来：
go( Ss, Es, Ms) :-
Ss = [S1, S2, S3, S4,S5,S6,S7], %Starttimes
Es = [E1, E2, E3, E4,E5,E6,E7], %Endtimeds
Ms = [M1, M2, M3, M4,M5,M6,M7], %MachineIds
domain(Ss, 0, 20),
domain(Es, 0, 20),
domain(Ms, 1, 10),
%All task has duration = 1
Tasks = [
task( S1, 3, E1, 1, M1 ),
task( S2, 3, E2, 1, M2 ),
task( S3, 1, E3, 1, M3 ),
task( S4, 1, E4, 1, M4 ),
task( S5, 1, E5, 1, M5 ),
task( S6, 1, E6, 1, M6 ),
task( S7, 4, E7, 1, M7 )
],
%All machines has resource capacity = 1
Machines = [
machine( 1, 1 ),
machine( 2, 1 ),
machine( 3, 1 ),
machine( 4, 1)
],
cumulatives(Tasks, Machines, [bound(upper)] ),
maximum( MaxEndTime, Es ),
%The variables to lable:
append([Ms, Ss ], Vars),
labeling( [minimize(MaxEndTime)], Vars).
而当我运行它时，结果（正确结果）是：
?- go(Ss,Es,Ms).
Ss = [0,0,3,3,0,1,0],
Es = [3,3,4,4,1,2,4],
Ms = [1,2,1,2,3,3,4] ?
唯一的问题是程序没有给我其他解决方案。这不是唯一的解决方案，但看起来程序只能找到这个解决方案。不知道为什么或如何改变它。
非常感谢，你是救星。
注意：我在您做出最终更改之前post做了这个:)
我修改了你的代码，因为我使用的是 SWI-prolog...
:- use_module(library(clpfd)).
shower(Durations, NumMachines, Starts, Done) :-
sum_list(Durations, Max),
Done in 0..Max,
maplist(task(Max, Done), Durations, Tasks, Starts),
cumulative(Tasks, [limit(NumMachines)]),
labeling([min(Done)], [Done|Starts]).
task(Max, Done, Duration, task(Start, Duration, End, 1, 0), Start) :-
MaxStart is Max-Duration,
Start in 0..MaxStart,
End #= Start + Duration, %End in 0..Max,
Done #>= End.
也就是说，现在 shower/4 需要持续时间和机器数量，并输出开始时间和最小化完工时间（这应该是合适的术语）。
1 ?- shower([3, 3, 1, 1, 1, 1, 4], 4, S, D).
S = [0, 0, 0, 1, 2, 3, 0],
D = 4 ;
S = [0, 0, 0, 1, 3, 2, 0],
D = 4
...
有很多可能，固定下界
?- aggregate(count,S^shower([1, 1, 1, 1, 3, 3, 4], 4, S, 4),N).
N = 348.
打印全部：
?- forall(shower([1, 1, 1, 1, 3, 3, 4], 4, S, 4), writeln(S)).
简单的机器分配任务：
allocate_machines(Machines, Starts, Durations, Gantt) :-
findall(M-[], member(M, Machines), Pool),
distribute(Starts, Durations, Pool, Gantt).
distribute([], [], Allocated, Allocated).
distribute([S|Ss], [D|Ds], Pool, Allocated) :-
select(M-Duties, Pool, Reduced),
\+ busy(S, Duties),
length(Duties, L), L < 3,
append(Duties, [S/D], Updated),
distribute(Ss, Ds, [M-Updated|Reduced], Allocated).
busy(S, [Sd/Dd|_]) :- S < Sd+Dd, !.
busy(S, [_|Ds]) :- busy(S, Ds).
Time 5, 3, 8, 2, 7, 3, 9, 3, 3, 5, 7
你必须安排玩家（使用时间）去三个不同的淋浴。获得最佳解决方案。 到目前为止，我的解决方案是：
use_module(library(clpfd)).
shower(S, E, D, Done) :-
D = [5, 3, 8, 2, 7, 3, 9, 3, 3, 5, 7],
R = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
length(D, N),
length(S, N),
length(E, N),
domain(S, 0, 100),
domain(E, 0, 100),
Done in 0..100,
ready(E, Done),
tasks(S, D, E, R, Tasks),
cumulative(Tasks, [limit(3)]),
labeling([minimize(Done)], [Done|S]).
tasks([], [], [], [], []).
tasks([S|Ss], [D|Ds], [E|Es], [R|Rs], [T|Ts]) :-
T = task(S, D, E, R, 0),
tasks(Ss, Ds, Es, Rs, Ts).
ready([], _).
ready([E|Es], Done) :-
Done #>= E,
ready(Es, Done).
如果我运行程序：
?- shower(S,D).
它将打印：
D = 19,
S = [0,0,0,3,5,5,8,8,11,14,12]
Done是总时间（最大时间），S是每个任务的开始时间，E是每个任务的结束时间，D是任务的持续时间。
到目前为止，还不错。
但现在，我正在为其他事情苦苦挣扎。准确地说：
1) 我怎样才能同时打印哪个玩家正在使用哪个淋浴器？
2) 我怎样才能限制一次淋浴最多 运行 四名玩家？
我是 Prolog 的新手，这很可能是我用它编写的最后一个程序。到目前为止我设法做到了这一点，但我需要完成这个（你猜对了，这是一项任务）。这是我在这门课程中必须做的最后一件事，而且我之前从未做过任何约束逻辑编程。
感谢阅读并最终回复！
好问题，+1！
这里有一种解决方法：假设你已经找到满足资源限制的时间表。然后，您只需描述必须附加的内容，以便可以以所需的方式将任务分配给机器。
例如：
distribution(Starts, Ends, Machines) :-
pairs_keys_values(Pairs, Starts, Ends),
length(Ms0, 4),
maplist(=(0-[]), Ms0),
foldl(task_machines0_machines, Pairs, Ms0, Ms1),
pairs_values(Ms1, Machines0),
maplist(reverse, Machines0, Machines1),
msort(Machines1, Machines).
task_machines0_machines(Start-End, Ms0, [End-[Start|Starts]|Ms1]) :-
Start #>= OccupiedUntil,
select(OccupiedUntil-Starts, Ms0, Ms1),
L #=< 2,
length(Starts, L).
Machines 包含每台机器的一个列表，其中每个列表依次包含分配给该机器的任务的开始时间。
我将更准确地识别任务作为一个简单的练习。
示例用法及其结果：
?- shower(Starts, Ends, _, _), distribution(Starts, Ends, Machines).
Starts = [0, 0, 0, 1, 2, 3, 0],
Ends = [3, 3, 1, 2, 3, 4, 4],
<b>Machines = [[0], [0], [0, 1, 2], [0, 3]]</b> .
让我们看看在 4 个时隙的总持续时间内有多少独特的解决方案，由于资源限制，我们已经知道这是最小值：
?- setof(Ms, Starts^Ends^Ds^(shower(Starts, Ends, Ds, 4),
distribution(Starts, Ends, Ms)),
Mss),
length(Mss, L).
Mss = [[[0], [0, 1], [0, 3], [0, 3]], ...]
<b>L = 14.</b>
这是实际唯一解决方案数量的下限，如果我们考虑唯一任务标识符而不是开始时间，我们只能计算它。
我已经这样做并找到了 20 种方法 来分配受所有限制的任务，可互换地使用机器：
distributions([
[[1],[2,3],[4,5,6],[7]], [[1],[2,4],[3,5,6],[7]], [[1],[2,5],[3,4,6],[7]],
[[1],[2,6],[3,4,5],[7]], [[1,3],[2],[4,5,6],[7]], [[1,3],[2,4],[5,6],[7]],
[[1,3],[2,5],[4,6],[7]], [[1,3],[2,6],[4,5],[7]], [[1,4],[2],[3,5,6],[7]],
[[1,4],[2,3],[5,6],[7]], [[1,4],[2,5],[3,6],[7]], [[1,4],[2,6],[3,5],[7]],
[[1,5],[2],[3,4,6],[7]], [[1,5],[2,3],[4,6],[7]], [[1,5],[2,4],[3,6],[7]],
[[1,5],[2,6],[3,4],[7]], [[1,6],[2],[3,4,5],[7]], [[1,6],[2,3],[4,5],[7]],
[[1,6],[2,4],[3,5],[7]], [[1,6],[2,5],[3,4],[7]]
]).
如果您使用 cumulatives/[2,3] 约束而不是 cumulative/1 约束，那么您将获得为 'free' 分配的机器。
通过使用cumulatives，可以为每台机器分配单独的资源容量。
这表明您的问题已通过 cumulatives:
:- use_module(library(clpfd)).
:- use_module(library(lists)).
go( Ss, Es, Ms) :-
Ss = [S1, S2, S3, S4,S5,S6,S7], %Starttimes
Es = [E1, E2, E3, E4,E5,E6,E7], %Endtimeds
Ms = [M1, M2, M3, M4,M5,M6,M7], %MachineIds
domain(Ss, 0, 10),
domain(Es, 0, 10),
domain(Ms, 1, 4),
Tasks = [
task( S1, 3, E1, 1, M1 ),
task( S2, 4, E2, 1, M2 ),
task( S3, 1, E3, 1, M3 ),
task( S4, 1, E4, 1, M4 ),
task( S5, 1, E5, 1, M5 ),
task( S6, 1, E6, 1, M6 ),
task( S7, 4, E7, 1, M7 )
],
%All machines has resource capacity = 1
Machines = [
machine( 1, 1 ),
machine( 2, 1 ),
machine( 3, 1 ),
machine( 4, 1 )
],
cumulatives(Tasks, Machines, [bound(upper)] ),
maximum( MaxEndTime, Es ),
%The variables to lable:
append([Ms, Ss ], Vars),
labeling( [minimize(MaxEndTime)], Vars).
启动后您将获得：
| ?- go( Ss, Es, Ms) .
Ss = [0,0,3,0,1,2,0],
Es = [3,4,4,1,2,3,4],
Ms = [1,2,1,3,3,3,4] ?
如您所见： 任务 1 分配给机器 1，开始时间为 0 任务 2 分配给机器 2，开始时间为 0 任务 3 分配给机器 1，开始时间为 3 . .
@MortenM
我对你的代码做了一些修改，使它更适合我的限制（基本上，不同的任务花费时间 - 就像我在原始规范中添加的第四台机器 - 更重要的是，任务开始于时间 0，而不是时间 1）。代码现在看起来：
go( Ss, Es, Ms) :-
Ss = [S1, S2, S3, S4,S5,S6,S7], %Starttimes
Es = [E1, E2, E3, E4,E5,E6,E7], %Endtimeds
Ms = [M1, M2, M3, M4,M5,M6,M7], %MachineIds
domain(Ss, 0, 20),
domain(Es, 0, 20),
domain(Ms, 1, 10),
%All task has duration = 1
Tasks = [
task( S1, 3, E1, 1, M1 ),
task( S2, 3, E2, 1, M2 ),
task( S3, 1, E3, 1, M3 ),
task( S4, 1, E4, 1, M4 ),
task( S5, 1, E5, 1, M5 ),
task( S6, 1, E6, 1, M6 ),
task( S7, 4, E7, 1, M7 )
],
%All machines has resource capacity = 1
Machines = [
machine( 1, 1 ),
machine( 2, 1 ),
machine( 3, 1 ),
machine( 4, 1)
],
cumulatives(Tasks, Machines, [bound(upper)] ),
maximum( MaxEndTime, Es ),
%The variables to lable:
append([Ms, Ss ], Vars),
labeling( [minimize(MaxEndTime)], Vars).
而当我运行它时，结果（正确结果）是：
?- go(Ss,Es,Ms).
Ss = [0,0,3,3,0,1,0],
Es = [3,3,4,4,1,2,4],
Ms = [1,2,1,2,3,3,4] ?
唯一的问题是程序没有给我其他解决方案。这不是唯一的解决方案，但看起来程序只能找到这个解决方案。不知道为什么或如何改变它。
非常感谢，你是救星。
注意：我在您做出最终更改之前post做了这个:)
我修改了你的代码，因为我使用的是 SWI-prolog...
:- use_module(library(clpfd)).
shower(Durations, NumMachines, Starts, Done) :-
sum_list(Durations, Max),
Done in 0..Max,
maplist(task(Max, Done), Durations, Tasks, Starts),
cumulative(Tasks, [limit(NumMachines)]),
labeling([min(Done)], [Done|Starts]).
task(Max, Done, Duration, task(Start, Duration, End, 1, 0), Start) :-
MaxStart is Max-Duration,
Start in 0..MaxStart,
End #= Start + Duration, %End in 0..Max,
Done #>= End.
也就是说，现在 shower/4 需要持续时间和机器数量，并输出开始时间和最小化完工时间（这应该是合适的术语）。
1 ?- shower([3, 3, 1, 1, 1, 1, 4], 4, S, D).
S = [0, 0, 0, 1, 2, 3, 0],
D = 4 ;
S = [0, 0, 0, 1, 3, 2, 0],
D = 4
...
有很多可能，固定下界
?- aggregate(count,S^shower([1, 1, 1, 1, 3, 3, 4], 4, S, 4),N).
N = 348.
打印全部：
?- forall(shower([1, 1, 1, 1, 3, 3, 4], 4, S, 4), writeln(S)).
简单的机器分配任务：
allocate_machines(Machines, Starts, Durations, Gantt) :-
findall(M-[], member(M, Machines), Pool),
distribute(Starts, Durations, Pool, Gantt).
distribute([], [], Allocated, Allocated).
distribute([S|Ss], [D|Ds], Pool, Allocated) :-
select(M-Duties, Pool, Reduced),
\+ busy(S, Duties),
length(Duties, L), L < 3,
append(Duties, [S/D], Updated),
distribute(Ss, Ds, [M-Updated|Reduced], Allocated).
busy(S, [Sd/Dd|_]) :- S < Sd+Dd, !.
busy(S, [_|Ds]) :- busy(S, Ds).