## 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.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)

## 3.2. Toy examples

### 3.2.1. N queens

#### 3.2.1.3. Screenshot

Here is a screenshot of the example:

#### 3.2.1.5. Domain model

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.

### 3.2.3. Traveling salesman (TSP - Traveling salesman problem)

#### 3.2.3.1. Problem statement

It is one of the most intensively studied problems in computational mathematics. Yet, in the real world, it's often only part of a planning problem, along with other constraints, such as employee shift time constraints.

## 3.3. Real examples

### 3.3.1. Course timetabling (ITC 2007 track 3 - Curriculum course scheduling)

#### 3.3.1.1. Problem statement

Schedule each lecture into a timeslot and into a room.

#### 3.3.2.1. Problem statement

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.

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.

#### 3.3.2.2. Problem size

```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).```