Patient Admission Scheduling

Data sets

The original data set that is used in the AI in Medicine paper on patient admission scheduling (Peter Demeester, Wouter Souffriau, Patrick De Causmaecker, and Greet Vanden Berghe. A hybrid tabu search algorithm for automatically assigning patients to beds. Artificial Intelligence in Medicine 48(1), January 2010, Pages 61-70)
data set 1
data set 2
data set 3
data set 4
data set 5
data set 6. Data set 1 to 6 are applied in the technical report (Burak Bilgin, Peter Demeester, Greet Vanden Berghe. A hyperheuristic approach to the patient admission scheduling problem. KaHo Sint-Lieven, Gent, p.12 (2008), TR-PD-2008-11-07-Hyper), in which the problem instances are solved with a hyperheuristics approach.
New data sets, with more room properties, different gender properties, planning horizons ranging from 14 days to 91 days, and age constraints for the departments.

data set 7
data set 8
data set 9
data set 10
data set 11
data set 12
data set 13 (with patients with multiple specialisms during a stay!!!)

Description of the data sets

The first part describes the number of rooms, the maximum number of room properties per room, the total number of beds, the number of departments and specialisms, the number of patients and the planning horizon.
Example from the first data set:
```
ARTICLE BENCHMARK DATA SET
Rooms: 98 
Roomproperties: 2 
Beds: 286 
Departments: 4 
Specialisms: 4 
Patients: 693 
Planning horizon: 14
```
The second part of the data set file describes the specialisms. The first column corresponds to the ID of the specialism.
Example:
```
   
SPECIALISMS: 
1 Specialism1
2 Specialism2
3 Specialism3
4 Specialism4
```
In the next part of the data set file, the departments are described. The first column corresponds to the ID of the department, while the next column presents the name of the department. The third and fourth number corresponds to the minimum respectively the maximum age of the department. Ex.: In the first department only patients that are at least 65 years old can be admitted. The third department only allows patients that are at most 16 years old. The numbers after the | symbol corresponds to the specialisms of the department
```
(1  1  2  2  2  3).
```
The numbers on the odd indices corresponds to the specialism choices. The first department has as a first choice specialism 1, and as second choice specialims 2 and 3.
Example:
```
DEPARTMENTS: 
1 Department1 65 0 | 1 1 2 2 2 3
2 Department2 0 0 | 1 2 2 3 2 4
3 Department3 0 16 | 1 3 2 4 2 1
4 Department4 0 0 | 1 4 2 1 2 2
```
This part describes the room properties. In this case there are 2. Not all rooms will necessarily have these properties. Some patients need some of these room properties, while others only prefer some of the room properties.
Example:
```
ROOMPROPERTIES: 
1 telemetry
2 oxygen
```

Rooms are descibed in this part. The first column corresponds to the room ID and the second column gives the room name. The next number determines the capacity of the room, while the fourth number indicates the department where the room is physically located.

The letter D indicates that the gender of the room is dependent on the gender of the first patient.
The letter F indicates that the gender of the room is female, meaning that only female patients are allowed.
The letter M indicates that the gender of the room is male, meaning that only male patients are allowed.
The letter N indicates that all genders are allowed in the room. (Actually, this should be M(ixed), but M was already taken, so, I took the next letter in the alphabet.)

The next 6 numbers indicate the specialism of the room. For example the first room, has as a first choice specialism 1, and as second choices specialisms 2 and 3. The last 2 number corresponds to whether a room has or has not the earlier described room properties. The first room has the first room property but not the second.
Example:

ROOMS: 
1 11 | 1 | 1 | D | 1 1 2 2 2 3 | 1 0 
2 12 | 1 | 1 | D | 1 1 2 2 2 3 | 1 0 
3 13 | 1 | 1 | D | 2 1 2 2 1 3 | 0 0 
4 14 | 1 | 1 | D | 1 1 1 2 1 3 | 0 0 
5 15 | 1 | 1 | D | 2 1 1 2 1 3 | 1 1 
6 16 | 2 | 1 | D | 1 1 1 2 3 3 | 1 1 
7 17 | 2 | 1 | D | 1 1 1 2 1 3 | 1 0 
8 18 | 2 | 1 | D | 2 1 1 2 1 3 | 1 0 
9 19 | 2 | 1 | D | 1 1 2 2 2 3 | 0 1 
10 110 | 2 | 1 | D | 1 1 1 2 3 3 | 0 1 
11 111 | 2 | 1 | D | 1 1 1 2 1 3 | 1 0 
12 112 | 4 | 1 | D | 1 1 1 2 1 3 | 0 0 
13 113 | 4 | 1 | D | 1 1 1 2 1 3 | 0 0 
14 114 | 4 | 1 | D | 1 1 2 2 2 3 | 0 0 
15 115 | 4 | 1 | D | 1 1 1 2 1 3 | 1 1 
16 116 | 4 | 1 | D | 1 1 1 2 1 3 | 1 1 
17 117 | 4 | 1 | D | 1 1 1 2 1 3 | 1 1 
18 118 | 4 | 1 | D | 3 1 1 2 1 3 | 1 1 
19 119 | 4 | 1 | D | 1 1 1 2 1 3 | 1 1 
20 120 | 4 | 1 | D | 1 1 1 2 2 3 | 0 1 
21 121 | 4 | 1 | D | 1 1 1 2 3 3 | 0 0 
22 122 | 4 | 1 | D | 2 1 1 2 1 3 | 1 1 
23 123 | 4 | 1 | D | 1 1 1 2 1 3 | 0 0 
24 124 | 4 | 1 | D | 2 1 1 2 1 3 | 1 0 
25 125 | 4 | 1 | D | 1 1 1 2 1 3 | 0 1 
26 226 | 1 | 2 | D | 1 2 2 3 1 4 | 1 1 
27 227 | 1 | 2 | D | 2 2 1 3 1 4 | 1 0 
28 228 | 1 | 2 | D | 1 2 2 3 1 4 | 1 1 
29 229 | 1 | 2 | D | 1 2 2 3 1 4 | 1 0 
30 230 | 1 | 2 | D | 1 2 1 3 1 4 | 1 1 
31 231 | 2 | 2 | D | 1 2 1 3 1 4 | 0 1 
32 232 | 2 | 2 | D | 2 2 1 3 1 4 | 1 1 
33 233 | 2 | 2 | D | 2 2 1 3 1 4 | 0 0 
34 234 | 2 | 2 | D | 3 2 1 3 2 4 | 0 1 
35 235 | 2 | 2 | D | 1 2 1 3 1 4 | 0 0 
36 236 | 2 | 2 | D | 1 2 1 3 2 4 | 0 0 
37 237 | 2 | 2 | D | 1 2 1 3 1 4 | 0 1 
38 238 | 2 | 2 | D | 2 2 2 3 2 4 | 1 0 
39 239 | 4 | 2 | D | 1 2 1 3 2 4 | 1 0 
40 240 | 4 | 2 | D | 1 2 3 3 1 4 | 0 0 
41 241 | 4 | 2 | D | 1 2 1 3 1 4 | 0 0 
42 242 | 4 | 2 | D | 1 2 1 3 1 4 | 1 1 
43 243 | 4 | 2 | D | 1 2 2 3 2 4 | 0 1 
44 244 | 4 | 2 | D | 1 2 1 3 1 4 | 1 0 
45 245 | 4 | 2 | D | 1 2 1 3 2 4 | 0 1 
46 246 | 4 | 2 | D | 1 2 1 3 1 4 | 1 0 
47 247 | 4 | 2 | D | 2 2 2 3 1 4 | 0 0 
48 248 | 4 | 2 | D | 2 2 1 3 2 4 | 0 1 
49 249 | 4 | 2 | D | 1 2 1 3 1 4 | 0 1 
50 250 | 4 | 2 | D | 2 2 1 3 1 4 | 0 0 
51 251 | 4 | 2 | D | 1 2 3 3 1 4 | 1 0 
52 252 | 4 | 2 | D | 1 2 1 3 1 4 | 1 0 
53 253 | 4 | 2 | D | 1 2 1 3 1 4 | 0 1 
54 354 | 1 | 3 | D | 1 3 1 4 1 1 | 0 1 
55 355 | 1 | 3 | D | 1 3 1 4 1 1 | 1 0 
56 356 | 1 | 3 | D | 2 3 2 4 1 1 | 1 1 
57 357 | 1 | 3 | D | 2 3 1 4 3 1 | 0 1 
58 358 | 2 | 3 | D | 1 3 1 4 2 1 | 1 1 
59 359 | 2 | 3 | D | 1 3 1 4 1 1 | 1 1 
60 360 | 2 | 3 | D | 1 3 2 4 2 1 | 1 1 
61 361 | 2 | 3 | D | 1 3 1 4 1 1 | 0 0 
62 362 | 2 | 3 | D | 1 3 2 4 1 1 | 0 1 
63 363 | 2 | 3 | D | 1 3 1 4 1 1 | 1 1 
64 364 | 2 | 3 | D | 1 3 1 4 1 1 | 0 0 
65 365 | 2 | 3 | D | 3 3 1 4 1 1 | 1 0 
66 366 | 2 | 3 | D | 3 3 1 4 1 1 | 0 1 
67 367 | 4 | 3 | D | 1 3 1 4 1 1 | 1 1 
68 368 | 4 | 3 | D | 1 3 1 4 1 1 | 1 0 
69 369 | 4 | 3 | D | 3 3 1 4 2 1 | 0 1 
70 370 | 4 | 3 | D | 1 3 2 4 1 1 | 1 0 
71 371 | 4 | 3 | D | 1 3 1 4 3 1 | 0 1 
72 372 | 4 | 3 | D | 1 3 1 4 3 1 | 0 0 
73 373 | 4 | 3 | D | 1 3 1 4 1 1 | 0 1 
74 374 | 4 | 3 | D | 1 3 1 4 1 1 | 1 0 
75 375 | 4 | 3 | D | 1 3 1 4 1 1 | 0 1 
76 376 | 4 | 3 | D | 1 3 2 4 1 1 | 0 1 
77 477 | 1 | 4 | D | 1 4 1 1 1 2 | 1 0 
78 478 | 1 | 4 | D | 1 4 1 1 2 2 | 1 1 
79 479 | 2 | 4 | D | 1 4 1 1 1 2 | 0 0 
80 480 | 2 | 4 | D | 2 4 1 1 1 2 | 1 0 
81 481 | 2 | 4 | D | 1 4 1 1 1 2 | 0 0 
82 482 | 2 | 4 | D | 1 4 2 1 1 2 | 1 0 
83 483 | 2 | 4 | D | 1 4 1 1 2 2 | 0 0 
84 484 | 2 | 4 | D | 1 4 1 1 1 2 | 1 1 
85 485 | 4 | 4 | D | 1 4 1 1 3 2 | 0 0 
86 486 | 4 | 4 | D | 1 4 2 1 1 2 | 1 1 
87 487 | 4 | 4 | D | 1 4 1 1 2 2 | 1 0 
88 488 | 4 | 4 | D | 1 4 3 1 1 2 | 0 1 
89 489 | 4 | 4 | D | 1 4 1 1 1 2 | 0 0 
90 490 | 4 | 4 | D | 2 4 1 1 1 2 | 1 0 
91 491 | 4 | 4 | D | 1 4 1 1 1 2 | 1 1 
92 492 | 4 | 4 | D | 1 4 1 1 1 2 | 1 1 
93 493 | 4 | 4 | D | 1 4 1 1 1 2 | 0 0 
94 494 | 4 | 4 | D | 1 4 1 1 1 2 | 1 0 
95 495 | 4 | 4 | D | 1 4 1 1 1 2 | 0 1 
96 496 | 4 | 4 | D | 1 4 1 1 1 2 | 0 0 
97 497 | 4 | 4 | D | 1 4 2 1 1 2 | 1 0 
98 498 | 4 | 4 | D | 1 4 2 1 1 2 | 1 1

In this part the beds are described. The first number corresponds to the ID of the bed, and the second number to the room ID where the bed is physically located.
Example:
```
BEDS: 
1 1
2 2
3 3
4 4
5 5
6 6
7 6
8 7
9 7
10 8
11 8
12 9
13 9
14 10
15 10
16 11
17 11
18 12
19 12
20 12
```

In the last part the patients are described.

1 Patient1 88 F | 0 9 | 1 4 9 | 2 | 1 1 0 0 | 0 1 0 1

The third number is the age of the patient. The gender is either F(emale) or M(ale). The fifth and sixth column indicate the admission and discharge date.
The next columns describe the specialism of the patient. For example the numbers 1 4 9 for the first patient mean that in the first part of the stay the patient should be assigned to a department that has specialism 4 for a duration of 9 nights.
We also added in data set 13 patients that have multiple specialisms, meaning that during a patient's stay, the patient is assigned in the first part of his/her stay to a specialism, and the second part of his/her stay to another specialism.
Patients that need to be assigned to multiple specialisms are presented as:

4 Patient4 28 M | 0 8 | 2 2 6 3 2 | 2 | 1 0 0 0 | 1 1 1 1

meaning that Patient4 will be assigned to 2 specialisms: first he/she is assigned to specialism 2 for 6 nights, and the remaining 2 nights, he/she is assigned to specialism 3. Remark that the sum of the individual stays is equal to the total duration: in this case this is,

6+2=8 (=8-0).

Example:

PATIENTS:

1 Patient1 88 F | 0 9 | 1 4 9 | 2 | 1 1 0 0 | 0 1 0 1

2 Patient2 106 M | 0 8 | 1 3 8  | 2 | 0 0 0 1 | 1 1 1 1

3 Patient3 81 F | 0 4 | 1 1 4 |  2 | 0 0 0 0 | 0 1 1 0

4 Patient4 28 M | 0 8 | 2 2 6 3 2 | 2 | 1 0 0 0 | 1 1 1 1

5 Patient5 41 M | 0 12 | 2 3 6 2 6 | 1 | 0 0 1 0 | 1 1 1 0

6 Patient6 99 F | 0 11 | 2 1 5 2 6 | 4 | 0 1 0 0 | 1 1 0 1

7 Patient7 4 M | 0 5 | 1 1 5 | 2 | 1 1 0 0 | 1 1 0 1

8 Patient8 0 M | 0 9 | 1 4 9 | 1 | 0 1 0 0 | 1 1 1 0

9 Patient9 8 M | 0 2 | 1 5 2 | 1 | 0 0 0 1 | 0 1 0 1

10 Patient10 3 F | 0 9 | 1 4 9 | 1 | 0 1 0 0 | 1 1 0 1

11 Patient11 88 M | 0 5 | 1 2 5 | 4 | 0 1 0 0 | 1 1 0 1

12 Patient12 79 F | 0 4 | 1 1 4 | 4 | 0 1 0 0 | 0 1 0 1

13 Patient13 45 F | 0 6 | 1 2 6 | 2 | 0 0 0 1 | 1 1 0 1

14 Patient14 28 F | 0 13 | 1 4 13 | 1 | 0 0 1 0 | 0 0 1 1

15 Patient15 22 M | 0 5 | 1 2 5 | 2 | 1 0 0 1 | 1 1 1 1

16 Patient16 45 F | 0 2 | 1 5 2 | 2 | 0 0 1 0 | 1 0 1 1

17 Patient17 69 F | 0 10 | 2 2 5 1 5 | 4 | 1 0 0 1 | 1 1 1 1

18 Patient18 87 F | 0 2 | 1 3 2 | 2 | 0 0 0 1 | 0 1 1 0

19 Patient19 85 F | 0 17 | 2 1 4 4 13 | 1 | 1 0 1 0 | 1 1 0 1

20 Patient20 97 F | 0 6 | 1 2 6 | 2 | 0 1 0 0 | 0 1 1 0

The following column indicates the room preference of the patient.

1 Patient1 88 F | 0 9 | 1 4 9 | 2 | 1 1 0 0 | 0 1 0 1

Patient 1 prefers a double room. The last 8 numbers indicate the needed and preferred room properties.

1 Patient1 88 F | 0 9 | 1 4 9 | 2 | 1 1 0 0 | 0 1 0 1

Penalty calculation

Room preference penalty calculation: a penalty is only induced when the capacity of the assigned room is greater than the room preference (capacity) of the patient. A patient with a room preference of 4 beds, which is assigned to a room of 2 beds does not induce a penalty.
Room degree-specialism penalty calculation: Rooms can have several specialisms in different degrees. For example, room 1 has as a first choice specialism specialism 1, and as second choice specialisms specialism 2 and 3. If the patient is assigned to a room that has the demanded specialism as a first choice, there is no penalty (this corresponds to the degree of the specialism of the room minus 1, thus 1-1=0). The penalty of a patient that is assigned to a room that has the demanded specialism as a second choice corresponds to 1 (this is equal to the degree of the specialism minus 1, thus 2-1=1) If the patient is assigned to a room that does not have the correct specialism, the corresponding penalty is 2.
preferred and needed room properties: Suppose a patient having both the same needed and preferred room properties (e.g.
```
263 Patient263 1 F | 4 5 | 1 3 1 | 4 | 1 0 0 1 | 0 1 0 1
```
). The idea is that the since the fourth room property is needed anyhow, we can reduce the problem to
```
263 Patient263 1 F | 4 5 | 1 3 1 | 4 | 1 0 0 1 | 0 1 0 0
```
. Of course this has consequences for the penalty calculation!

Weights of the cost function

Constraint	Corresponding weight
Patients in the same room and timeslot have the same gender	5.0
The patient's treatment requirements correspond to the medical equipment of the room and to the treatment of the ward (mandatory room properties)	5.0
The age of the patients should correspond to the maximum or minimum age of the department	10.0
The patient's treatment requirements correspond to the medical equipment of the room and to the treatment of the ward (preferred room properties)	2.0
The room preference should not differ from the room category that is assigned (e.g. a patient prefers to be in a single room and is assigned to a double room); in case it does, a penalty of (assigned room category - preferred room category) is added to the value of the objective function	0.8
Patients should be assigned to the department that is equipped and has trained staff for treating their clinical pictures	1.0
The number of transfers from one room to another should be minimised.	11.0

Solution

The solution's format consists of the patient's ID and a list of assigned bed IDs.
This is an example for the original data set.

Solution validation

The Java based validator can be found here.
Execute the following command in a terminal: java -jar Validator.jar name-of-data-set name-of-solution
Example: java -jar Validator.jar testdata0.txt outputBigFile.txt

Best solutions

All approaches have as a termination criterion the execution time. In order to have an objective means of comparison, we decided to follow the rules of the Second International Timetabling Competition. They provide a benchmark program that calculates based on the characteristics of each individual PC the allowed execution time (on that PC). We opt to distinguish between short and long calculation times: the short calculation times corresponds to the value that is generated by the ITC benchmark program, while the long calculation time corresponds to ten times the short calculation time. In the case of the hyperheuristics and constraint solver approaches this corresponds to 300 seconds for the short calculation times and 3000 seconds for the long calculation times.