Ascend FD-23R Manual do Utilizador descarregar pdf (Página 43)

2.3. More Complex Examples 31

noOverlaps T1 T2 = true <== precedes T2 T1

A task is modelled (via the type task) as a 5-tuple which holds its name, du-

ration, list of precedence tasks, list of required resources, and the start time. Two

functions for accessing the start time and duration of a task are provided (start and

duration, respectively) that are used by the function precedes. This last function

imposes the precedence constraint between two tasks. The function requireList im-

poses the constraints for tasks requiring resources, i.e., if two diﬀerent tasks require the

same resource, they cannot overlap. The function noOverlaps states that for two non

overlapping tasks t1 and t2, either t1 precedes t2 or vice versa. The main function is

schedule, which takes three arguments: a list of tasks to be scheduled, the scheduling

start time, and the maximum scheduling ﬁnal time. These last two arguments repre-

sent the time window that has to ﬁt the scheduling. The time window is imposed via

domain pruning for each task’s start time (a task cannot start at a time so that its du-

ration makes its end time greater than the end time of the window; this is imposed with

the function horizon). The function scheduleTasks imposes the precedence and re-

quirement constraints for all of the tasks in the scheduling. Precedence constraints and

requirement constraints are imposed by the functions precedeList and requireList,

respectively.

With this model, we can declare for example a function that deﬁnes the solution

to the problem.

sched :: startType -> startType -> startType -> startType ->

startType -> startType -> bool

sched S1 S2 S3 S4 S5 S6 :-

Tasks == [(t1,3,[t5,t6],[m1],S1),

(t2,8,[],[m1],S2),

(t3,8,[],[m1],S3),

(t4,6,[t3],[m2],S4),

(t5,3,[t3],[m2],S5),

(t6,4,[],[m2],S6)],

schedule Tasks 1 20,

labeling [ff] [S1,S2,S3,S4,S5,S6]

where Tasks deﬁnes the set of tasks. Observe that the problem for a possible scheduling

is limited to time window (1,20) by the sub-goal schedule Tasks 1 20. A solving in the

command line:

TOY(FD)> sched S1 S2 S3 S4 S5 S6

yes

S1 == 1

S2 == 4

S3 == 12

S4 == 1

1 2 ... 38 39 40 41 42 43 44 45 46 47 48 ... 80 81

Sem comentários

Ascend FD-23R Manual do Utilizador Página 43