Last update: 20 March 2017

Problem description

The offline bed assignment problem has been formally introduced by Demeester et al. - Demeester, P., Souffriau, W., De Causmaecker, P., Vanden Berghe, G.. A hybrid tabu search algorithm for automatically assigning patients to beds. Artificial Intelligence in Medicine 2010;48(1):61(70).

The problem consists in assigning elective patients to beds at minimum discomfort by satisfying different constraints related to hospital policies, quality of care, medical requirements and patients preferences. Each patient has proper characteristics and has to be assigned to the most appropriate bed/room/department over his/her stay (admission and discharge dates have been already planned). Transfers in and out of rooms are avoided or minimised.

The best patient bed assignment, which consists in matching patients' characteristics and room characteristics, among all possible alternatives, becomes difficult to determine and hard to solve manually. Hence, the recent interest in developing efficient quantitative approaches to support hospital admission administrators. In the following the terms characterizing this problem.

 

Night - It is the unit of time for patient’s length of stay. The planning horizon is given as consecutive nights.

Department - A hospital has a number of departments. A hospital department has a number of specialitues with different levels of expertise in treating certain pathologies.

Specialism - Department specialties have different expertise in treating certain pathologies. The depatment should have high expertise for the specialisms of patients assigned to their rooms; a low expertise is penalized.

Rooms - Every room is characterized by several items, number of beds, and is located in a department.

Room equipment - Equipment (e.g. oxygen, telemetry) is necessary to treat some pathologies.  

Room Gender Policy - A room can be subject to a gender policy: it can be either restricted to male female patients (restricted gender policy), or subject to the dependent gender policy (that is only patients of the same gender of patients that already occupy a room can be assigned to). Rooms without a gender policy can be assigned both to women and men at the same time.

Room Age Policy - A department should have age restrictions (e.g. paediatric and geriatric Rooms of certain departments can be subject to age policies and only patients consistent with the age policy can be assigned to.

Room Capacity - Every room has a number of beds defining the room capacity.

Patients - Elective patients have to be assigned to hospital rooms in a defined planning period. are characterized by age, gender, pathology, mandatory and preferred equipment, room type preference. Every patient should be treated in a room in correspondence with his/her characteristics, otherwise there is a penalization.

Patient Age - The assignment of patients with age that is not consistent with the age policy of a department is penalized.

Patient Gender - The gender of patients should satisfy the defined gender policy. Otherwise, there is a penalization.

Patient Requirements - Some pathologies of patients need of certain equipment, which is then mandatory.

Patient Preference - Some pathologies of patients are better treated if certain equipment can be (preferred equipment). There is a penalization if the preferred equipment is not in the assigned. Patients may also express some preferences concerning room category (single, double, or ward) they wish to stay. Patients should be assigned to rooms of the preferred or smaller category, otherwise there is a penalization.

Transfer - Patients should not change their bed during the stay. A change of bed is a transfer and it is penalized.

Benchmark instances

Benchmarch instances are available by following this link.

Results on the benchmark instances

The following table summarizes the main features of the benchmark instances. The last column reports our results, that is the bed assignment evaluated with the default penalty values defined by Demeester et al..

Table Keys:I=instance, B=number of beds, R=number of rooms,R1=number of equipped rooms, P=number of patients to schedule and overall number of patients (in parenthesis), P1=number of patients with mandatory equipment, D=planning horizon (in days), DGP=Dependent Gender Policy, RGP=restricted gender policy (N:no, Y:yes), AP= age policy (N:no, Y:yes).
I B R R1 P P1 D RGP AP Results
1 286  98  74  652 (693) 257  14 N N  652.8 download
2 465  151  113  755 (778) 269  14  1134.4 download
3 395  131  101  708 (757) 276  14  764.2 download
4 471  155  110  746 (782) 260  14  1162.2 download
5 325  102  75  587 (631) 234  14  624.0 download
6 313  104  81  685 (726) 247  14  794.2 download
7 472  162  133  519 (770) 455  14  1176.6 download
8 441  148  124  895 (895) 788  21  4068.0 download
9 310  105  87  1400 (1400) 1213  28  20832.8 download
10 308 104 82 1575 (1575) 1373  56  7806.4 download
11 318 107 90 2514 (2514) 2193  91  11536.2 download
12 310 105 89 2750 (2750) 2413  84  22707.2 download
13 368 125 108 907 (907) 805  28  9109.8 download

 

Publication (under review)

A matheuristic approach for solving the offline bed assignment problem. Rosita Guido, Maria Carmela Groccia, Domenico Conforti.