A Job-Shop problem refers to most problems found in a typical factory environment where different tasks must be completed to complete a job. A number of jobs are processing at any one time on a number of machines. A schedule must be derived which aims to complete all Jobs as quickly as possible on the given production plant.

           Job | Task | Machine | Duration
           ----|------|---------|---------
           Ja  | Ta1  |    M1   |    2
           Ja  | Ta2  |    M2   |    6
           Jb  | Tb1  |    M2   |    5
           Jb  | Tb2  |    M1   |    3
           Jb  | Tb3  |    M2   |    3
           Jc  | Tc   |    M2   |    4
           Jd  | Td1  |    M1   |    5
           Jd  | Td2  |    M2   |    2

In the following example, the `production plant' comprises three machines: one of type M1 and two of type M2. The table shows the planned production run of jobs Ja...Jd. Each job is different and is broken up into one or more tasks which must be performed on various machines, in a certain order; each task takes a certain time to complete.

  :- import(const_domain).

program :- Jobs = [Ja,Jb,Jc,Jd],
           M1_Tsk = [Ta1,Tb2,Td1],     M2_Tsk = [Ta2,Tb1,Tb3,Tc,Td2],
           M1_Dur = [Da1,Db2,Dd1],     M2_Dur = [Da2,Db1,Db3,Dc,Dd2],
           M1_Dur = [  2,  3,  5],     M2_Dur = [  6,  5,  3, 4,  2],
           append(M1_Tsk,M2_Tsk,Tasks),
           append(M1_Dur,M2_Dur,Durations),

           Tasks in 0..100,      Jobs in 0..100,

           Ta2 ?>= Ta1 + Da1,    Tb2 ?>= Tb1 + Db1,
           Td2 ?>= Td1 + Dd1,    Tb3 ?>= Tb2 + Db2,

           Ja ?= Ta2 + Da2,      Jc ?= Tc + Dc,
           Jb ?= Tb3 + Db3,      Jd ?= Td2 + Dd2,

           cumulative(M1_Tsk,M1_Dur,[1,1,1],1),
           cumulative(M2_Tsk,M2_Dur,[1,1,1,1,1],2),

           minimize_maximum(label(Tasks),Jobs),
           print((Tasks,Durations,Jobs)).

In the program, variables are defined to represent all tasks and their durations. A time range for all Task and Job variables is specified to provide an outer boundary, here nominally between 0 and 100.

The first set of constraints specify the interdependencies between tasks within each job, as in the project planning example; interdependencies ensure that all tasks are completed in the correct order. The second set of constraints specify that the Job variables (Ja, Jb, Jc, Jd) are completed when the last task for each Job is completed.

The two cumulative/4 constraint predicates correspond to each of the two machine types (M1 and M2). cumulative/4 is a builtin constraint predicate which can be used in a number of ways, here to allow each machine to perform only one task at a time. cumulative/4 takes a list of tasks, their durations and their required resource and constrains the resource utilisation to the number of resources available.

The scheduling of M1 tasks on the M1 machine is distinct from the scheduling of M2 tasks on M2 machines. The task dependencies within a job, specified earlier, will though, restrict when certain tasks may be performed on M1 and M2 machines.

The times determined as completion times of each Job is the aspect we wish to optimise. We wish to minimise the maximum completion time for each Ja...Jd variable, i.e. minimise the overall time when the last job is completed. The minimize_maximimum/2 predicate tackles this by minimising the maximum completion time for all the Job variables by repeatedly assigning values to the Task variables.

 
Execution of the program derives the following results (in 0.01 seconds): 
[user] ?- program.
[0,7,2,2,0,10,5,8] , [2,3,5,6,5,3,4,2] , [8,13,9,10]
yes
The resultant lists correspond to the optimised Start times, Durations and 
Job Completions.  The resulting schedule can be illustrated more clearly as 
a Gantt diagram: 

scroll to top