Increasing the Complexity of the Job Shop Scheduling Problem

In order to illustrate the expressive power of the ACLP, we considered the addition of new constraints to the job shop scheduling problem and we studied the ability of the ACLP system to represent these constraints. We compared the two implementations (the ACLP and the ECLiPSe version) not only according to their performance results but also in their ability to represent these constraints and their flexibility in changing the problem requirements.

Assume the extra requirement on the initial core job shop scheduling problem which says that: for a specific task T0, if this starts after a specific time t0 then this task has to be executed last (i.e. no other task can start execution after the task t0). This is represented in ACLP by the single integrity constraint: (for the specific case of T0 = 14 and t0 = 21)

% After time then last ic :- start(1,14,R0,S0), start(J,T,R,S), T =\= 14, S0 #>= 21, S #> S0.

We can simply add this constraint to the program and re-run the query. Here , you can retrieve one way that this constraint can be implemented using the ECLiPSe language.

An alternative new requirement states that: after the end of a specific task T1 and for a specific resource R1, no other task can start execution on that resource before the end of a time interval t_i. This is represented in the ACLP system by the single integrity constraint: (for the specific case of T1=41, R1=1 and t_i =20)

% Rest period after a specific task constraint ic :- start(J,T,1,S), start(4,41,1,Sd),task(41,Dd,_), S #> Sd, S#< Sd+Dd+20.

Here , you can retrieve one way that this constraint can be implemented using the ECLiPSe language. In ACLP we again simply add this constraint and rerun our query.

Consider the requirement that if at least two jobs start their execution in a specific time interval (t_s,t_e) using a specific resource Ri, then no other task can start execution in the interval (t_e,t_e+t_d). The resource Ri must have a rest period. This is represented in ACLP by the integrity constraint: (where Ri=3, (t_s,t_e) = (0,20) and t_d =6)

% if more than one task in a time period then rest period ic :- start(J,T,3,S),start(J1,T1,3,S1),start(J2,T2,3,S2),T1=\=T2, 0 #<= S1, S1 #< 0+20, 0 #<= S2, S2 #< 0+20, S #> 20, S #< 0+20+6.

Due to the much needed effort to implement this directly in ECLiPSe we did not carry this out!

Assume now 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. % Auxiliary Predicate related(1,4).

Again this constraint was not implemented directly in ECLiPSe.

The previous constraint required that no task could start on resource R1 at a time when the related resource R2 is busy. Consider now the ``dual'' constraint requiring that no task can begin on resource R1 at a time when the related (e.g. cheaper) resource R2 is idle. In other words, if a task starts at time T on resource R1 then the related/cheaper resource R2 must be working at this time T. This requirement is represented in ACLP by the following integrity constraint:

% No task on R1 if R2 is idle ic :- start(J1,T1,R1,S1), cheaper(R1,R2), idle(R2,S1).

where the cheaper/2 and idle/2 predicates are defined in the program of the ACLP theory as follows:

% Auxiliary Predicates cheaper(0,1). idle(R,S) :- not working(R,S). working(R,S) :- already_started(Ja,Ta,R,Sa), task(Ta,Da,_), S #> Sa, S #< Sa + Da. working(R,S) :- select_task(Ja,Ta,R), not test(start(Ja,Ta,_,_)), start(Ja,Ta,R,Sa), task(Ta,Da,_), S #> Sa, S #< Sa + Da. already_started(J,T,R,S) :- test(start(J,T,R,S)). select_task(Ja,Ta,Ra) :- findall(T,task(T,_,Ra),L), call(member(Ta,L)), //(Ta,10,Ja), Ja < 9.

The effect of this constraint is that whenever a task T is scheduled on resource R1 the system dynamically schedules in the consistency phase of task T another task Ta on the related resource R2 to ensure that this constraint is satisfied.