pasu

2015 Best Paper Prize Awarded

 

Surgical processes are the most important activities in hospitals, not only from a medical and social perspective, but also from an economic viewpoint.

In light of this, the crucial issue of an efficient planning and scheduling of operating theatre has become a major priority.

deHealth Lab  was awarded IMA Journal of Management Mathemathics2015 Best Paper Prize, for a research work, which offers a solutions for surgical processes scheduling.

IMA says that the research work undertaken by prof. Maria Elena Bruni, Patrizia Beraldi, and Domenico Conforti, is not trivial because there are conflicting objectives, such as patient waiting time, operating theatre utilisation and overtime costs, significant uncertainties, relating to procedure duration, cancellations and emergency arrivals, and these uncertainties are dynamic.

 

IMA 2015 Best Paper Prize website

http://www.oxfordjournals.org/our_journals/imaman/prize.html

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.

Last update: 28 September 2018

Problem description

Appointment scheduling systems represent a method to manage patient's waiting lists effectively. This work advances an innovative quantitative approach, based on an optimization model, to manage outpatient Day Service operations. 

Our work acknowledges online scheduling in a multidisciplinary setting, where a case manager, i.e. a physician who coordinates and shares the responsibility for patient care with other specialists. We focus on indirect waiting, and we see the amount of time a patient waits to be admitted as a factor affecting utilization of healthcare services.

We advance our earlier work [ielpa-guido-conforti_HCSE2017], that models HDS with the aim to explore the declarative approach of ASP, to represent knowledge related to the problem and to solve it.

Patients - Patients waiting to be scheduled for clinical test or exams.

Prescriptions - Each patient is characterised by a priority, according to severity of the disease, a number of days the patient has already waited, since a baseline visit, a list of prescriptions of clinical tests or exams. Priorities and prescriptions are determined by a case manager, during the baseline visit. 

Clinical Services - Clinical tests or exams listed in a Package specified for the diagnosis (or therapy) of a disease. For the sake of this work the Ankylosing Spondylitis Day Service Standard Package wase taken as reference.

Time Slot - Time slot is the unit time for patient's clinical service execution. Time slot lasts 1 hour, and it is identified by working hour, working day, week in a scheduling horizon of one working month. The working month consists of 160 time slots, according to a working calendar, specified in input.

Availability Calendar - The calendar specifies which clinical services are available at a given time slot in the scheduling period. The calendar is due to hospital resource management and policies. Some slots may result always unavailable for service maintenance or hospital organization reasons (e.g. no Hospital Day Service is available in the weekends).

Patient  Centered requirements - A number of soft requirements helps to keep the number of patient accesses to the hospital as the smaller as possible. We try to group the services, prescribed to a patient, by the same day, whenever this is not possible, for some reason, we try to group the exams by the same week. The advantage of this requirement is twofold: on the patient side, this contributes to shorten the waiting period, on the resource management side we try to maximize the utilization of hospital resources, according to service capacity.

All patients prescriptions are possibly scheduled in the scheduling month, possibly honouring patient requirements.

Patients are scheduled according to their priority.

If requirements are not met, and/or some exams cannot be scheduled (for a lack of service capacity), a penalty is given.

Clinical Services capacity - The number of clinical service prescriptions that can be scheduled in a day, or week or month. Some services have a very limited capacity, some others, such like blood counts, are highly available.

Priority Queues - Priorities devise priority queues, one for each priority level. Patient requirements are honoured according to their priority level.

Objective Function - Takes into account of the cost deriving from the violation of patient requirements. If admissible solutions are found, the optimal combinations are taken into account according to the value of the objective function.

 

Instances

Instances are available by following this link.

Results on the instances

The following table summarizes the main outcomes of the results download

Table Keys:P=Patient, D=distance between the beginning of the scheduling horizon and the schedule of the clinical service prescription,T=Prescribed clinical service (Test or Exam),W=week,D=day,H=hour of the scheduled clinical service, Weight=cost incurred to schedule the clinical service in the schedule slot (W,D,H), according to patient priority and requirements. A dash symbol in slot cells ('-', '-', '-') means that the clinical service was not scheduled.

Table Sorting: Results are sorted by 

 

P

D

T

W

D

H

Weight

 

           

 


Publication (under review)

Scheduling Outpatient Day Service Operations for Rheumatology Diseases. Giuseppe Ielpa, Rosita Guido, and Domenico Conforti.

Last update: 9 November 2018

Problem description

The patient admission scheduling problem under uncertainty (PASU) has been formally introduced by Ceschia and Schaerf – Ceschia, S., Schaerf, A.. Modeling and Solving the Dynamic Patient Admission Scheduling Problem under Uncertainty. Artificial Intelligence in Medicine, 56(3): 199-205, 2012.

The problem consists in defining for each patient an admission date within a range of possible days and assigning him/her to the most suitable bed/room/department.

Each patient has a registration date, an earliest admission date, a latest admission date and a length of stay. Each room has a defined capacity, a level of expertise (high, medium, null) in treating each specialty, a set of available equipment, that could be mandatory or preferred for patients. There are three room gender policies: the restricted gender policy (RGP) means that only male or female patients can be assigned in a given room; instead, the dependent gender policy (DGP) states that only patients with the same gender of the other patients staying in the room can be assigned. Uncertainty concerns length of stay. In fact, some patients have an overstay risk, i.e. their stay could be extended. Some rooms have an age policy (e.g., paediatric or geriatric rooms).

The best patient-to-bed assignment, which consists in matching patients' characteristics and room characteristics as much as possible, is hard to determine manually. Then, efficient quantitative approaches have to be proposed.  

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 two columns report our results. The bed assignment is evaluated with the default penalty values defined by Ceschia & Schaerf (2012). 

Table Keys:FI= Family of instances, De= number of departments, R= number of rooms, F= number of features, P= number of patients, S= number of specialities, D= planning horizon (in days).
FI De R F P S D Results Results
Small short 4 4 50 3 14 2616.12 SS1  2616.34 SS2
Small mid 100 3 28  5907.34 SM1 5901.76 SM2
Small long 200 3 56  11887.92 SL1 11912.78 SL2
Med short 6 40  250 10 14  11740.78  MS1 11855.12 MS2
Med mid 40  500 10 28  25960.66 MM1 26000.22 MM2
Med long 6 40 5 1000 10 56 // // 57301.91 ML2
Large short 8 160 6 1000 15 14 // // 34157.90  LS2

 

Publication (Omega: The International Journal of Management Science - Under Review)

Efficient matheuristics based on large neighborhood search algorithm for offline patient admission planning and room assignment problems. Rosita Guido, Vittorio Solina, Domenico Conforti.