Industrial Modelling Competition

NEWS FLASH 3!

The customer has queried the quality of the results. How good are your solutions really? Can you show how far you are from the optimal value (makespan only), or can you prove that your solution is optimal? How much have your solutions improved during the week?

NEWS FLASH 2!

The customer has released a new set of large instances: Download test instance set 2.

NEWS FLASH!

The customer has changed his mind: Instead of minimising the makespan alone, you should minimise the sum of the solving time and the makespan of the solution you produce. This is motivated by the usage scenario. The customer creates the test sets very often, and wants to run them as quickly as possible, once they are ready. For this, you can spend time on finding a very good solution, or spend less time for a slower schedule you can start sooner. What counts is the time from receiving the data, and starting the solver,  to the time the last test has finished.

Please report the solving time (in seconds) together with your makespan in the title of the email submission after the name of the instance. The duration of the tests is given in seconds as well. The sum of the two number is the objective value. You may want to re-evaluate your solver, to see if a shorter solving time leads to a better overall value.

Of course, we can not check the execution time you submit, we trust you on this!

Leaderboard (updated 2015-10-05 16:23)

Problem Description

The problem has kindly been provided by Morten Mossige from ABB in Norway.

As part of Industrial Day on Thursday, we propose a modelling competition for the participants of CP2015 and ICLP2015. We will have a session on Thursday afternoon (13:45-15:00 in room G08) to discuss progress, and will add the problems and suggested models to the CSPLib on Saturday in the CSPLib sprint event.

The problem arises in the context of a testing facility. A number of tests have to be performed in minimal time. Each test has a given duration and needs to run on one machine. While the test is running on a machine, no other test can use that machine. Some tests can only be assigned to a subset of the machines, for others you can use any available machine.  For some tests, additional, possibly more than one, global resources are needed. While those resources are used for a test, no other test can use the resource. The objective is to finish the set of all tests as quickly as possible, i.e. all start times should be non-negative, and makespan should be minimized. The makespan is the difference between the start of the earliest test, and the end of the latest finishing test.

To participate

Submission is by email, send result files to cpmodellingcomp@gmail.com with the problem name as the subject. Any solver is allowed, teams of up to three participants are allowed to work together. Nobody should participate in more than one team.

Submissions are now closed.

Details of format

The input data is given as a set of Prolog facts. An example is shown below:

%% ****  Testsuite  ****
% Number of tests                  : 40
% Number of machines               : 10
% Number of resources              : 3
% Number of families               : 1
% Prob that a test use a resource  : 30%
% Minimum test duration            : 1
% Maximim test duration            : 800
% MPri                             : 40%

test( 't1', 568, [], [], 'fam1', 1 ).
test( 't2', 669, [], ['r3'], 'fam1', 1 ).
test( 't3', 688, [], [], 'fam1', 1 ).
test( 't4', 709, ['m7'], [], 'fam1', 1 ).
test( 't5', 505, ['m3'], [], 'fam1', 1 ).
test( 't6', 683, [], [], 'fam1', 1 ).
test( 't7', 20, [], [], 'fam1', 1 ).
test( 't8', 250, ['m6'], [], 'fam1', 1 ).
test( 't9', 235, [], [], 'fam1', 1 ).
test( 't10', 651, [], [], 'fam1', 1 ).
test( 't11', 477, ['m10'], [], 'fam1', 1 ).
test( 't12', 227, [], [], 'fam1', 1 ).
test( 't13', 464, [], [], 'fam1', 1 ).
test( 't14', 257, [], [], 'fam1', 1 ).
test( 't15', 80, ['m2'], [], 'fam1', 1 ).
test( 't16', 592, [], [], 'fam1', 1 ).
test( 't17', 376, ['m9'], [], 'fam1', 1 ).
test( 't18', 541, [], [], 'fam1', 1 ).
test( 't19', 215, [], [], 'fam1', 1 ).
test( 't20', 645, [], [], 'fam1', 1 ).
test( 't21', 624, [], ['r2'], 'fam1', 1 ).
test( 't22', 463, ['m1'], [], 'fam1', 1 ).
test( 't23', 549, [], [], 'fam1', 1 ).
test( 't24', 647, [], ['r1'], 'fam1', 1 ).
test( 't25', 361, [], [], 'fam1', 1 ).
test( 't26', 57, [], ['r3'], 'fam1', 1 ).
test( 't27', 422, [], [], 'fam1', 1 ).
test( 't28', 530, ['m1'], [], 'fam1', 1 ).
test( 't29', 492, [], ['r2'], 'fam1', 1 ).
test( 't30', 306, ['m9','m4','m8'], ['r3'], 'fam1', 1 ).
test( 't31', 519, [], [], 'fam1', 1 ).
test( 't32', 176, [], [], 'fam1', 1 ).
test( 't33', 354, [], ['r1','r2','r3'], 'fam1', 1 ).
test( 't34', 682, [], [], 'fam1', 1 ).
test( 't35', 428, [], [], 'fam1', 1 ).
test( 't36', 340, [], [], 'fam1', 1 ).
test( 't37', 119, ['m1','m6','m4'], ['r3','r2'], 'fam1', 1 ).
test( 't38', 791, [], [], 'fam1', 1 ).
test( 't39', 167, ['m4','m1','m9'], [], 'fam1', 1 ).
test( 't40', 363, [], [], 'fam1', 1 ).

embedded_board( 'm1').
embedded_board( 'm2').
embedded_board( 'm3').
embedded_board( 'm4').
embedded_board( 'm5').
embedded_board( 'm6').
embedded_board( 'm7').
embedded_board( 'm8').
embedded_board( 'm9').
embedded_board( 'm10').

testsetup( 'fam1', 0 ).

resource( 'r1', 1).
resource( 'r2', 1).
resource( 'r3', 1).

The format is the following:

Comment lines starting with % are ignored.

Naming convention of a test suite (the files): t<number of test cases>m<number of machines>r<number of resources>-<instance no>.pl

e.g. t20m10r3-18.pl  20 test case, 10 machines, 3 resources, instance number 18

Each test suite is currently encoded as Prolog predicates as:

A test case:

test(<name>, <duration>,
        <possible machine (empty list = all machines)> ,
        <requested resources>,
        <family of test case (not used)>, 
        <priority(not used)>).

e.g. test( 't13', 537, [], ['r2','r1'], 'fam1', 1 ).

Name:t13, duration 537, executable on any machine, requesting resource r2 and r1

An empty list for the machine indicates any machine can be used, an empty list for the resources indicates that no additional resources are required.

A machine:

embedded_board( <name of machine> ).

e.g. embedded_board( 'm8').

A resource:

resource(<name>,<capacity>).

e.g. resource( 'r1', 1).

Name: r1, capacity: 1 (currently we only use 1 as capacity, to be changed in future.)

The results should be given in the form:

result(<name>,<start>,<machine>).

e.g. result('t1',0,'m1').

Task t1 starts at time 0 on machine m1.

Example

An example problem and its solution is shown in the following Figure:

Scoring

Teams are ranked based on the relative quality of the makespan across all instances. If no team provides a solution to an instance, that instance is not considered for scoring. If a team fails to solve an instance but other teams do, it is given a score equal to the number of teams that did solve the instance. This penalises teams relative to the difficulty of the instance. If only one team solves an instance, it is given a score of zero. Lower is better in this scoring system.

In the case where multiple teams solve an instance, their relative scores are computed as follows. Let \(S\) be the set of solutions for the instance, where \(s_i \in S\) is the makespan of team \(i\). If all objective values are equivalent, then each solver scores zero, otherwise let \(\\alpha = \min_{s_j \in S}{s_j}\) be the best, and \(\\beta = \max_{s_j \in S}{s_j}\) be the worst makespan across any team. Then, the relative score achieved by team \(i\) for the instance is given as: \[ \\text{score}_i = {{s_i - \\alpha} \over {\\beta - \\alpha}} \]

Instances

Download test instance set 1

Download test instance set 2

Download the above problem description as a pdf

Checker script to verify instances and makespan: checker.py