Information Technology Reference
In-Depth Information
Domains: Each period is a certain time on a certain day. A period can be encoded
as a number:
(
×
)+
24
hr
.
clock
. So, for example, for Monday at 9am, the
period would be 109; for Tuesday at 2pm, it would be 214; and for Friday at 4pm,
it would be 516.
Constraints: The five chosen periods must be available (not already taken), non-
consecutive, and with no more than two per day. In addition (although it is not
stated explicitly), the five periods must all be distinct.
100
day
The following generates five available periods:
% P1,P2,P3,P4,P5 are five distinct available periods.
uniq_periods(P1,P2,P3,P4,P5) :-
per(P1), per(P2), per(P3), per(P4), per(P5),
\+ P1=P2, \+ P1=P3, \+ P1=P4, \+ P1=P5, \+ P2=P3,
\+ P2=P4, \+ P2=P5, \+ P3=P4, \+ P3=P5, \+ P4=P5.
% per(P): P is a period that is not already taken.
per(P) :- day(D), time(T), P is 100*D+T, \+ taken(P).
day(1). day(2). day(3). day(4). day(5).
% The five days
time(9). time(10). time(11). time(12).
% The eight times
time(13). time(14). time(15). time(16).
This assumes that the
taken
predicate is defined separately to tell which periods have
been taken by previously scheduled activities.
The
solution
predicate for this scheduling problem is shown in figure 5.19. The
constraints are handled by two predicates:
not_2_in_a_row
ensures that there is
not a pair of periods where one is an hour earlier or later than the other; and
not_3_same_day
ensures that there are not three periods that are on the same day.
(The day of a period is obtained by doing integer division by 100.)
All that remains is to specify which periods are unavailable using the
taken
pred-
icate. An example specification appears in figure 5.20. Adding those clauses to the
scheduling program gives the following:
?- solution(P1,P2,P3,P4,P5).
P1 = 111, P2= 113, P3 = 213, P4 = 409, P5 = 411
% Mon 11am Mon 1pm Tue 1pm Thu 9am Thu 11am
The scheduling constraints are somewhat loose in this example,
so the solution
displayed here is not unique.
