JBoss.orgCommunity Documentation

Chapter 3. Use cases and examples

3.1. Introduction
3.2. Toy examples
3.2.1. N queens
3.2.2. Cloud balancing
3.2.3. Traveling salesman (TSP - Traveling salesman problem)
3.2.4. Manners 2009
3.3. Real examples
3.3.1. Course timetabling (ITC 2007 track 3 - Curriculum course scheduling)
3.3.2. Machine reassignment (Google ROADEF 2012)
3.3.3. Vehicle routing
3.3.4. Hospital bed planning (PAS - Patient admission scheduling)
3.4. Difficult examples
3.4.1. Exam timetabling (ITC 2007 track 1 - Examination)
3.4.2. Employee rostering (INRC 2010 - Nurse rostering)
3.4.3. Sport scheduling (TTP - Traveling tournament problem)

Drools Planner has several examples. In this manual we explain Drools Planner mainly using the n queens example. So it's advisable to read at least the section about that example. For advanced users, the following examples are recommended: curriculum course and nurse rostering.

You can find the source code of all these examples in the distribution zip under examples/sources and also in git under drools-planner/drools-planner-examples.

Use a good domain model: it will be easier to understand and solve your planning problem with Drools Planner. This is the domain model for the n queens example:

public class Column {

    
    private int index;
    // ... getters and setters
}
public class Row {

    
    private int index;
    // ... getters and setters
}
public class Queen {

    
    private Column column;
    private Row row;
    public int getAscendingDiagonalIndex() {...}
    public int getDescendingDiagonalIndex() {...}
    // ... getters and setters
}
public class NQueens implements Solution<SimpleScore> {

    
    private int n;
    private List<Column> columnList;
    private List<Row> rowList;
    private List<Queen> queenList;
    private SimpleScore score;
    // ... getters and setters
}

A Queen instance has a Column (for example: 0 is column A, 1 is column B, ...) and a Row (its row, for example: 0 is row 0, 1 is row 1, ...). Based on the column and the row, the ascending diagonal line as well as the descending diagonal line can be calculated. The column and row indexes start from the upper left corner of the chessboard.


When 2 queens share the same column, row or diagonal line, such as (*) and (**), they can attack each other.

A single NQueens instance contains a list of all Queen instances. It is the Solution implementation which will be supplied to, solved by and retrieved from the Solver. Notice that in the 4 queens example, NQueens's getN() method will always return 4.

Assign each process to a machine. All processes already have an original (unoptimized) assignment. Each process requires an amount of each resource (such as CPU, RAM, ...). This is more complex version of the Cloud balancing example.

The problem is defined by the Google ROADEF/EURO Challenge 2012.

Hard constraints:

  • Maximum capacity: The maximum capacity for each resource for each machine must not be exceeded.

  • Conflict: Processes of the same service must run on distinct machines.

  • Spread: Processes of the same service must be spread across locations.

  • Dependency: The processes of a service depending on another service must run in the neighborhood of a process of the other service.

  • Transient usage: Some resources are transient and count towards the maximum capacity of both the original machine as the newly assigned machine.

Soft constraints:

  • Load: The safety capacity for each resource for each machine should not be exceeded.

  • Balance: Leave room for future assignments by balancing the available resources on each machine.

  • Process move cost: A process has a move cost.

  • Service move cost: A service has a move cost.

  • Machine move cost: Moving a process from machine A to machine B has another A-B specific move cost.

model_a1_1: 2 resources, 1 neighborhoods, 4 locations, 4 machines, 79 services, 100 processes and 1 balancePenalties with flooredPossibleSolutionSize (10^60).
model_a1_2: 4 resources, 2 neighborhoods, 4 locations, 100 machines, 980 services, 1000 processes and 0 balancePenalties with flooredPossibleSolutionSize (10^2000).
model_a1_3: 3 resources, 5 neighborhoods, 25 locations, 100 machines, 216 services, 1000 processes and 0 balancePenalties with flooredPossibleSolutionSize (10^2000).
model_a1_4: 3 resources, 50 neighborhoods, 50 locations, 50 machines, 142 services, 1000 processes and 1 balancePenalties with flooredPossibleSolutionSize (10^1698).
model_a1_5: 4 resources, 2 neighborhoods, 4 locations, 12 machines, 981 services, 1000 processes and 1 balancePenalties with flooredPossibleSolutionSize (10^1079).
model_a2_1: 3 resources, 1 neighborhoods, 1 locations, 100 machines, 1000 services, 1000 processes and 0 balancePenalties with flooredPossibleSolutionSize (10^2000).
model_a2_2: 12 resources, 5 neighborhoods, 25 locations, 100 machines, 170 services, 1000 processes and 0 balancePenalties with flooredPossibleSolutionSize (10^2000).
model_a2_3: 12 resources, 5 neighborhoods, 25 locations, 100 machines, 129 services, 1000 processes and 0 balancePenalties with flooredPossibleSolutionSize (10^2000).
model_a2_4: 12 resources, 5 neighborhoods, 25 locations, 50 machines, 180 services, 1000 processes and 1 balancePenalties with flooredPossibleSolutionSize (10^1698).
model_a2_5: 12 resources, 5 neighborhoods, 25 locations, 50 machines, 153 services, 1000 processes and 0 balancePenalties with flooredPossibleSolutionSize (10^1698).