Constraint Solving - Global Constraints (2)

 

2. Job Shop

A job shop problem consists of scheduling J jobs, each consisting of T tasks, which have precedence constraints. The jobs are independent, except for the fact that the tasks are executed in machines of certain types and there are only a limited number of machines of each type. The goal is to finish all tasks within a certain makespan (Satisfaction) or to minimize the makespan.

    i.       Solve the job-shop problem for (small) instances obtained from the OR-library[1]:

For example, benchmark " la03.txt", (other benchmarks available here, together with file read_jshp_mat.co with a function to read this type of files) with a which has the following data:

instance la03

Lawrence 10x5 instance (Table 3, instance 3); also called (setf3) or (F3)

10 5

1 23 2 45 0 82 4 84 3 38

2 21 1 29 0 18 4 41 3 50

2 38 3 54 4 16 0 52 1 52

4 37 0 54 2 74 1 62 3 57

4 57 0 81 1 61 3 68 2 30

4 81 0 79 1 89 2 89 3 11

3 33 2 20 0 91 4 20 1 66

4 24 1 84 0 32 2 55 3  8

4 56 0  7 3 54 2 64 1 39

4 40 1 83 0 19 2  8 3  7

specifies a problem with 10 jobs (rows) and 5 tasks each, where each row indicates for that job the types of the machines in which the tasks are executed and their duration. For example job 1 is composed of 5 tasks, to be executed, respectively, in machines of type 1,2,0,4 and 3, with duration 23, 45, 82, 84 and 38.

a)     Consider the problem variants of satisfaction (finish all tasks before some time T) or minimisation (minimise this time T).

 

   ii.       Consider a variant of the problem where all tasks of all jobs can be executed in any of M machines of the same type (where N is a given number). Adapt the program you have used to solve the job shop problem, and specify a function

cumulate(int o,int h, int maxCap, var<CP>{int}[] s, var<CP>{int}[] d, int [] r)

to constrain a set of tasks starting in time slots s and durations d, each consuming r units of resources, to be executed between time slots o and h, so that in none of these time slots the resources used by the tasks in execution exceeds maxCap.

a)     Reformulate your solution to the jobshop instances, using this user-defined function cumulate.

b)    Replace your function (cumulate) by the system-defined global constraint cumulative/6. Check the efficiency of the specialised propagation algorithms that is used in the global constraint, compared with the propagation obtained by simple decomposition of the global constraint (as you did in the spec of function cumulate).