Dynamic Patient Admission Scheduling Problems

Dynamic Patient Admission Scheduling Problem under Uncertainty

Problem description

The Dynamic Patient Admission Scheduling Problem under Uncertainty (PASU) extends the Patient Admission Scheduling (PAS) problem, introduced by Demeester et al. , by including several real-world features, such as the presence of emergency patients, uncertainty in stay lengths, and the possibility to delay admissions.

Therefore, we propose the definition of a new version of the problem that comprises the basic notions:

Day:
It is the unit of time and it is used to express the length of the planned stay of each patient in the hospital; the set of (consecutive) days considered in the problem is called the planning horizon.
Patient:
She/he is a person who needs some medical treatment, and consequently must spend a period in the hospital, so that she/he must be placed in a bed in a room. Each patient has planned admission and discharge dates within the planning horizon. The actual admission might be delayed w.r.t. the planned one, but not more than a given maximum, which is related to her/his health conditions. In addition, the patient has a registration day in which she/he becomes known to the system. This is equal to the admission day for emergency patients, but can be considerably earlier for elective patients. Only patients registered before the current day are included in the planning. Finally, the patient might have an overstay risk depending on his/her health conditions, which represents the possibility that she/he needs to spend extra nights in the hospital.
Room/Department:
A room belongs to an unique department and can be single or can have more beds. The number of beds in a room is called its capacity (typically one, two, four, or six). Patients may (with an extra charge) express preferences for the capacity of the room they will occupy.
Specialism:
Each patient needs one specific specialism for her/his treatment. Departments might be fully qualified for the treatment of a disease, partially qualified, or not qualified. The assignment of a patient to a department that is not qualified for the treatment of her/his disease is not feasible, whereas the assignment to a department partially qualified is possible, but it contributes to the cost of the solution.
Room Feature:
Each room has different features (oxygen, telemetry, \dots) necessary to treat particular pathologies. Every bed in a room has the same equipment. Patients may need or simply desire specific room features. Assignment to a patient to a room without a needed feature is not feasible, whereas the missing desired features contribute to the objective function.
Room Gender Policy:
Each room has a gender policy. The are four different policies, identified by the strings in the set SG, Fe, Ma, All. In rooms with policy Fe(resp.\ Ma) only female (resp. male) patients can be accepted. If the policy is SG the room can be occupied by patients of both genders, but on any day the patients in the room must be all of the same gender. Finally, rooms of policy All can be occupied simultaneously by patients of both genders.
Age Policy:
Some departments are specialized in patients of a specific age range (e.g., pediatrics or gerontology). For these departments there is a limit on the minimum or the maximum age of the patients admitted.

The PASU problem consists in assigning a room to each patient for a number of days equal to her/his stay period, starting in a day not before his/her planned admission. The assignment is subject to the following constraints and objectives (soft constraints):

Room Capacity:
There can be at most one person per bed per day in each room.
Department Specialism:
The department should have full qualification for the specialism of the patients hosted in the rooms of the department; partial qualification is penalized in the objective function.
Room Features:
The room should have the features needed by the patients; desired ones can be missing, but their absence is penalized.
Room Gender:
For each day, the gender of the patients in the same room should obey the gender policy of the room.
Room Preference:
Patients should be assigned to rooms of the preferred capacity or smaller.
Patient Age:
Patients must be assigned to department that can accept patients of their age.
Transfer:
Patients should not change the bed during their stay; a bed change is called a transfer. All transfers are penalized in equal way.
Delay:
Each time the admission of a patient is delayed, it creates a discomfort for the patient herself, therefore it is penalized in the objective function.
Overcrowd Risk:
Whenever a patient with an overstay risk is scheduled in a room that is full in the day after her/his (presumed) discharge day, this created an overcrowd risk that is penalized.

Constraints are split into hard constraints, that must be satisfied, and soft constraints (or objectives) that can be violated and contribute to the objective function, as shown in the following table. Each soft constraint is associated with a weight, that accounts for its relative importance.

Constraint Type Default weight
Room Capacity Hard ---
Room Gender Soft 50
Department Specialism Hard/Soft 20
Room Features Hard/Soft 20
Patient Age Hard ---
Room Preference Soft 10
Transfer Soft 100
Delay Soft 2
Overcrowd Risk Soft 1

Instances

We designed a parametrized generator which receives as parameters the number of departments, rooms, features, patients, and days. It creates a random instance based on predefined distributions concerning various features such as the stay length, the room capacity, the number of specialisms, and so on. You can download the instance generator.

We have created 9 sets of 50 instances each, using the values shown in following table. The datasets correspond to three different sizes in terms of number of patients and planning horizons. When the horizon is doubled, the number of patients is doubled as well so as to maintain approximately the same average bed occupancy.
A description of the input and output format can be found here.

Family Depts Rooms Features Patients Specialisms Days Best results
Small Short 4 8 4 50 3 14
Small Mid 4 8 4 100 3 28
Small Long 4 8 4 200 3 56
Med Short 6 40 5 250 10 14
Med Mid 6 40 5 500 10 28
Med Long 6 40 5 1000 10 56
Large Short 8 160 6 1000 15 14
Large Mid 8 160 6 2000 15 28
Large Long 8 160 6 4000 15 56

To download all instances and solutions in one shot, the public subversion repository is available:
git clone https://bitbucket.org/satt/pasu-instances.git

Validator

You can download the C++ source code of a solution validator.

Patient Admission Scheduling Problem

The table summarizes the features of the benchmark instances of the PAS problem by Demeester et al. in terms of number of beds, rooms, departments, patients and multi speciality patients. The one in parenthesis is the number of patients reported in the instance files, but it also includes patients that stay for zero days (same admission and discharge date) or that have an admission day subsequent to the end of the planning horizon. The last column reports our best results.

Instance Beds Rooms Depts Patients MP Patients Best results
1 286 98 14 652 (693) 0 658.0
2 465 151 14 755 (778) 0 1137.2
3 395 131 14 708 (757) 0 773.6
4 471 155 14 746 (782) 0 1172.2
5 325 102 14 587 (631) 0 625.6
6 313 104 14 685 (726) 0 798.0
7 472 162 14 519 (770) 0 1193.0
8 441 148 21 895 (895) 0 4149.8
9 310 105 28 1400 (1400) 0 21501.8
10 308 104 56 1575 (1575) 0 8036.2
11 318 107 91 2514 (2514) 0 11811.8
12 310 105 84 2750 (2750) 0 23344.2
13 368 125 28 907 (907) 202 9340.8

Here you can download the original validator implemented by Peter Demeester solution validator.

The Patient Admission Scheduling with Operating Room Constraints

The Patient Admission Scheduling with Operating Room Constraints is a further extension of the PAS problem, which considers also constraints about the utilization of operating rooms for patients that have to undergo a surgery.

Instances, generator, solutions and validator are published here.

Publications

S. Ceschia and A. Schaerf. Local search and lower bounds for the patient admission scheduling problem. Computers & Operations Research, 38(10):1452-1463, 2011.

S. Ceschia, A. Schaerf. Modeling and Solving the Dynamic Patient Admission Scheduling Problem under Uncertainty. Artificial Intelligence in Medicine, 56(3):199-205, 2012.

S. Ceschia and A. Schaerf. Dynamic patient admission scheduling with operating room constraints, flexible horizons, and patient delays. Journal of Scheduling, 1-13, 2014. Online first.