`
planning([]).
planning([on(X,Y,T)|Rest]):-
on(X,Y,T),
planning(Rest).
`

`
on(X,Y,T) :- initially(X,Y,T0), T0 #<= T, not moved(X,T0,T).
on(X,Y,T) :- T1 #>0, T1 #<= T, not moved(X,T1,T), move(X,Y,T1).
`

`
moved(X,T1,T2) :- Y::1..22, Y ## X, T1 #< T2, between1(T9,T1,T2), move(X,Y,T9).
`

where `on(X,Y,T)` is a (the only) property predicate
meaning that block X is on block or position Y at time T.
The predicate `moved(X,T1,T2)` corresponding to the
*clipped* predicate of the Event Caclculus, is defined to
hold if block X was
moved within the time period `T1` to `T2` thus
terminating the previous position of X at `T1`.
Note that in this simple formulation of the problem
we are assuming that the effects of moves
start to hold instantaneously.

The abducible predicates are `A={move(-,-,-)}` as we
only have one type of action in the example domain that we
are considering. This action of `move(X,Y,T)` means that
block X is moved to position Y (that may be another block)
at time T. The general integrity constraints for the
preconditions of this action are the constraints which
state that a block X can be moved to a new position Y only
if the block X and the position Y are both clear i.e. there is
no block on top of either of them. These can be represented
by the following integrity rules in *IC*:

`
ic:- move(X,Y,T), initially(Z,X,T1), not moved(Z,T1,T).
ic:- move(X,Y,T), move(Z, X1, T1), T \== T1, not moved(Z,T1,T),
T#>=T1 #/\ X #= X1.
`

`
ic:- move(X,Y,T), number(Y), initially(Z,Y,T1), not moved(Z,T1,T).
ic:- move(X,Y,T), move(Z,Y1,T1), T \== T1, not moved(Z,T1,T),
T #>= T1 #/\ Y #= Y1.
`

`
ic:- move(X,Y,T), initially(Z,Y1,T1), nott moved(Z,T1,T), Y#=Y1.
`

Note that in the second integrity constraint ` X1 ` is not
written (unified) as ` X ` but we use an explicit equality `
X #= X1 ` so that one way to satisfy this integrity constraint
is by setting the constraint `X ## X1`. Similarly for
` Y1 ` and ` Y ` in the forth and fifth integrity constraint.

Two more constraints which state that different moves can never take place at the same time instance are:

`
ic:- move(X1,Y1,T1), other_move(X2,Y2,T2), X1=\=X2, T1 #= T2.
ic:- move(X,Y1,T1), other_move(X,Y2,T2), Y1\==Y2, T1 #= T2.
`

**Negation as failure** is treated through abduction
and hence all occurances of ` not moved(-,-,-) `
in the program * P * will be replaced by a new predicate
` not_moved(-,-,-) `. Furthermore, the set of integrity
constraints * IC * has to be extended with the additional
constraint:

`
ic:- not_moved(X,T1,T2), moved(X,T1,T2).
`,

unfolded to :

`
ic:- not_moved(X,T1,T2), move(X,Z,T), between1(T,T1,T2).
`

The set of abducible predicates has to be extended with the
declaration
` abducible_predicate(not_moved/3). `

**Example.**
You can retrieve the planning program in its final form
here. Initial
states with either 15 blocks or
12 blocks can aslo be retrieved and
compiled together with the planning program.
These two files of the initial states
contain also some sample queries together with their answer and their
execution time (all the experiments took place on a SUN Ultra workstation
with 64 MB RAM).

Job-shop scheduling is defined as the problem of assigning in time
` n ` jobs on ` m ` machines where each job is a request
for the scheduling of a set of tasks with a particular order.
Each job has a specified release time after which its execution can
start and has to complete its work before a specified deadline.
In addition, the schedule must satisfy other basic constraints such
as the **precedence** constraints that define in which order the
different tasks of a job should be carried out and the **capacity**
constraints that prevent resources from being allocated to more tasks
than they can process at one time (resource capacity).
In ACLP the precedence and resource capacity constraints can
be represented with the following integrity constraints in *IC*:

`
ic :-
start(J, T1,R1,S1), previous(J, T1, T2, S2),
task(T2,D2,_), S1 #< (S2 + D2).
`

`
ic :-
start(J1,T1,R,S1),ostart(J2,T2,R,S2),T1=\=T2,
not decoupled(T1,S1,T2,S2).
`

where ` start(J,T,R,S) ` denotes that task ` T ` of job
` J ` starts execution at time ` S ` on resource (machine)
` R ` and is an abducible predicate. The program ` P `
of the ACLP job-shop scheduling theory is a simple representation
of the basic features of the problem that generates the abductive
hypotheses ` start(J,T,R,S) ` for each job and task from
some top level goal. It also contains the definition of
auxiliary predicates that are used in the integrity constraints
e.g. ` decoupled/4 `

You can retrieve the program in its final form here . In a relevant file you can also retrieve a set of 20 jobs (100 tasks) together with their release times, their deadlines and durations that can be scheduled using the previous ACLP program.

Other constraints specific to the particular application may
be needed, making the problem more difficult to solve.
For example, assume that we are given a new requirement on
the initial problem which says that: if any task ` T2 ` is
using the resource ` R2 ` then the related with ` R2 `
resource ` R1 ` has to be idle till the end of ` T2 `.
This is represented in ACLP by the integrity constraint:

`
% Resource R1 must be idle when R2 is running
ic :-
start(J1,T1,R1,S1),start(J2,T2,R2,S2),T1=\=T2, related(R2,R1),
task(T2,Dur,_), S1 #<= S2 + Dur, S2 #< S1.
`

Such complex constraints can be found in the relevant file.

Another important feature of the ACLP framework is that it facilitates the adoption of new requirements with a small number of changes to the existing solution. One of the main reasons for this is the inherent ability of abduction to reason with a non-empty initial set of assumptions (partial solution) which enables us to use the old solution and recalculate only what is affected (rendered inconsistent) by the changes in the requirements. This helps to achieve a small number of changes in the existing solution.

To illustrate this consider an example where after we
have obtained a solution to a given job-shop problem a new requirement
is added which says that: resource `5` is temporarly out of order
(e.g. between the time points 12 and 20).This new requirement is easily incorporated in the ACLP representation
of the problem by adding the new integrity constraint:

`
% Resource 5 is out of order between the time points 12 and 20
ic :- start(J,T,5,S), S #> 12, S #< 20.
`

We can now run the ACLP query:

Back to ACLP home page