DM204 – Scheduling, Timetabling, Routing
Assignment Sheet 3, Fall 2010 [pdf format]

Prepare for discussion in class at 10.00 of Wednesday, March 10 and of Wednesday, March 17.

Exercise 1

Consider the Sport Scheduling problem of Exercise 2, Sheet 2.

Using Comet™:

solve by Constraint Programming a simplified formulation of the problem in which all matches, intra- and inter-division are played once;
solve by Constraint Programming the original formulation; (Hint: you may have to use the global constraint cardinality.)
solve by Local Search the original formulation. (Hint: take inspiration from the example 4 of the lecture on LS in Comet.)

Exercise 2

Given the data below consider the following 4 problems

1 | prec | L_max
1 | prec | ∑C_j
1 | r_j | L_max
1 | r_j, prec | L_max

The first case is not NP-hard and you may think about a polytime algorithm to solve it. For the other cases, make a Comet™ implementation of a CP solver. (To learn how to implement scheduling problems in Comet™ read chapter 14 of the Manual and look at the examples examples/cp/shiploading.co and examples/visu/jobshopDemo.co. You need to use Scheduler<CP>,Activity<CP>, UnaryResource<CP>.)

int n_jobs = 7; range Jobs = 1..n_jobs; int n_machines = 1; range Machines = 1..n_machines; int job_duration[Jobs] = [6,18,12,10,10,17,16]; int job_release_date[Jobs] = [0,0,0,14,25,25,50]; int job_due_date[Jobs] = [8,42,44,24,90,85,68]; //precedences: 2 -> 1 -> 4 // 6 -> 7 tuple pair{int a; int b;} set{pair} precedences={pair(2,1), pair(1,4), pair(6,7)}; // alternative format: // (i,j) = 1 => i->j // (i,j) = -1 => i<-j int precedes[Jobs,Jobs] = [[ 0,-1,0,1,0,0,0 ], [1,0,0,0,0,0,0 ], [0,0,0,0,0,0,0 ], [-1,0,0,0,0,0,0 ], [0,0,0,0,0,0,0 ], [0,0,0,0,0,0,1 ], [0,0,0,0,0,-1,0 ] ];

Exercise 3

Consider 1||∑_j w_j T_j.

Implement in Comet™ two basic local search procedures using the swap and the interchange neighborhoods.

Define the data structures in terms of variables and invariants that you need to represent candidate solutions
Make sure that your algorithm ends when it reaches a local optimum
Try both a first improvement and a best improvement
Improve your heuristic in order to find solutions of better quality using a construction heuristic and/or a metaheuristic.

Start experimenting your program on this small instance:

import cotls; int n_jobs; range Jobs; n_jobs=6; Jobs=1..6; int duration[Jobs] = [8,10,5,13,16,15]; int weights[Jobs] = [9,5,2,8,9,6]; int due_date[Jobs] = [30, 25,50,30,20,45];

Afterwards try your program on a more challenging instance. In order to read the instance download this script and substitute the initial part above with

import cotls; int n_jobs; range Jobs; int []weights; int []duration; //int []release; int []due_date; include "load-wt";

(Hint: You may need the following)

Solver<LS> m(); // Invariants var{int} pos[Jobs](m,Jobs); // Set of predecessor var{set{int}} pre[i in Jobs](m) <- setof(j in Jobs) ( pos[j] < pos[i] ); // Gives start time of job j var{int} start_time[i in Jobs](m) <- sum(j in pre[i]) duration[j]; m.close();

DM204 – Scheduling, Timetabling, Routing Assignment Sheet 3, Fall 2010 [pdf format]

Exercise 1

Exercise 2

Exercise 3

DM204 – Scheduling, Timetabling, Routing
Assignment Sheet 3, Fall 2010 [pdf format]