Optimizing Operating Theater Planning - A Data Mining And Optimization Appoach
Full text
Op imizing ope a ing oom planning
a da a mining and op imiza ion app oach
by
Ca los Alexand e Pe ei a da Sil a Godinho Gomes
Mas e in Da a Analysis and Decision Suppo Sys ems
Supe ised by
P o . D . Ca los Manuel Milhei o de Oli ei a Pin o Soa es
P o . D . José Luis Mou a Bo ges
Faculdade de Economia
Uni e sidade do Po o
2014
Los ime is ne e ound again.
Benjamin F anklin
i
Biog aphic no e
Ca los Gomes bo n in Po o in 1987, has a deg ee in Indus ial Enginee ing and
Managemen by he Facul y o Enginee ing o Uni e si y o Po o since 2010. Upon
comple ing his deg ee, he joined a esea ch eam in his o me Facul y o de elop
he p ojec
An in eg a ed amewo k o ope a ing oom capaci y planning
, which
ma e ialized in his disse a ion, a publica ion and a con e ence p oceeding:
An
In elligen Decision Suppo Sys em o he Ope a ing Thea e : A Case S udy
, IEEE
T ansac ions on Au oma ion Science and Enginee ing (2014), and
In eg a ing da a
mining and op imiza ion echniques on su ge y scheduling
, Ad anced Da a Mining
and Applica ions (2012), Nanjing, China.
A e a pe iod a IBM, he cu en ly holds he posi ion o da a scien is a Fa -
e ch, he la ges ashion ma ke place in he wo ld, whe e he is helping o e olu i-
onize how he wo ld shops o ashion.
ii
Acknowledgemen s
Fi s and o emos , I would like o exp ess my since e g a i ude o bo h D . Ca los
Soa es and D . José Bo ges, supe iso and co-supe iso o his disse a ion, o
all he suppo and condence gi en h oughou his jou ney. Despi e he cons an
pos ponemen s, hei op imism could no be le down. Also om he academic
se ing, I wan o hank D . Be na do Almada-Lobo and D . An ónio Ca alho
B i o o he oppo uni y o wo k wi h hem and o e e y ad ice and lesson augh .
Secondly, I wan o hank all my amily, especially my pa en s and my b o he
o all he ene gy, de o ion and lo e.
Ca olina, wo ds a e simply no enough o exp ess how I am so g a e ul o
e e y hing we sha e oge he . Thank you o all he mo i a ion and suppo you
ha e gi en me.
Thank you o e e yone I ha e wo ked wi h a FEUP, IBM and Fa e ch ha
somehow wi nessed and suppo ed me in his endea o . A special wo d o ecogni ion
goes o Fab ício, Gonçalo and C is ina, o all he challenges we sha ed and he
oppo uni y o lea n wi h you.
This wo k was pa ly unded by he P ojec NORTE-07-0124-FEDER-000059,
nanced by he No h Po ugal Regional Ope a ional P og amme (ON.2 - O No o
No e), unde he Na ional S a egic Re e ence F amewo k (NSRF), h ough he
Eu opean Regional De elopmen Fund (ERDF), and by na ional unds, h ough he
Po uguese unding agency, Fundação pa a a Ciência e Tecnologia (FCT).
Finally, I would also like o show my app ecia ion o he esea ch p ojec and
eam o
An in eg a ed amewo k o ope a ing oom capaci y planning and schedu-
ling
, nanced by he FCT p ojec PTDC/EGE-GES/102681/2008, which was he
incep ion o his p ojec and allowed his wo k o be done in he s place.
iii
Abs ac
A g ea pa o he popula ion ha is ope a ed has o wai a long ime o access he
su gical p ocedu e, and as ime elapses he condi ion o hese pa ien s degene a es.
On he o he hand, he amoun o ime du ing which ope a ing ooms a e idle is
signican . Thus, op imizing he ope a ing hea e becomes impo an o educe he
ime pa ien s wai o hei ea men and o a oid unnecessa y was e o esou ces.
This disse a ion p esen s a combina ion o wo decision managemen echniques
applied o he ope a ing hea e , in o de o imp o e he eciency o he su ge y
scheduling p oblem p esen in heal hca e ins i u ions. The app oach de eloped in-
eg a es a da a mining model, used o p edic he du a ion o su ge ies, and an
op imiza ion model, o handle he decision p ocess o scheduling su ge ies. The
p oblem p ima ily exis s because su ge ies a e na u ally unce ain, esul ing in high
a iance in he du a ion o su gical p ocedu es. The inhe en unce ain y o su g-
e ies leads o de ia ions om su geon du a ion es ima es, dis up ing schedules o
causing unde -u iliza ion o ope a ing ooms. To a oid his p oblem, a combina-
ion o supe ised lea ning echniques a e used o imp o e he accu acy o hese
es ima es. Su ge y scheduling is also a dicul combina o ial p oblem, in which
su geons ha e o nd a ime and loca ion o ope a e hei pa ien s. This p oblem
has a s ong impac in he pe o mance o heal hca e o ganiza ions and socie ies,
hence he impo ance o op imize i . This app oach is based in a mixed in ege
p og amming model, sol ed using exac me hods and a me a-heu is ic, de eloped
o his pu pose.
This wo k shows ha he e is an oppo uni y o imp o e he pe o mance o
he ope a ing hea e wi h a gene alized scheduling model. On he case s udy con-
side ed, he me hod p oposed bea s he su geons own su ge y du a ion es ima es
and ou pe o ms hei scheduling plans. The da a mining me hodology de eloped
was es ed in en die en su gical special ies and is able o inc ease he accu acy
o su geon es ima es by up o 44%. The op imiza ion componen was applied o
an ou pa ien su ge y depa men , duplica ing he numbe o su ge ies pe o med
and inc easing ope a ing oom u iliza ion by a leas 50% du ing he pe iod o ime
es ed.
Keywo ds:
Su ge y Scheduling, Da a Mining, Op imiza ion
i
Resumo
Uma g ande pa e da população que é ope ada passa po um longo empo de espe a
a é ecebe o seu p ocedimen o ci ú gico, e à medida que es e empo passa, o es ado
dos pacien es de e io a-se. Po ou o lado, a quan idade de empo du an e o qual o
bloco ope a ó io es á pa ado é signica i a. Assim, a o imização do bloco ope a ó io
o na-se um p oblema impo an e pa a eduzi o empo que os pacien es espe am
pelo seu a amen o e pa a e i a o despe dício de ecu sos hospi ala es.
Es e abalho ap esen a uma combinação de duas écnicas de in es igação ope-
acional aplicadas ao bloco ope a ó io, com o obje i o de melho a a eciência do
agendamen o de ci u gias. A abo dagem desen ol ida in eg a um modelo de
da a
mining
, usado pa a p e e a du ação das ci u gias, e um modelo de o imização, que
lida com o escalonamen o das mesmas. O p oblema exis e p imo dialmen e de ido à
a iabilidade ine en e às ci u gias, causando p oblemas de sob eposição de ci u gias
ou sub-u ilização do bloco ope a ó io. Pa a diminui a ince eza, é u ilizada uma
combinação de écnicas de ap endizagem supe isionada que esul am num modelo
de es imação da du ação das ci u gias. O agendamen o de ci u gias é um p oblema
combina ó io complexo, em que os ci u giões êm que de e mina o empo e o local
pa a ope a um conjun o de pacien es. A abo dagem desen ol ida pa a o p oblema
de agendamen o é baseada num modelo de p og amação in ei a mis a, esol ido
a a és de mé odos exa os e de uma me a-heu ís ica desen ol ida pa a o mesmo
e ei o.
Es e abalho mos a que há uma opo unidade de melho ia do desempenho do
bloco ope a ó io a a és da me odologia desen ol ida. No caso de es udo conside-
ado, o mé odo p opos o supe a a p ecisão das es ima i as dos ci u giões e os seus
planos de agendamen o. O modelo p edi i o desen ol ido oi es ado em dez especi-
alidades ci ú gicas, e é capaz de melho a a p ecisão das es ima i as dos ci u giões
em a é 44%. A componen e de o imização oi es ada no depa amen o de ci u gia
ambula ó ia, duplicando o núme o de ci u gias ealizadas e aumen ado ambém a
u ilização das salas de ope ação em pelo menos 50% no pe íodo de empo es ado.
Pala as-Cha e:
Agendamen o de ci u gias, Da a Mining, O imização
Con en s
Biog aphic no e ii
Acknowledgemen s iii
Abs ac i
Resumo
1 In oduc ion 1
1.1 Mo i a ion................................. 2
1.2 P oblem.................................. 5
1.3 Con ibu ions............................... 6
1.4 Ou line................................... 6
2 S a e o he a 7
2.1 Ope a ing hea e capaci y planning . . . . . . . . . . . . . . . . . . 8
2.2 Da a Mining applied o heal hca e . . . . . . . . . . . . . . . . . . . . 11
2.2.1 Su ge y du a ion es ima ion . . . . . . . . . . . . . . . . . . . 12
3 Da a Mining: Su ge y du a ion es ima ion 18
3.1 Theo e ical backg ound . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.1.1 Algo i hms and models . . . . . . . . . . . . . . . . . . . . . . 20
3.1.2 Me a-lea ning........................... 23
3.2 Me hodology ............................... 23
3.2.1 Da adesc ip ion ......................... 23
3.2.2 Model e alua ion . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.2.3 Modeling ............................. 28
3.3 Expe imen al esul s . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.3.1 Me a-lea ning esul s . . . . . . . . . . . . . . . . . . . . . . . 35
4 Op imiza ion: Su ge y scheduling 37
4.1 Theo e ical backg ound . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.2 Me hodology ............................... 39
i
4.2.1 Ma hema ical model . . . . . . . . . . . . . . . . . . . . . . . 39
4.2.2 Me a-heu is ic........................... 42
4.3 Expe imen al esul s . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5 Conclusions 47
5.1 Su ge y du a ion es ima ion . . . . . . . . . . . . . . . . . . . . . . . 47
5.2 Ope a ing hea e schedule op imiza ion . . . . . . . . . . . . . . . . 48
5.3 Fu u ewo k................................ 49
Bibliog aphy 50
ii
Lis o Tables
3.1 T aining and es ing da a se spli . . . . . . . . . . . . . . . . . . . . 24
3.2 Da abase desc ip ion . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.3 Da a se spli by medical special y . . . . . . . . . . . . . . . . . . . 30
3.4 Su geon es ima es accu acy, anked by MAE (in minu es) . . . . . . . 31
3.5 Resul s om da a mining models applied o he es ing se . . . . . . 32
3.6 Bes da a mining model o each medical special y . . . . . . . . . . . 33
3.7 Compa ison be ween he MAE o su geon es ima es and he bes da a
mining model o each special y . . . . . . . . . . . . . . . . . . . . . 34
3.8 Hypo he ical MAE esul s achie ed by using he bes model o each
su gicalcase................................ 34
3.9 MAE esul s om he applica ion o he s me a-s a egy . . . . . . 35
3.10 MAE esul s om he applica ion o he second me a-s a egy . . . . 36
4.1 Ma hema ical no a ion used in he op imiza ion p oblem . . . . . . . 41
4.2 Cha ac e is ics o he op imiza ion ins ances . . . . . . . . . . . . . . 44
4.3 Op imiza ion esul s o he cons ained su ge y special ies . . . . . . 45
4.4 Op imiza ion esul s o he ou pa ien su ge y special y . . . . . . . 45
iii
solu ion is a complex ask. Mo eo e , hese schedules a e subjec o se e al con-
s ain s, such as pa ien p io i y, ope a ing oom and su geon a ailabili y. This is a
combina o ial p oblem sol ed by he ma hema ical op imiza ion app oach p esen ed
in his disse a ion.
Ul ima ely, since scheduling depends on su ge y du a ion es ima es, combining
he wo app oaches closes he su ge y scheduling cycle.
1.3 Con ibu ions
The objec i e o his disse a ion was o de elop a solu ion ha could oe a mo e
ecien me hod o o ganize and un an ope a ing hea e . To achie e his, an
in eg a ed da a mining and an op imiza ion p ocess was de eloped, esul ing in an
accu a e me hod o es ima e su ge y du a ions and dene su ge y schedules. The
nal esul is a amewo k capable o p o iding ope a ing hea e decision make s
an op imized and comple e su ge y scheduling decision p ocess.
This me hodology is spli in wo app oaches, ha coupled oge he achie e
g ea e pe o mance. Th oughou he li e a u e no simila solu ion was ound, ei he
comple ing he su ge y scheduling p ocess o p o iding a gene ic app oach o he
p oblem, capable o dealing wi h die en medical special ies. Mos o he esea ch
wo k p esen in he li e a u e is bound o specic medical special ies, and he da a
mining and op imiza ion app oaches we e ne e ound oge he .
1.4 Ou line
This documen is di ided in o e main chap e s. The second chap e p o ides a
e iew o he scien ic li e a u e associa ed o ope a ing hea e capaci y planning,
gi ing special emphasis o he p oblem o su ge y du a ion es ima ion. The hi d
and ou h chap e s desc ibe he wo me hodologies de eloped in his disse a ion
and p esen hei esul s. The las chap e add esses he conclusions o his p ojec ,
consolida ing he ndings and p esen ing di ec ions o u u e wo k.
6
Chap e 2
S a e o he a
Heal hca e planning p oblems in he li e a u e da e as a back as 1933, when Pea -
son s a ed ha heal hca e ins i u ions needed mo e quali y and inc eased economy:
The pa ien equi es a highe s anda d o com o and mo e indi idual
a en ion; he enginee ing se ices g ow mo e complica ed and a he
same ime he e is a g ea e desi e o eciency and economy.
Pea son's wo k challenges he p e ious hund ed yea s o hospi al planning p in-
ciples and his esea ch is ocused on he design o ecien hospi al layou s, aiming
o p o ide be e and quicke access o medical acili ies (Pea son, 1933). The c i -
ical hinking ound in his wo k, and he desi e o achie e be e pa ien ca e and
eciency a e he same easons ha nowadays mo i a e esea che s o use hei
knowledge and expe ise o op imize heal hca e se ices.
Acco ding o Eijkemans e al. (2010), 60% o medical pa ien s e en ually unde go
some kind o su gical p ocedu e h oughou hei li e ime. Conside ing his, and he
ac ha he ope a ing hea e is a high esou ce en i onmen , i is comp ehensible
how i becomes he la ges budge consume o hospi al o ganiza ions (Spe andio
e al., 2013; Gue ie o and Guido, 2011). Fu he , and o emphasize why i is im-
po an o become mo e ecien , hospi al o ganiza ions ha e been acing eno mous
p essu es o diminish cos s and downsize hei wo k o ces (Thomas, 2003).
The e has been an inc easingly amoun o esea ch wo k done in he eld o
ope a ing hea e capaci y planning, bu gene ic app oaches o he p oblem as a
whole a e s ill lacking. The emainde o his chap e co e s he li e a u e on op-
e a ing hea e capaci y planning, whe e op imiza ion p oblems can be ound, and
da a mining applica ions o heal hca e, gi ing p ominence o he p oblem o su ge y
du a ion es ima ion.
7
2.1 Ope a ing hea e capaci y planning
In o de o unde s and he meaning o ope a ing hea e capaci y planning, s i
is necessa y o comp ehend wha he ope a ing hea e consis s o . The ope a ing
hea e is composed by se e al spaces closely loca ed whe e su ge ies a e p epa ed
and pe o med, such as: he anes hesia induc ion ooms whe e pa ien s a e gi en a
combina ion o anes he ics o p epa e hem o he p ocedu e; he ope a ing ooms
whe e he su gical p ocedu e is pe o med; and also he eco e y wa ds whe e pa-
ien s eco e om ope a ions. Some ope a ing hea e s enclose in ensi e ca e uni s,
o pa ien s who need o eco e om majo in e en ions and ha e he need o spe-
cialized ca e.
In sum, i is in he ope a ing hea e whe e pa ien s a e p epa ed, unde go
su gical p ocedu es and s a hei eco e y. I s planning equi es he scheduling o
hose pa ien s, he s a needed o ea hem and he equipmen o pha maceu ical
d ugs o pe o m he su ge y (Blake, 2010; Shamayleh e al., 2012; G een, 2005).
P e iously, i was men ioned ha he ope a ing hea e is di ided in h ee decision
le els: s a egic, ac ical and ope a ional. Decisions such as expanding ope a ing
hea e s o he alloca ion o one o a specic medical special y all in o he s a egic
decision le el, as hey conce n high le el and longe e m decisions. The p oblem o
p edic ing su ge y du a ions and scheduling pa ien s o su ge y has an ope a ional
na u e and alls in ha ca ego y. The emaining pa o his sec ion explo es hese
p oblems, dening hem and desc ibing some o he wo ks ound in he li e a u e.
Case mix planning:
Wi hin he s a egic decision le el s ands an impo an in-
dica o ha measu es he mix o pa ien s and condi ions ea ed in a heal hca e o -
ganiza ion, he case mix index. Each ea men pe o med by a heal hca e p o ide
con ibu es o his index acco ding o a weigh a ibu ed by local egula ions. The
case mix index no only becomes an indica o o hospi al pe o mance bu also an
e enly way o und public heal h ins i u ions, an ac i e example o ac i i y based
cos ing.
Planning he case mix o an ins i u ion is a long e m decision and i can be
compa ed o dening a budge o a company. Conce ning he ope a ing hea e , case
mix planning leads o he di ision o esou ces and ime a ailable in he ope a ing
hea e among e e y su gical g oup. I also quan ies he numbe o su ge ies pe
diagnos ic g oup an ins i u ion is willing o pe o m in hei planning ho izon (Hall,
2006). Conside ing he expec ed demand o each ea men and he esou ces a ail-
able, his becomes a p oblem subjec o many cons ains, and in he adminis a ion
pe spec i e, i aims o maximize he e enue (e.g., public unding) while op imiz-
ing he dis ibu ion o se ice be ween exis ing esou ces (e.g., ope a ing ooms,
medical special ies and specialized s a). Beliën and Demeulemees e (2007); Blake
and Ca e (2002), a e wo examples o wo ks de eloped o his p oblem, c ea -
ing op imiza ion models ha no only op imize hospi al unding, bu also, allow
8
s akeholde s o in es iga e die en ade-os be ween unding and esou ce allo-
ca ion. This p oblem is app oached by Hughes and Soliman (1984); Robbins and
Tun iwongpiboom (1989); Kuo e al. (2003) who use linea and in ege p og amming
models o dene his p oblem, each p esen ing hei own cha ac e is ics. Tes i e al.
(2007), in pa icula , de ised a me hodology o in eg a e e e y decision le el o he
ope a ing hea e in one amewo k.
Mas e su ge y schedule planning:
The ac ical le el o ope a ing hea e
planning denes cyclical schedules o each su gical special y based on he hei
alloca ed ime. Di iding ope a ing ooms and hei a ailable ime among su gical
special ies denes he Mas e Su ge y Schedule (MSS). A ime able de e mining
when (i.e., shi and day o he week) and whe e (i.e., ope a ing oom) each spe-
cial y has he oppo uni y o wo k (Beliën and Demeulemees e , 2007). Any ime
he a ailable ope a ing ime changes (e.g., ope a ing oom closing o main enance),
a new MSS mus be dened, in o de o allow a good balance o esou ces inside
and ou side he ope a ing hea e .
Depending on he o ganiza ion, i is possible o nd ope a ing ooms comple ely
alloca ed o a medical special y whe e o he s a e sha ed. This is mainly due o he
high se up cos s o p epa ing ope a ing ooms. This ype o in o ma ion has o be
aken in conside a ion du ing planning, as well as, he a ailabili y o su geons and
common esou ces (e.g., equipmen ) in he ope a ing hea e . The una ailabili y o
such esou ces could cause delays, leading o pe o mance issues. The e a e se e al
wo ks de eloped o sol e his p oblem, wi h solu ion app oaches anging om linea
o mixed in ege p og amming, sol ed using exac me hods (Visse s e al., 2005;
Tes i e al., 2007), app oxima e heu is ics (Blake e al., 2002) and me a-heu is ics
(Beliën and Demeulemees e , 2007). Some imes ope a ing hea e s ha e an acyclic
( a iable) MSS, enabling au ho s o in eg a e he ac ical and ope a ional p oblem
in one app oach, balancing he capaci y alloca ed o each special y on a egula
basis (Ma ques e al., 2012; Tes i e al., 2007).
A his poin , no su ge ies a e scheduled, bu su gical g oups become awa e o
when and whe e hey can pe o m su ge ies (Blake e al., 2002). I is no en i ely
isible ye how hese decisions ha e an impac in socie ies, bu hey a e conside ed
as impo an as su ge ies, since hey dene he mix o su ge y p ocedu es aking
place in he u u e.
Su ge y scheduling:
The nal s age o ope a ing hea e planning conce ns he
su ge y scheduling p oblem, ha is, when he day, hou , loca ion and su gical eam
a e dened o a se o su ge ies. This le el o decision has a sho - e m na u e
(daily, weekly), and because i deals wi h each indi idual pa ien , i is placed in he
ope a ional decision le el.
In su ge y scheduling, i is impo an o ake in o conside a ion wo ypes o pa-
9
ien s: elec i e and non-elec i e. The o me a e su gical cases known and planned
in ad ance, while he la e a e cases ha a i e o he ope a ing hea e as eme -
gencies wi h e y high p io i y. I is a well-known ac ha he eme gency cases
cause se e al planning p oblems because hei u gency can dis up exis ing sched-
ules (G een, 2005; Wullink e al., 2007). Due o hei u gen na u e, elec i e cases
may ha e o be pos poned i he e a e no enough su geons o esou ces o pe -
o m hem (Ca doen e al., 2010). Acco ding o Ca doen e al. (2010); Blake e al.
(1997); Gue ie o and Guido (2011), who exhaus i ely e iew he ope a ing oom
scheduling li e a u e, esea ch on elec i e pa ien planning is a he as compa ed
o non-elec i e.
I is also impo an o dis inguish be ween wo o he ypes o su gical pa ien s,
hose who ha e o be hospi alized o eco e y a e a su ge y (inpa ien s) and hose
who a e able o lea e he p emises in he same day (ou pa ien s). Since inpa ien s
ha e o s ay o e o eco e , hey equi e mo e esou ces, namely om he eco e y
wa d. In hese cases he eco e y p ocess becomes he bo leneck o he su ge y
p ocess, and his is a ely eec ed in he op imiza ion app oaches o his p oblem,
ound in he li e a u e. Ou pa ien s on he o he hand, ha e a simple logic because
hey do no equi e hese esou ces o be conside ed when hey a e scheduled o
su ge y.
Scheduling i sel can ollow die en s a egies. Fi s , i is necessa y o di ide he
p ocess be ween o-line and on-line scheduling. O-line scheduling is he planning
o u u e cases, while on-line scheduling conce ns he daily managemen o schedule
de ia ions, such as when eme gency pa ien s a i e o su ge ies un la e. O-line
scheduling can be u he di ided in o wo ca ego ies: ad ance case scheduling and
alloca ion scheduling. The o me , ad ance scheduling, consis s in de e mining he
da e and place o he su ge y, and he la e , alloca ion scheduling, denes he se-
quence o su ge ies wi hin a pe iod.
Resea che s ha e been ackling hese p oblems wi h a a ie y o objec i es, be-
ing he mos common, maximizing he numbe o su ge ies pe o med. None heless,
minimizing pa ien wai ing ime and maximizing esou ce u iliza ion objec i es a e
also ound (Ca doen e al., 2009). O he e y impo an goals p esen in he li e -
a u e a e: minimizing schedule dis up ions, balancing nu sing beds occupancy and
minimizing schedule dis up ions.
Conce ning he ope a ional planning le el, o he ope a ional p oblems ela ed o
he ope a ing hea e exis . To achie e g ea e eciency i is impo an o o ecas
pa ien demand, by p edic ing eme gency admissions (Ab aham e al., 2009) o bed
occupancy (Kuma e al., 2008), o ake nancial, ope a ional o ac ical le el de-
cisions. Jones e al. (2002) nds in e es ing ela ionships be ween he wea he and
he numbe o admissions o he eme gency ca e uni o a ce ain hospi al and Joy
and Jones (2005) uses a hyb id ARIMA model oge he wi h a Neu al Ne wo k o
o ecas eme gency ca e demand. The subjec o pa ien admission o ecas is well
co e ed by Oli ei a (2004). S a scheduling is ano he dicul and impo an ope a-
10
ional p oblem o heal hca e o ganiza ions, whe e se e al cons ain s and objec i es
a e conside ed (Pa o and Moz, 2008).
Finally, Blake e al. (1997) s a e ha i is u gen ly needed o in eg a e ope a ing
oom scheduling echniques in heal hca e managemen . Mos app oaches o sol e
heal hca e p oblems a e independen om one ano he , decision suppo sys ems,
coupled wi h op imiza ion app oaches, a e mo e han e e needed o de ise be e
plans and achie e highe pe o mances (Gue ie o and Guido, 2011).
2.2 Da a Mining applied o heal hca e
Da a mining is he non- i ial ex ac ion o implici , p e iously unknown and po en-
ially use ul in o ma ion abou da a (F awley e al., 1992). This knowledge disco e y
p ocess has been ge ing g ea e ele ance on ou li es and i s applica ions ex end
o any eld, including heal hca e. In o de o in oduce he p oblem o su ge y
du a ion es ima ion, a b ie his o ical pe spec i e and applica ions o da a mining
o heal hca e will be gi en, beginning wi h John Snow's disco e y.
John Snow is known o be he a he o mode n epidemiology. In 1854, by
using maps wi h ea ly o ms o ba g aphs, Snow disco e ed he o igin o a chole a
ou b eak in he ci y o London and p o ed ha i was being dissemina ed h ough
he ci y's wa e supply ne wo k (Tu e and Weise Moelle , 1997). Snow calcula ed
he numbe o losses and mapped he ic ims' add esses on he ci y map, disco e ing
ha se e al dea hs we e wi hin he adius o a specic wa e pump (see Figu e 2.1).
Figu e 2.1: Ba cha s plo ed o e a map o London depic ing he spa ial dis ibu-
ion o chole a (Tu e and Weise Moelle , 1997)
Da a mining echniques, anging om isualiza ion, clus e ing, classica ion and
eg ession ha e since been ex ensi ely applied o heal hca e. S ill, die en concep s
o da a mining in he heal hca e li e a u e can be ound: Some au ho s e e o da a
11
mining as he p ocess o acqui ing in o ma ion, whe eas o he s e e o da a min-
ing as u iliza ion o s a is ical echniques wi hin he knowledge disco e y p ocess.
(Wilson e al., 2004). A si ua ion ha ca es o special a en ion, as he heal hca e
communi y may lack he backg ound o ully unde s and da a mining and s a is ical
concep s.
Heal hca e o ganiza ions a e known o gene a e an immense amoun o pa ien -
cen ic in o ma ion, making i a sou ce o e y ich bu a he same ime e y
sensi i e da a (Kau and Wasan, 2006). The p i acy o pa ien da a becomes a
big ba ie o he applica ion o da a mining in heal hca e (Canlas, 2009). How-
e e , as mo e heal hca e da a becomes publicly a ailable, new oppo uni ies su ace
o disco e no el medical knowledge and o imp o e he p ocess o ca e wi h he
applica ion o da a mining echniques(Peek, 2010).
Canlas (2009) p o ides a comp ehensi e lis o da a mining applica ions in he
heal hca e sec o , such as aud de ec ing in claims, policy making, demand o ecas -
ing and disease diagnosis. He iden ies a majo challenge ha da a mining aces in
he heal hca e sec o : (...) s anda d da a mining is conce ned mos ly wi h desc ib-
ing bu no explaining he pa e ns and ends. In con as , medicine needs hose
explana ions because any sligh die ence could change he balance be ween li e and
dea h (...). Da a mining models a e o en e y ha d o in e p e and despi e he
aluable esul s hey can p o ide, he lack o unde s anding o hese models is an
issue o he medical communi y. O he au ho s also exp ess hei dicul y o a ain
a p oduc i e collabo a ion wi h he medical communi y, in o de o de elop be e
and au oma ed su eillance sys ems (Obenshain, 2004). O he applica ions o da a
mining in heal hca e p oblem a e, o ins ance: an icipa ing ad e se d ug eac ions
(Wilson e al., 2004), p edic ing cases o sepsis in ad ance (Viei a e al., 2013),
o ecas ing ea men cos s (Kau and Wasan, 2006), iden i ying high- isk pa ien s
(Obenshain, 2004) and o ecas ing pa ien a i als o he eme gency depa men
(Jones e al., 2008).
2.2.1 Su ge y du a ion es ima ion
Apa om he su ge y i sel , p obably he mos impo an decision a su geon has
o make when scheduling a pa ien , is ela ed o he su ge y du a ion es ima e. The
es ima e becomes mo e impo an han o he ac o s since i ese es ha ime in
he ope a ing hea e , he s a and esou ces needed o pe o m he su ge y. As
such, he mo e accu a e he p edic ion is, he be e he ope a ing oom is used.
The unde lying unce ain y o he su ge y aec s he quali y o he schedules, since
de ia ions om planning lead o ei he unde -u iliza ion o o e -u iliza ion o he
ope a ing oom. The du a ion o a su ge y also has an eec on i s cos , bo h con-
ce ning he oppo uni y cos o occupying he ope a i e sui e, and he esou ce cos s
(Dex e e al., 1995; Dex e , 2000; Abouleish e al., 2004). Bacche a e al. (2005)
nds ha he hou ly cos o un an ope a ing oom du ing a simple p ocedu e can
12
be as high as 900$ pe hou , which jus ies why be e su ge y es ima es can educe
ope a ing oom cos s. Ano he eason o he impo ance o hese es ima es is o
know be o ehand wha is he expec ed ou come, (Chu e al., 2008) nds a co ela-
ion be ween he su ge y o al du a ion and he eco e y ime pa ien s. Ha ing his
in o ma ion in ad ance is use ul o he p epa a ion and planning o downs eam
esou ces o he ope a ing oom.
The e a e, howe e , many challenges o accu a ely p edic he leng h o su ge ies,
being he s o human na u e. I has been epo ed ha su geons pu posely bias
hei es ima es (Maca io, 2009; Spangle e al., 2004; Jous a e al., 2013), by ei he
unde es ima ing hei case du a ions o se e al cases in o hei alloca ed ope a ing
oom ime, o hey o e es ima e he du a ion o su ge ies o keep con ol and block
he ope a ing oom ime o o he su geons (Dex e e al., 2005). Rega ding he
au oma ed ask o p edic ing su ge ies, he e a e also challenges, because da a is
o en en e ed inco ec ly o because some p ocedu es a e so a e ha no his o ical
da a is a ailable o hem (Zhou e al., 1999; Maca io and Dex e , 1999; Dex e
e al., 1999, 2002).
As i has been highligh ed, he su gical p ocess is cha ac e ized by s ong un-
ce ain y (Dex e e al., 1999), su ge ies a e s ochas ic p ocesses ha ha e many
a iables aec ing hei o al du a ion (Maca io, 2009). Acco ding o Zhou e al.
(1999) he su gical p ocedu e and he su geon who pe o ms i a e he wo mos
impo an ac o s de e mining he su gical ime. Ye , he e a e o he uncon ollable
and unp edic able easons o inaccu a e es ima ions such as complica ions du ing
su ge ies ha cause delays. To cope wi h he unce ain y, doc o s usually eso o
he his o ical da a o simila p ocedu es. Acco ding o some au ho s, he s a e o
he a in p ac ice is he u iliza ion o he mean his o ical ime o o ecas u u e
su ge y du a ions (Dex e e al., 1999; Zhou e al., 1999; Maca io and Dex e , 1999).
The applica ion o such me hods help o s anda dize he me hodology o es i-
ma e he leng h o su ge ies (Dex e e al., 1999; Zhou e al., 1999). Howe e , he e
is a p oblem o su gical cases wi hou any his o ical da a, and hose ha e a disp o-
po ional la ge impac in ope a ing oom managemen . Also, Maca io (2009) s a es
ha despi e he usage o such echniques, his o ical da a alone can ell us li le
abou he u u e cases. A e aging his o ical da a case du a ion does no inc ease
p edic ion accu acy o newly scheduled case as one would hink (...). This is
mainly due o he ac ha su gical case du a ions do no ollow a no mal dis ibu-
ion. The dis ibu ions in su ge y du a ions a e posi i ely skewed, whe e long cases
ina e he es ima ed case du a ion a e age, making he s a is ical a e age es ima e
less accu a e o he majo i y o cases.
The majo obs acle o accu a e su ge y p edic ion is usually he la ge combi-
na ion o su gical p ocedu es and he su geons pe o ming hem. In ha ega d,
Maca io s a es ha hal o he cases scheduled in he ORs will only ha e e o
ewe p e ious occu ences o he same p ocedu e ype and he same su geon du ing
he p eceding yea (Maca io, 2009). The li e a u e abou case du a ion p edic ion
13
is di ided in es ima ing he du a ion o he su ge y be o e and du ing he su ge y.
The la e is ela ed o a eld o e-scheduling, which eadjus s he emaining ime
o a su ge y gi en how long has al eady passed. Ha ing his in o ma ion allows ope -
a ing hea e decision make s o adjus hei eams, p epa e o eschedule su ge ies
mo e accu a ely.
The s wo ks eme ging in he li e a u e ocusing on he p oblem o de e mining
he leng h o su ge ies da es back o 1996. W igh e al. (1996) compa ed he
accu acy o he su geon es ima es o su ge y du a ions o a comme cial so wa e,
and ound ha he su geon es ima es we e be e . A, c ea ed a linea eg ession
model o p edic he du a ions, leading o he s imp o emen eco ded in he
li e a u e. Al hough his wo k was ocused on a small subse o medical special ies,
i was an impo an miles one in his eld. Fi s , i men ions he exis ence o
scheduling so wa e able o es ima e su ge ies' du a ion, and second, i is he s
wo k ha success ully applies a s a is ical me hod o his p oblem.
F anklin Dex e , who migh be he leading esea che in his eld, is publishing
s a is ical wo ks ela ed o su ge y leng h since 1999. In his s pape , Dex e
e al. (1999), s udies se e al s a is ical echniques o es ima e he du a ion o a
se o su ge ies ins ead o only one. They de elop a linea p og amming model o
schedule su ge ies, and use he mean du a ion o pas su ge ies as es ima es o
hei du a ion. They discuss he ineec i eness o he mean du a ion o minimize
he labo cos s associa ed wi h p edic ing he ime o comple e a se ies o successi e
su ge ies. Ne e heless, hey de end ha i is easonable o use he mean ime i
li le da a is a ailable. Finally, he impo ance o hei me hod is highligh ed due o
he necessi y o ma ch ope a ing oom capaci y agains he cos s o unning unde
o o e -u ilizing hem.
Maca io and Dex e (1999) e alua e he accu acy o die en s a is ical me h-
ods (e.g.: mean, immed mean, median, geome ic mean) o p edic he leng h o
indi idual su ge ies, when su geons had no pe o med hem ecen ly. The lack o
his o ical da a o de e mine u u e ou comes is a p oblem ha aec s many a eas o
science. In he pa icula case o ope a ing hea e managemen , one can nd simi-
la i ies be ween cases in o de o ex apola e hei ou comes and educe he inhe en
a iabili y. He nally concludes ha when ecen his o ical da a is no a ailable,
he mean o he du a ions o cases o he same scheduled p ocedu e pe o med by
o he su geons is as accu a e an es ima e as mo e sophis ica ed analysis. Fo he
bes model he esul ing mean pe cen age e o was 44% o su ge ies ha did no
ha e any his o ical case in he p e ious h ee yea s.
Zhou e al. (1999), s udies i he usage o his o ical su gical imes o p edic he
leng h o u u e cases can minimize he mean du a ion o cases ha nish la e. In
his wo k, he only conce n we e su ge ies nishing la e (o e ime), due o hei
dis up i e na u e on subsequen su ge ies. O he p oblems ise om hese ci cum-
s ances, such as pa ien and s a dissa is ac ion, wo k o e load and he inabili y o
a end u u e appoin men s. In he case s udy conside ed, abou 37% o he su gical
14
cases did no occu in he ecen pas (one yea ime ame). Thus, ein o cing he
dicul y o p edic he co ec ime a su ge y is going o ake. Concluding ha
eso ing o his o ical da a om nished su ge ies alone is an ineec i e s a egy,
mainly due o he low occu ences o each combina ion o su geon and in e en-
ions. The posi i e aspec ha should be highligh ed om his wo k is ha as he
numbe o occu ences is highe , he be e a e he es ima es o u u e su ge ies.
May e al. (2000) e alua es die en s a is ical dis ibu ions o model su gical
imes, nding ha he h ee-pa ame e o m o he log-no mal dis ibu ion is ade-
qua e o su gical imes. They de end he need o schedule ecien ly o con ain he
cos s o su gical se ices and ha modeling he s a is ical dis ibu ion o su ge y
imes is he s s ep o unde s and hei a iabili y. In e ms o p edic ion, he
usage o s a is ical dis ibu ions p o ides li le use ulness since i only desc ibes he
a e age phenomenon and no each indi idual case. S um e al. (2000) also analysis
he s a is ical dis ibu ion o su gical imes. P o ided wi h a la ge da a se o his-
o ical da a wi h 1 580 p ocedu es wi h a leas 5 occu ences each, de e mining i
he dis ibu ion o su gical imes is close o he no mal o log-no mal dis ibu ion.
As wi h May e al. (2000), he use o log-no mal happens o be ecommended and
he single mos impo an sou ces o a iabili y ound in su ge y du a ions a e he
ype o anes hesia used and he pa ien 's age and gende . La e , Spangle e al.
(2004) p oposes a me hod o sys ema ically es ima ing he loca ion pa ame e s o
log-no mal dis ibu ions o model he o al su gical ime. They no e ha ime
eco ds can be biased by hose who eco d he obse a ions, adjus ing hem o mo e
con enien alues a he han making p ecise eco ds.
The se up p oposed by Dex e and Ledol e (2005) comp ises he p edic ion o
lowe and uppe bounds o o al su ge y ime. The goal o p edic ing he bounds
is o know in ad ance he dimension o possible delays (uppe bound) and as e
su ge ies (lowe bounds). I he ope a ing hea e has enough capaci y o accom-
moda e ime be ween su ge ies, i is possible o conside a delay be ween su ge ies
based on he uppe bound o su ge y du a ions. This way i is possible o a oid
longe o e unning su ge ies and educe he wai ing ime be ween su ge ies o he
su gical eam and o pa ien s. Al hough his me hodology does no allow a pe ec
ecien scheduling sys em, i allows o imp o e o e all sa is ac ion. I also p o ides
be e es ima es o when pa ien s should s a p epa ing o su ge y.
Dex e e al. (2005) p oposes a s a is ical me hod o de ec ex eme a ia ions
on scheduled case du a ions. T ying o mi iga e he bias in oduced by su geons
ha was epo ed by Maca io (2009). Mo eo e , hey conside ha Nea ze o bias
can be achie ed in p ac ice h ough he use o his o ical case du a ion da a o
case scheduling and/o ha ing schedule s and su geons mo i a ed o be accu a e.
Fo medical special ies consis en ly unde es ima ing hei case du a ions, i is p o-
posed o schedule hese su ge ies wi h s a is ical es ima es based on his o ical da a,
su geons' es ima es.
Eh enwe h e al. (2006), e alua e he accu acy o su ge y du a ion es ima ion
15
e o and he complexi y o he decision model. In pa icula , his me hod allows
o educes he e o de i ed om he a iance.
C4.5 and C5.0:
hese a e ano he o m o decision ee classica ion algo i hms,
de ised a e he ID3 algo i hm. The C se ies o algo i hms use in o ma ion en opy
o build he model ees. Each node o he decision ee spli s he da a by maximizing
he no malized in o ma ion gain, and ecu si ely does i o he smalle subse s o
da a. The C5.0 e sion o he algo i hm has imp o emen s in pe o mance bu also
inc eased accu acy, mainly due o i s suppo o boos ing.
Random Fo es s:
an ensemble lea ning app oach o classica ion and eg ession
ha wo ks by cons uc ing a la ge se o decision ees. The algo i hm ou pu s he
mos equen p edic ion in he indi idual ees as p edic ions (mode). The me hod
combines B eiman's bagging idea and he andom selec ion o ea u es, in oduced
independen ly in o de o cons uc a collec ion o decision ees wi h con olled
a iance.
Suppo Vec o Machines:
a bina y machine lea ning algo i hm classie , ha
sepa a es da a poin s by maximizing a ma gin unc ion be ween hem. SVMs assume
da a is linea ly sepa able, bu a e applicable o non-linea uni e ses using a echnique
named ke nel ick. This echnique p ojec s he da a se o a high-dimensional
space, allowing linea hype -planes o spli he da a se . New ins ances o he da a
will be classied acco ding o which side o he hype -plane hey all.
kNN:
also known as he k-Nea es Neighbo s algo i hm, is one o he simples
me hods o classica ion and eg ession, which uses he
k
closes aining examples
in he ea u e space o de e mine he p edic ed ou come. This selec ion is based
on he majo i y o e o i s neighbo s (classica ion) o he a e age alues om he
k
-nea es neighbo s ( eg ession).
Leas Angle Reg ession:
ano he eg ession model, sui able o high dimen-
sional da a ha uses a linea combina ion o co a ia es be ween he dependen and
independen a iables. This algo i hm is simila o o wa d s epwise eg ession,
p oducing a ull piecewise linea model.
Mul i a ia e adap i e eg ession splines:
an ex ension o linea models, based
on ecu si e pa i ioning app oaches. MARS models a e able o ep oduce non-
linea i y in da a poin s using hinge unc ions, esul ing in a con inuous models.
22
3.1.2 Me a-lea ning
In he da a mining con ex , me a-lea ning is he p ocess o lea ning o lea n. In-
o mally, a me a-lea ning algo i hm uses pas expe iences o change ce ain aspec s
o lea ning p ocedu es, o igina ing new and, hope ully, be e lea ne s. This lea n-
ing expe ience can be ob ained om se e al ways, bu i is mos ly de i ed om
me a-da a and p ope ies o he p oblem:
Disco e ing me a-knowledge:
inducing knowledge o exp ess how die en al-
go i hms pe o m in se e al p oblems. The me a-da a is made by cha ac e is ics o
he lea ning p oblem da a and he pe o mance o he lea ning algo i hms. Then,
o he algo i hm lea ns how he da a cha ac e is ics ela e o he algo i hms. Gi en
a new p oblem, he pe o mance o he algo i hms can be p edic ed.
S acked gene aliza ion:
combining a pool o lea ning algo i hms, he me a-da a
is o med by he p edic ions o hose algo i hms. A new algo i hm hen lea ns
om his me a-da a o p edic which combina ions o algo i hms pe o ms bes .
Finally, he p edic ions o he bes se o algo i hms a e combined p o iding he
nal p edic ion.
Boos ing:
simila o s acked gene aliza ion, boos ing uses an algo i hm mul iple
imes, whe e he ins ances in he aining da a se a e weigh ed die en ly e e y
un, yielding die en p edic ions. Conside ing ha each lea ning un is ocused on
a pa icula subse o da a, combining hose p edic ions e en ually leads o be e
esul s.
Induc i e ans e :
also known as lea ning o lea n, his me hod ocus in im-
p o ing he lea ning p ocess o e ime. Knowledge is ans e ed om o he lea ning
p oblems, o help lea ning in o he domains.
3.2 Me hodology
This sec ion desc ibes he s eps ollowed o achie e an eec i e me hodology o
accu a ely p edic he du a ion o su ge ies. The emaining opics in his sec ion
conce n model e alua ion and he model phase i sel .
3.2.1 Da a desc ip ion
Da a is conside ed o be he g ea es asse o he XXI cen u y and he ope a ing
hea e is a g ea sou ce o in o ma ion, p o iding aluable da abases o his o ical
su gical da a. The da a a ailable o his wo k comp ehends a da abase o 5.5 yea s
23
o su ge ies om a Po uguese hospi al. The s 4 yea s we e used o ain he
da a mining models and he ollowing yea and a hal o e alua e hei pe o mance.
The dis ibu ion o su ge y ins ances can be ound in Table 3.1.
Table 3.1: T aining and es ing da a se spli
Type Yea s Su ge ies % Spli
T ain
4 52 129 74%
Tes
1.5 18 402 26%
To al
5.5 70 531 100%
Fi s ly, he ea u es used in his wo k conce n mainly h ee ypes o cha ac-
e is ics: he pa ien and his condi ion, he su gical eam and also con ex ual and
en i onmen al se ings. Some o he ea u es lis ed in Table 3.2 we e enginee ed om
he o iginal da a sou ce, and we e calcula ed due o hei ele ance in he li e a u e.
Fo example, Dex e e al. (2008) s a e ha he ype o p ocedu e, he su geon and
eam pe o ming he p ocedu e and he ype o anes he ic used a e good p edic o s
o he o al du a ion o a su ge y. S epaniak e al. (2010) ein o ces ha lis by
a ming ha he mos signican ac o s o aec he leng h o a su ge y a e he
eam composi ion, hei expe ience and ime o he day he su ge y is pe o med.
The da abase used comp ehends 10 die en medical/su gical special ies. The
da a was spli in o die en da a se s, one o each special y, o educe he size
and complexi y o he models ained. No only his made sense o pe o mance
easons, bu each medical special y has i s own g oup o su geons and deals wi h
e y die en su gical p ocedu es, jus i ying he bene s o isola ing each medical
special y. Figu e 3.2, shows how su gical special ies die om each o he ega ding
he dis ibu ion o su ge y du a ions
1
.
Finally, despi e being g ea sou ces o in o ma ion, ope a ing hea e s a e also
a emendous sou ce o inco ec da a, likely gene a ed om inpu e o s o o he
ci cums an ial p oblems. Thus, he o iginal da a se had o be ans o med and
cleaned. The ollowing we e emo ed om he da a se :
•
Scheduled and o al du a ions abo e 10 hou s, likely o be da a inse ion e o s;
•
Nega i e wai ing imes, esul o lis ing pa ien s a e he su ge y was pe -
o med;
•
Ins ances wi h missing alues in c i ical a iables (e.g., su geon and p ocedu e)
1
ENT: Ea s Nose and Th oa , o O ola yngology
24
Figu e 3.2: Dis ibu ion o su ge y du a ions among he su gical special ies consid-
e ed (in minu es)
Table 3.2: Da abase desc ip ion
Va iable Type Desc ip ion Enginee ed Values
Pa ien Gende
nominal Pa ien 's gende Yes M/F
Pa ien Age
nume ic Pa ien s' age (in yea s) 0-100
Su ge y P io i y
nominal P io i y a ibu ed o he su ge y L/M/H/U
Pa ien Wai ing Time
nume ic Numbe o days a pa ien wai ed o su ge y Yes 1-2700
Mon h
nominal Mon h o su ge y Jan-Dec
Weekday
nominal Weekday o su ge y Mon-Sun
Shi
nominal Su ge y scheduled o a mo ning o a e noon M/A
Disease (ICD-Code)
nominal Pa ien 's disease 4000
P ocedu es
nume ic To al numbe o p ocedu es in su ge y Yes 1-3
P ocedu e (ICD-Code)
nominal Su ge y's main p ocedu e code 4000
Su ge ies o da e
nume ic Numbe o su ge ies a pa ien had o da e Yes 0-30
O he Special ies
bina y I he pa ien had a su ge y in a die en special y Yes T/F
Su geon
nominal Su geon iden ica ion Yes 300
Su geon Gende
nominal Su geon's gende Yes M/F
S. Expe ience (Disease)
nume ic Numbe o su ge ies pe o med wi h ha disease Yes 0-800
S. Expe ience (P ocedu e)
nume ic Numbe o su ge ies pe o med wi h ha p ocedu e Yes 0-2000
O he diagnosis
bina y I he pa ien has o he diagnosis Yes T/F
Vascula P oblems
bina y I pa ien has ci cula o y sys em p oblems Yes T/F
Diabe es
bina y I pa ien has diabe es Yes T/F
Recidi is
bina y I condi ion is ecu ing Yes T/F
Mean Du a ion
nume ic Mean his o ical du a ion o simila su ge ies Yes 1-600
Scheduled Time
nume ic O iginal scheduled du a ion by he su geon 1-600
To al Du a ion
nume ic The o al du a ion o a su ge y 1-600
25
3.2.2 Model e alua ion
In o de o e alua e he quali y o any da a mining model, i is necessa y o ha e
app op ia e ways o measu e he ou comes o he model. Gi en wha was said
abou his p oblem, he ideal way o assess an indi idual esul is an e o me ic
(
ei
) dened by he die ence be ween he eal du a ion o a su ge y (
i
) and i s
es ima e (
i
).
ei= i− i
(3.2)
An o e iew o he es da a, compa ing he su geons' es ima es and he eal
du a ions o he su ge ies shows ha he e a e die en beha io s wi hin he se e al
medical special ies s udied. Figu e 3.3, below shows he e o dis ibu ion among
su gical special ies.
Figu e 3.3: E o dis ibu ion by special y (in minu es)
Since he cha ac e is ics o each special y die om each o he , i is impo an
o ha e a scale-independen e o measu e o make a ai compa ison. The ela i e
e o o an indi idual ins ance (
pi
) is gi en by:
pi=( i− i)
i
(3.3)
S ill, simple indi idual measu emen is no enough o judge he quali y o a
model as a whole, hence and agg ega ed iew is equi ed. Fu he , i is impo an
o hese me ics o ha e ce ain cha ac e is ics o c ea e a good pe spec i e o he
esul s. Some o hose p ope ies a e:
26
•
Scale-independence: measu e independen o he se ies scale;
•
Ou lie -independence: measu e no aec ed by ex eme o ou lie e o s;
•
Sensi i i y: measu e eac i e o small changes in e o s;
•
Typicali y: measu e ep esen a i e o i s unde lying s a is ical dis ibu ion.
The e is a wide discussion on he mos app op ia e measu e o eg ession models,
bu since each me ic has i s ad an ages and disad an ages, he me ics below will
be used o measu e he esul s.
Mean Absolu e E o (MAE):
In s a is ics, he MAE is he a e age o he
absolu e alue o he e o s. I is an indica o o how close he p edic ions a e om
i s eal alues, and i is gi en by:
MAE =1
N
N
X
i=1 |ei|
(3.4)
The eason o no using he Mean E o (ME) comes om he ac ha some
ins ances will ha e posi i e e o s and o he nega i e, canceling each o he . Looking
o ME alone would be misleading as he a e age e o would be close o ze o.
Mean Absolu e Pe cen age E o (MAPE)
: MAPE helps o unde s and he
ela i e pe o mance o he models compa ed o eali y. I a e ages he absolu e
ela i e e o s and i is gi en by:
MAPE =1
N
N
X
i=1 |pi|
(3.5)
Roo Mean Squa ed E o (RMSE):
RMSE esul s om mean squa ed e o
(MSE), which penalizes la ge de ia ions. Using RMSE alone, equen ly leads o
models wi h a small numbe o la ge e o s bu a g ea numbe o small e o s.
Compa ed o i s squa ed coun e pa (MSE), his me ic is p e e ed because i has
he same scale as he da a:
RMSE =√MSE =
u
u
1
N
N
X
i=1
e2
i
(3.6)
27
Pea son Co ela ion:
This co ela ion coecien exp esses he deg ee o linea
dependence be ween wo a iables (
xy
). I akes any con inuous uni alue and
he close i is o ze o, he weake he ela ionship be ween he a iables. This will
indica e he co ela ion be ween he es ima es and eal su ge y du a ions, and si is
exp essed by:
xy =Pn
i=1(xi−¯x)(yi−¯y)
qPn
i=1(xi−¯x)2Pn
i=1(yi−¯y)2
(3.7)
In he con ex o su ge y scheduling, he objec i e o imp o ing he accu acy
o su ge y es ima ions is con eyed by minimizing he e o me ics desc ibed. As
he e o is educed, he co ela ion coecien is expec ed o be close o one. Be-
cause he impac o o e - (OE) and unde -es ima ion (UT) is e y die en , wo
addi ional me ics a e in oduced o measu e hei impac , Equa ions 3.8 and 3.9
espec i ely. This is he s s ep owa ds a cos sensi i e model e alua ion (Bow y,
2010). Finally, he o al was e is measu ed by adding Equa ions 3.8 and 3.9.
O e −es ima ion =
N
X
i=1
ei,∀ei>0
(3.8)
Unde −es ima ion =
N
X
i=1
ei,∀ei<0
(3.9)
3.2.3 Modeling
The modeling phase essen ially consis ed in c ea ing die en da a mining eg ession
models (
M
), ha gi en he ec o o independen ea u es o a su ge y (
XT
i
) would
be able o accu a ely o ecas su ge y du a ions (
i
).
i=M(XT
i)
(3.10)
Despi e his high-le el and a he simple desc ip ion, de eloping his me hod-
ology was an i e a i e p ocess. Th ough he de elopmen and ial phase, se e al
a emp s we e made and models ied o a ain be e accu acy. The da a was spli
in o die en da a se s, one o each medical special y, so ha each model could
be ained wi h only one special y. No only would his educe he compu a ional
ime equi ed o ain he models, bu i also simplied hem. In ee o ule based
models his is a he impo an , since i becomes easie o in e p e he esul ing
model. In a me a-lea ning pe spec i e his is known as in oducing me a-knowledge
o he p oblem. The aining se , dened by he s 4 yea s o da a was used o
ain 22 die en eg ession models using he algo i hms in oduced be o e. Each
model was ained using a 10- old c oss alida ion. Some o he models buil de i e
om die en pa ame iza ion o he algo i hms and we e included in he esul s due
28
o hei pe o mance die ences. Special emphasis was gi en o imp o e he model
and in o de o do so, a g id uning app oach was used. This app oach enables he
da a mining engine o i e a i ely es die en combina ions o pa ame e s on each
algo i hm, op imizing hei p edic ion obus ness. Figu es 3.4, below, depic s he
esul s o wo op imiza ion uns o a k-NN algo i hm and a GLM ne wo k, showing
he die ence in pe o mance as he pa ame e s a e changed.
(a) GLM Ne uning (2 pa ame e s) (b) k-NN uning (1 pa ame e )
Figu e 3.4: Sample esul s om uning wo da a mining models
A e expe imen ing wi h die en algo i hms, he idea o use he bes p edic ions
ound and use hem o c ea e he nal es ima e, minimizing he o al o e all e o ,
eme ged. A me a-lea ning o ensemble way o hinking, which would use he bes
p edic ions p o ided by he base models o c ea e a new and nal es ima e. To
a ain his goal, wo die en s a egies we e c ea ed and applied o e he o iginal
es se . This es ing da a se was hen spli in wo new subse s o aining and
es ing pu poses, esul o a 70% / 30% andom spli o he da a. A his s age, he
impo ance o ha ing a ch onological logic in he me hodology was dismissed.
The s ensemble s a egy was de ised o p edic he bes pe o ming model o
each indi idual su ge y. To do so, and gi en he pool o models and esul s ga he ed
be o e, a new ca ego ical a iable was c ea ed and included in he da a se , dening
he model ha p oduced he minimum e o o e e y indi idual su ge y. Then,
he objec i e is o p edic he bes algo i hm gi en he in o ma ion o he su ge y.
The p edic ion o his new nominal a iable was pe o med wi h se e al supe ised
classica ion algo i hms. No o he a emp s o modi y he o iginal da a se s uc u e
we e ied.
The second ensemble a emp was de eloped by c ea ing a new da a se o me a-
ea u es. This s a egy esembles he s acking app oach, whe e he esul s o se e al
lea ning algo i hms a e combined and a new lea ne is ained o e his in o ma ion.
The same eg ession modeling app oach was ollowed bu now he ec o o indepen-
den ea u es o a su ge y (
XT
i
) was composed by he du a ion es ima es ga he ed
29
be o e. This me hod only conside ed he me a- ea u es and disca ded he o iginal
da a se ea u es, o igina ing a pu ely nume ic da a se .
3.3 Expe imen al esul s
This sec ion e alua es he success o he me hodology de eloped and he models
used o he p oblem o su ge y du a ion es ima ion. The esul s o he models es ed
will be compa ed agains each o he , and will always ha e as a baseline he o iginal
su geons' es ima e and accu acy. This sec ion p esen s he ini ial base models es ed
and las ly he ensemble app oach. The base model me hod was pu ely o mula ed
by lea ning p edic i e models om he aining da a o each medical special y. In
o al, 22 models we e es ed in 10 die en su gical special ies. The spli o da a in
aining and es se s by medical special y is gi en in Table 3.3, which shows ha
on a e age 26% o he da a a ailable was labeled o es ing pu poses.
Table 3.3: Da a se spli by medical special y
Special y T ain Tes To al % Tes
De ma ology
2 634 827 3 461 24%
Gene al Ou pa ien Su ge y
7 223 2 175 9 398 23%
Gene al Su ge y
5 071 1 363 6 434 21%
Neu o Su ge y
2 237 730 2 967 25%
Oph halmology
10 800 4 608 15 408 30%
O hopedics
7 032 2 063 9 095 23%
O ola yngology
4 336 1 901 6 237 30%
S oma ology
2 863 887 3 750 24%
U ology
4 687 1 870 6 557 29%
Vascula Su ge y
5 246 1 978 7 224 27%
To al
52 129 18 402 70 531 26%
As explained be o e, he es ing se ep esen s he la e yea s o he da a se ,
allowing a p ope e alua ion o he me hodology in a ch onological pe spec i e:
using pas da a o p edic u u e ou comes. To unde s and he o iginal p oblem
p ope ly, he pe o mance o he o iginal su geon es ima es is specied on Table 3.4.
The able p esen s he me ics p e iously in oduced and i s s uc u e will be used
h oughou he chap e o quan i y he esul s. The ank in oduced, ep esen s he
anking o he model in e ms o MAE compa ed o he o al 22 models assessed.
The mos ema kable e ela ion is ha in a pe iod o 1.5 yea s o ope a ions,
mo e han hal a million minu es we e los , bo h by o e -es ima ed (40%) and unde -
es ima ed (60%) su ge ies. This is he equi alen o oughly 9 000 ope a ing oom
hou s, which could ha e been a ailable o o he su ge ies. Ano he insigh shown
30
Table 3.4: Su geon es ima es accu acy, anked by MAE (in minu es)
Special y Rank MAE RMSE MAPE TW OE UE
xy
De ma ology
2 9.2 13.4 30% 7 565 1 986 5 579 0.08
Ou pa ien Su ge y
20 15 20.2 80% 32 722 11 448 21 274 0.67
Gene al Su ge y
22 47.2 67.5 46% 64 359 17 224 47 135 0.69
Neu o Su ge y
22 76.8 102.5 43% 56 028 27 269 28 759 0.54
Oph halmology
22 18.1 30.5 69% 83 350 36 247 47 103 0.39
O hopedics
21 40.1 53.7 36% 82 746 60 365 22 381 0.77
O ola yngology
22 28.4 39.9 57% 54 011 17 942 36 069 0.58
S oma ology
12 23.1 35.9 50% 20 453 4 336 16 117 0.78
U ology
21 42.7 65.5 69% 79 925 13 059 66 866 0.65
Vascula Su ge y
22 31.9 48.6 53% 63 130 27 009 36 121 0.67
To al
22 29.6 47.8 58% 544 289 216 885 327 404 0.76
in Table 3.4 is ha on a e age, su geons es ima e su ge ies wi h an absolu e e o
o 29.6 minu es. In absolu e e ms his shows how big he a e age e o is and
how big is he oppo uni y o imp o e. In e es ingly, i is no iceable how ce ain
special ies end o o e -es ima e he leng h o su ge ies compa ed o o he s which
unde -es ima e. This is likely o be a cha ac e is ic o su geons ha compose he
special y and he inhe en dicul y o he p ocedu es pe o med. O all he 22
models es ed, he su geon es ima es pe o m he wo s wi h an o e all ank o 22.
Tha is no he case o De ma ology, whe e he su geon es ima es pe o m second
bes . Howe e , in his case, he co ela ion be ween he su geon es ima es and he
o al su ge y du a ion o 0.08 is disce ning. The eason o he low co ela ion is
he ough and ound es ima es su geons make (e.g., 30, 45, 60 minu es) when in
ac he du a ion o a su ge y is a con inuous a iable. Figu e 3.5 plo s he o al
du a ion agains he scheduled du a ion ound in de ma ology. The pa icula case
o De ma ology is excep ional due o he low du a ion o su ge ies.
The esul s o he applica ion o e e y da a mining model o each special y es
se is p esen ed in Table 3.5, consolida ed by model and no special y. In his able
i is possible o obse e how ce ain algo i hms minimize some e o measu es bu
no o he s. I is he case o he M5 Rules algo i hm which has he lowes MAE bu
he Decision able algo i hm, which anks 8
h
, has he lowes MAPE.
Compa ing he bes pe o ming model agains he su geons' baseline (and also
he wo s model) he e is a gain o 27% in e ms o MAE and 26% on o al was ed
ime. The absolu e die ence in ime los be ween he su geon es ima es and he
bes model co esponds o a o al o 2 414 hou s. Implying ha i would ha e
been possible o sa e ha ime i he M5 model was used o p edic he du a ion
o e e y su ge y pe o med in ha pe iod. Mo eo e , he o al ime los due o
unde es ima ion is educed by 34% and o e es ima ion by 16%, which means ha
he e would be a signican less amoun o su ge ies su passing hei dened imes,
31
4.1 Theo e ical backg ound
The ounda ions o ope a ions esea ch da e back o he beginning o he Second
Wo ld Wa , when Managemen Sciences / Ope a ions Resea ch (MS/OR) s a ed
o become an impo an eld o s udy. Du ing ha ime, he applica ion o MS/OR
yielded g ea esul s o he Allies on , imp o ing he eciency o anspo a ion
ne wo ks and he o ganiza ion o mili a y de ensi e and oensi e on s. Ope a ions
esea ch conce ns he de elopmen o echniques, algo i hms and models o sol e
eal and complex p oblems. Common p oblems ound and sol ed in he li e a u e
using ope a ions esea ch me hods ange om scheduling applica ions, alloca ion o
esou ces, ow managemen , ou e deni ion, among many o he s. An o e iew and
desc ip ion o he echniques used o sol e his p oblems is gi en in his sec ion.
Ma hema ical op imiza ion:
op imiza ion is he sea ch o he bes possible
solu ion o a ce ain p oblem. Op imiza ion p oblems a e dened by ma hema -
ical models, which ep esen a eali y whe e a decision make wishes o op imize
a ce ain objec i e (i.e., objec i e unc ion), made o se e al decision ac o s (i.e.,
decision a iables) and subjec o ce ain cons ain s. These p oblems a e o mu-
la ed ma hema ically and he e a e usually die en ways o nd solu ions o hem.
Solu ion app oaches can be spli in o exac me hods, ha can p o e i a solu ion is
op imal o no , and app oxima e me hods, ha sea ch he solu ion space o easible
solu ions, bu a e unable o de e mine i one is op imal o no .
Combina o ial op imiza ion:
a pa icula case o ma hema ical op imiza ion
ha aims o nd he op imal se o al e na i es o op imize a gi en objec i e unc-
ion. The main die ence om hese p oblems o, o ins ance, linea op imiza ion
p oblems, is he disc e e na u e o he ea u e space. A well known ins ance o
combina o ial p oblems is he a elling salesman, which a ge s o nd he op imal
ou e be ween a se o des ina ions. Combina o ial p oblems in ol e de e mining
he mos ecien way o ecien ly alloca e esou ces. Due o he disc e e na u e
o he p oblem, he solu ion space g ows exponen ially as a iables a e added, be-
coming imp ac ical o use exhaus i e sea ch o nd easible solu ions. The e a e
exac app oaches o sol e hese p oblems (e.g., B anch and Bound), bu app oxi-
ma e me hods and specic ailo ed algo i hms can also be used o sea ch he disc e e
solu ion space o hese p oblems.
Heu is ics & Me a-heu is ics:
when op imiza ion p oblems become oo la ge
o sol e wi h exac me hods, heu is ics and me a-heu is ics eme ge as p ac ical ways
o sol e complex p oblems. These a e app oxima e me hods ha can ake ad an age
o specic p oblem logic o ope a e, bu on he o he hand canno gua an ee op imal
solu ions. Heu is ics a e app oxima e p ocedu es, specially designed o a pa icula
38
p oblem. Me a-heu is ics on he o he hand a e mas e s a egies, independen o
he p oblem, by deni ion hey a e comple ely agnos ic o he p oblem hey a e sol -
ing, allowing a la ge numbe o applica ions. They ha e special ea u es ha make
hem ad an ageous in he sea ch o good solu ions, as hey ha e buil in mechanisms
o a oid he algo i hm o be s uck in local op imum solu ions, pe o ming mo e e -
cien sea ches o e he sea ch space. Commonly, me a-heu is ics mimic disco e y
p ocesses obse ed in na u e and a e usually non-de e minis ic, since hey inco po-
a e andom p ocesses o suppo di e sica ion du ing he sea ch o he disc e e
solu ion space. They can also use o ms o memo y o ake ad an age o acqui ed
sea ch expe ience. Gene ic algo i hms (GA), which a e used in his disse a ion, a e
a popula ion based me a-heu is ic ha ha e his capaci y.
Gene ic algo i hms:
A gene ic algo i hm (GA) is a me hod o sol ing bo h
cons ained and uncons ained op imiza ion p oblems based on a na u al selec ion
p ocess. GAs use a pool o candida e solu ions and e ol e hem owa ds be e solu-
ions by mimicking biological e olu ion, whe e he s onges indi iduals (solu ions)
su i e and a e ca ied o wa d. In he GA pe spec i e his happens h oughou
gene a ions (o i e a ions) as he ness o each indi idual is assessed. The ness
denes he likelihood o su i al, and is dened he objec i e unc ion o he p oblem
being sol ed. T adi ionally solu ions a e ep esen ed (encoded) in bina y, allowing o
pe o m a exible and ecien se o ope a ions o e he pool o solu ions. Th ough
he e olu iona y p ocess, indi idual solu ions a e combined (c osso e ) wi h each
o he in o de o p omo e he sea ch o he ea u e space. A second ope a o , mu a-
ion, is also able o p o ide di e si y o he pool o solu ions by andomly changing
ce ain ea u es o each indi idual. These algo i hms s op a e a p edened numbe
o gene a ions o i a sa is ac o y ness h eshold is eached.
4.2 Me hodology
The me hodology de eloped and p esen ed in his chap e sol es he ma hema ical
model c ea ed o schedule su ge ies. In he s expe imen al phase a a comme cial
combina o ial sol e was used. Howe e , due o he comme cial licensing aspec o
he so wa e, a ailo -made gene ic algo i hm solu ion me hod was de ised o sol e
he scheduling p oblem.
4.2.1 Ma hema ical model
The p inciple o he ma hema ical model w i en ackles he ad ance scheduling
p oblem dened in Sec ion 2.1, alloca ing pa ien s wai ing o su ge y o a momen
in a ime and space in he u u e, gi en he cons ain s ha dene ope a ing hea e
planning.
39
The model c ea ed o his p oblem is based on he mul iple knapsack bina y
model. A classic ope a ions esea ch p oblem ha a ge s he decision o which i ems
should be added o a mul iple knapsacks, maximizing he alue o his selec ion.
Su ge y scheduling can be seen as a mul iple knapsack bina y p oblem, conside ing
ope a ing ooms as knapsacks and su ge ies as i ems, subjec o he bina y decision
o being selec ed o an ope a ing oom o no . The classic o mula ion o he
p oblem is, succinc ly, gi en by:
max X
i∈N
xiwis. . X
i∈N
xiwi≤C
(4.1)
Whe e he decision a iable
xi
ep esen s he bina y decision o selec ion i em
i
,
weigh ing
wi
, o knapsack cons ained by i s capaci y
C
.
In he ope a ing hea e con ex , each a ailable shi o an ope a ing oom co e-
sponds o a knapsack and pa ien s a e assigned o knapsacks gi en he a ailabili y o
he esponsible su geon. The goal is o maximize he numbe o su ge ies pe o med
o he u iliza ion o each ope a ing oom. A his poin , he sequence o su ge ies
in an ope a ing oom shi is neglec ed, since in his o mula ion, a e selec ing
pa ien s o a ope a ing oom shi , e e y sequence is possible. The sequence can be
ob ained using a simple naï e me hod.
The decision a iable used o schedule pa ien s in he ope a ing hea e o m o
he knapsack p oblem is dened by
xi d
, assigning pa ien
i
, o ope a ing oom
, on
day
d
and shi
. Ano he decision a iable was added o simul aneously schedule
su geons o he same ime and place o hei pa ien s:
yj d
, alloca ion su geon
j
, o
ope a ing oom
, on day
d
and shi
. The ma hema ical no a ion he ein used is
summa ized in Table 4.1.
The goal o his model o inc ease he eciency o he ope a ing oom ansla es,
in maximizing he numbe o su ge ies pe o med, o maximizing ope a ing oom
u iliza ion in he planning pe iod. The s goal can be dened by maximizing he
ollowing exp ession:
max 1=X
i∈NX
∈RX
d∈DX
∈T
xi d
(4.2)
Ye , inc easing he numbe o su ge ies pe o med educes he u iliza ion o op-
e a ing ooms due o he se up ime equi ed o p epa e and clean ope a ing ooms
be ween p ocedu es. Thus, i is also impo an o ha e he abili y o maximize he
u iliza ion a he expense o ha ing less su ge ies being pe o med. The ollowing ex-
p ession ep esen s he maximiza ion o he mean u iliza ion o all ope a ing ooms
in he planning ho izon.
Max 2=Pi∈NP ∈RPd∈DP ∈Txi d di
cP ∈RPd∈DP ∈TA d
(4.3)
40
Table 4.1: Ma hema ical no a ion used in he op imiza ion p oblem
Symbol Desc ip ion
N
Se o pa ien s
R
Se o ope a ing ooms
S
Se o su geons
D
Se o scheduling days
T
Se o shi s (mo ning/a e noon)
xi d
Assignmen o pa ien
i
, o ope a ing oom
, on day
d
and shi
yj d
Assignmen o su geon
j
, o ope a ing oom
, on day
d
and shi
Pi
Su geon esponsible o pa ien
i
di
Es ima ed du a ion o su ge y
i
A d
Ope a ing oom
a ailabili y, on day
d
, and shi
Ssd
Su geon
s
a ailabili y, on day
d
, and shi
u
Ope a ing oom clean up ime (cons an )
c
Shi capaci y (cons an )
As i was men ioned p e iously, su ge y scheduling is a complex p oblem subjec
o se e al cons ains. Fi s ly, gi en ha he e is a su geon esponsible o each
pa ien , his equi es a linking cons ain be ween he pa ien and su geon, which is
exp essed by equa ion 4.4:
xi d ≤yj d ,∀i∈N, ∈R, d ∈D, ∈T, j ∈S:j=Pi
(4.4)
Limi ing he capaci y o each ope a ing oom shi is equi alen o ha ing a sum
o su ge ies' du a ion and hei se up imes assigned o he ope a ing oom less o
equal o i s capaci y. This cons ain also de e mines he a ailabili y o an ope a ing
oom is a gi en day and shi , and i is dened by equa ion 4.5:
X
i∈N
xi d (di+u)≤A d c, ∀d∈D, ∈R, ∈T
(4.5)
The same a ailabili y cons ain applies o he su geons, whose a ailabili y is
dened in each day and shi . The cons ain ha deno es hei a ailabili y is gi en
in equa ion 4.6:
yj d ≤Sjd ,∀j∈S, d ∈D, ∈R, ∈T
(4.6)
To a oid su geons om ope a ing in die en ope a ing ooms in each shi , he
cons ain dened in equa ion 4.7 was implemen ed. By a oiding su geons changing
ope a ing ooms in a shi , he sequence o he su ge y can be neglec ed wi hou
unde mining he alidi y o he esul s.
41
X
∈RX
∈T
yj d ≤1,∀j∈S, d ∈D
(4.7)
Finally, equa ion 4.8 cons ain s he decision a iables o a bina y domain:
xi d , yj d ∈ {0,1}
(4.8)
4.2.2 Me a-heu is ic
Due o he ma hema ical complexi y in ol ed in sol ing he ma hema ical model
p e iously p esen ed, and o ee his wo k om p op ie a y so wa e, his wo k
yielded a simple gene ic algo i hm able o schedule su ge ies. In e ms o complexi y,
he mul i-knapsack bina y app oach ollowed, yields
2n d
possible solu ions o each
ins ance o he p oblem, a la ge ea u e space wi h exponen ial g ow h.
One o he ad an ages o de ising his me a-heu is ic was he abili y o ap-
ply specic business logic o i s sea ch mechanism, in o de o imp o e i s sea ch
pe o mance. Gene ic algo i hms' sea ch p ocedu e and he pa icula ea u es im-
plemen ed a e desc ibed below:
Ini ializa ion:
o ini ialize he algo i hm wi h a pool o good solu ions, he ini-
ializa ion o he popula ion was implemen ed so ha he p opo ion o pa ien s
assigned in each indi idual solu ion, co esponded o he expec ed numbe o su g-
e ies pe o med gi en he ope a ing oom a ailabili y and he su ge ies du a ion.
Addi ionally, p io i y pa ien s we e o ced o be selec ed in hal he popula ion.
Ope a o s:
he c osso e ope a ion implemen ed was a simple one-c osso e poin
andomly selec ed in each gene a ion o he algo i hm. The mu a ion ope a o was
implemen ed so ha he p obabili y o mu a ion o each gene was p opo ional o
he numbe o pa ien s wai ing o su ge y, allowing g ea e di e sica ion when
wai ing lis s a e longe .
Selec ion:
ega ding indi idual selec ion he s a egy known as eli is selec ion
was in oduced, whe e he es indi iduals o one gene a ion a e ca ied o wa d o
he nex . Howe e , eli ism was only applied o a pe cen age o he cases, he oule e
wheel selec ion mechanism was implemen ed, dening he indi iduals' p obabili y
o selec ion acco ding o hei ness.
Since gene ic algo i hms do no ha e he abili y o cons ain he p oblem di ec ly
as o he sol e s, cons ain s ha e o be inco po a ed in he objec i e unc ion. To
comply wi h he cons ain s dened, a penal y unc ion was added o he objec i e
unc ion o each cons ain , esul ing in a so -cons ain app oach.
42
4.3 Expe imen al esul s
The expe imen s conduc ed o alida e he op imiza ion me hodology, we e pe -
o med a e de e mining he su ge y du a ions using he bes da a mining model
de eloped. This ollows he logic encoun e ed in he su ge y scheduling p ocess,
whe e su geons ha e o s es ima e he du a ion o a su ge y and hen schedule
i . Bo h he exac app oach and he me a-heu is ic we e es ed in se e al su gical
special ies. Howe e , he lack o in o ma ion ega ding pos -ope a i e necessi ies
and capaci y o suppo pa ien s a e su ge y, he model was limi ed. Due o his
ci cums ances, only one su gical special y will be compa ed o eal schedules. The
Ou pa ien su ge y depa men is cha ac e ized o pe o ming ligh p ocedu es and
ha ing he abili y o le pa ien s eco e ou side medical acili ies. This ac enables
he compa ison o i s op imiza ion esul s o he eal schedules. Compa ing o he
special ies o eali y would be misleading, as he op imiza ion app oach, ha ing less
cons ain s, would no depic eal condi ions. None heless, o e i y he app oach
de eloped hey we e included in he expe imen s.
The exac app oach was sol ed using a well-known comme cial sol e ha allows
academic usage, CPLEX, and i was modeled using IBM ILOG Op imiza ion S udio,
e sion 12.6. The gene ic algo i hm was de eloped and an unde R, e sion 3.02.
The p oblem ins ances de eloped o es he wo sol e s simula e a eal scena io,
whe e, in a gi en pe iod, a medical special y has o schedule an en i e week o
su ge ies in i s alloca ed ime. These ins ances a e cha ac e ized by hei su geons,
he capaci y alloca ed o hem and hei pa ien wai ing lis . The pa ien s a e
dened by hei p io i y and he es ima ed su ge y du a ions de e mined by he da a
mining app oach. Fo each medical special y es ed, one ins ance o he p oblem was
c ea ed. In he con ex o his p oblem, his scena io is limi ed o one week, because
he da a a ailable is a snapsho o he sys em in a gi en pe iod. I would no be
easible o c ea e mo e ins ances as i would equi e simula ing pa ien a i als.
Finally, e e y ins ance is dened o ha ing ope a ing ooms wi h 6 hou s shi s,
co esponding o he mo ning pe iod be ween 8am and 2pm and he a e noon pe iod
om 2pm o 8pm. The pa icula cha ac e is ics o each ins ance can be ound in
Table 4.2.
Each ins ance o he p oblem will be sol ed wi h he objec i e unc ions p e i-
ously desc ibed, one o maximize he numbe o su ge ies pe o med (
1
) and he
second o maximize he u iliza ion o he ope a ing ooms (
2
). The esul s and
he compa ison be ween he exac and app oxima e app oach is gi en below in Ta-
ble 4.3. Since exac app oaches can un o a long ime, due o he disc e e and
combina o ial na u e o his p oblem, he sol ing p ocedu e was limi ed o un du -
ing one hou . I no solu ion was ound in ha pe iod, he gap o he uppe bound
o he op imal solu ion was de e mined. The gene ic algo i hm was se o un o 1
000 gene a ions, and Figu e 4.1 depic s he ness e olu ion du ing one un.
43
Table 4.2: Cha ac e is ics o he op imiza ion ins ances
Special y N. Pa ien s N. Su geons N. Shi s To al A ailable Time (m)
De ma ology (D) 52 8 6 2 160
Gene al Su ge y (GS) 224 17 9 3 240
Neu o Su ge y (NS) 297 15 20 7 200
O hopedics (ORT) 197 8 7 2 520
O ola yngology (ENT) 505 17 8 2 880
U ology (URO) 289 20 11 3 960
Vascula Su ge y (VS) 1 057 20 7 2 520
Ou pa ien Su ge y (OS) 394 8 5 1 800
Figu e 4.1: Fi ness e olu ion h oughou 1 000 gene a ions
44
Table 4.3: Op imiza ion esul s o he cons ained su ge y special ies
CPLEX Gene ic Algo i hm
Ins ance # Su ge ies U iliza ion Gap # Su ge ies U iliza ion Va . Cplex
D-F1 19 79% 0.0% 19 79% 0.0%
D-F2 17 85% 0.0% 17 85% 0.0%
GS-F1 51 72% 0.0% 28 84% -43.1%
GS-F2 18 90% 1.0% 29 86% -4.2%
NS-F1 57 83% 7.6% 39 91% -31.6%
NS-F2 40 90% 1.1% 39 91% 0.6%
ORT-F1 35 75% 0.0% 23 85% -34.3%
ORT-F2 14 90% 0.0% 23 85% -5.9%
ENT-F1 45 70% 3.4% 27 84% -40.0%
ENT-F2 17 88% 1.9% 23 85% -3.4%
URO-F1 68 70% 0.0% 43 81% -36.8%
URO-F2 22 89% 1.3% 42 80% -10.8%
VS-F1 35 74% 0.0% 31 81% -11.4%
VS-F2 14 89% 0.0% 33 80% -10.4%
Al hough he esul s canno be compa ed o he eal schedules, hey a e im-
po an as hey show ha bo h app oaches achie e easible and appa en ly good
solu ions. These esul s also demons a e ha he exac app oach can ob ain op-
imal solu ions mos o he ime. The e is only one ins ance (NS1-F2) whe e he
gene ic algo i hm ou pe o ms he exac app oach. Howe e , CPLEX could no
achie e an op imal solu ion in he p oposed unning ime. The gene ic algo i hm
was able o achie e he same solu ions as CPLEX on he wo ins ances o De ma-
ology. This is likely ela ed o he ac ha De ma ology has he lowes mean
su ge y du a ion, which may de e mine he dicul y o sol e he p oblem. I is also
possible o obse e, as expec ed, ha ha ing a g ea e numbe o su ge ies leads o
a smalle u iliza ion o he ope a ing oom due o he se up ime be ween su ge ies.
This is a consequence o scheduling sho e su ge ies when maximizing he numbe
o su ge ies, and longe su ge ies when u iliza ion is maximized.
Finally, o compa e his app oach o eali y, Table 4.4 below, p esen s he esul s
conce ning he ou pa ien su ge y depa men .
Table 4.4: Op imiza ion esul s o he ou pa ien su ge y special y
Reali y CPLEX Gene ic Algo i hm
Ins ance # Su ge ies U iliza ion # Su ge ies U iliza ion # Su ge ies U iliza ion
ODF1 18 40% 36 61% 29 52%
ODF2 18 40% 15 84% 14 79%
These esul s show a signican gain in pe o mance compa ed o eali y, and
45
bo h sol ing app oaches could bea he eal ou pa ien depa men schedule. The
ou comes o his op imiza ion un indica e a wo- old inc ease in su ge ies pe o med
when using CPLEX and an inc ease in u iliza ion o a leas 50%. The same obse -
a ion s ill applies, indica ing ha ha ing less bu longe su ge ies leads o highe
u iliza ion due o he educ ion o p epa a ion ime be ween su ge ies.
46
Chap e 5
Conclusions
Al hough he o e ime wo k incen i e in oduced by he Po uguese go e nmen in
2006 helped o educe wai ing imes o su ge y, his measu e ca ied an excessi e
cos and didn' achie e a eal ecien sys em. This wo k add esses a p oblem o
op imizing ope a ing oom su ge y schedules wi h he in eg a ion o da a mining
and op imiza ion echniques in he scheduling p ocess. The me hodology de eloped
esul ed in an ensemble da a mining model able o es ima e su ge y du a ions and a
ma hema ical model ep esen ing he ope a ing oom scheduling p ocess. Fu he ,
o sol e his ma hema ical model, an e olu iona y me a-heu is ic was de ised and
compa ed agains an exac op imiza ion app oach.
The no el y in oduced in his wo k de i es om he in eg a ion o hese wo
echniques and i s abili y o be applied o any su gical special y. The esul s in-
dica e signican gains in he pe o mance o he ope a ing hea e , an ou come o
educing he o e - and unde -es ima ion e o s in su ge y du a ions, and inc easing
he h oughpu and u iliza ion o he ope a ing hea e . This chap e summa izes
he conclusions om his wo k and sugges s opics o u u e esea ch.
5.1 Su ge y du a ion es ima ion
In his wo k, se e al da a mining models we e assessed o compa e hei p edic ion
pe o mance o su ge y du a ions.
This assessmen led o an ensemble o he en i e pool o models es ed, c ea ing
a new lea ne based on he esul s o he ini ial base models. The esul s o he en-
semble we e used o es ima e he nal du a ion o su ge ies. The pe o mance o he
models was compa ed agains he es ima es made by su geons and he eal su ge y
du a ions, showing imp o emen s o up o 47% compa ed o he mean absolu e e -
o o he su geon es ima es. These esul s also educe ex emely la ge de ia ions,
shown by he dec emen o he oo mean squa ed e o o he es ima es.
Despi e he gene alized e o educ ion o e e y su gical special y, his app oach
47
Ma ques, I., Cap i o, M., and Vaz Pa o, M. (2012). An in ege p og amming ap-
p oach o elec i e su ge y scheduling.
OR Spec um
, 34(2):407427.
May, J. H., S um, D. P., and Va gas, L. G. (2000). Fi ing he logno mal dis ibu-
ion o su gical p ocedu e imes*.
Decision Sciences
, 31(1):129148.
Nelde , J. A. and Bake , R. (1972).
Gene alized linea models
. Wiley Online Lib a y.
New Yo k S a e, D. o. H. (2014). S a ewide planning and esea ch coope a i e
sys em.
h p://www.heal h.ny.go /s a is ics/spa cs
.
Obenshain, M. K. (2004). Applica ion o da a mining echniques o heal hca e da a.
In ec ion Con ol and Hospi al Epidemiology
, 25(8):690695.
OECD (2011).
Heal h a a Glance 2011: OECD Indica o s
. OECD Publishing.
Oli ei a, M. (2004). Modelling demand and supply inuences on u iliza ion: a ow
demand model o p edic hospi al u iliza ion a he small a ea le el.
Applied
economics
, 36(20):22372251.
Pa o, M. V. and Moz, M. (2008). Sol ing a bi-objec i e nu se e os e ing p oblem
by using a u opic pa e o gene ic heu is ic.
Jou nal o Heu is ics
, 14(4):359374.
Pea son, L. (1933). P ac ical p oblems in hospi al planning.
I ish Jou nal o Medical
Science
, 8(5):193197.
Peek, N. (2010).
Da a Mining
, chap e 24, pages 24.124.17. Handbook o Heal hca e
Deli e y Sys ems. CRC P ess.
Quinlan, J. R. e al. (1992). Lea ning wi h con inuous classes. In
P oceedings o
he 5 h Aus alian join Con e ence on A icial In elligence
, olume 92, pages
343348. Singapo e.
Resea ch, N. I. C. O. (2014). Na ional adul ca diac su ge y audi .
h p://www.
ucl.ac.uk/nico /audi s/adul ca diac/da ase s
.
Robbins, W. A. and Tun iwongpiboom, N. (1989). Linea p og amming a use ul
ool in case-mix managemen .
Heal hca e nancial managemen : jou nal o he
Heal hca e Financial Managemen Associa ion
, 43(6):114.
Shamayleh, A., Fowle , J., and Zhang, M. (2012). Ope a ing oom capaci y planning
decisions. In
Wo ld Academy o Science, Enginee ing and Technology, 64
.
Spangle , W., S um, D., Va gas, L., and May, J. (2004). Es ima ing p ocedu e
imes o su ge ies by de e mining loca ion pa ame e s o he logno mal model.
Heal h Ca e Managemen Science
, 7(2):97104.
54
Spe andio, F., Gomes, C., Bo ges, J., B i o, A. C., and Almada-Lobo, B. (2013).
An in elligen decision suppo sys em o he ope a ing hea e : A case s udy.
Au oma ion Science and Enginee ing, IEEE T ansac ions on
, PP(99):11.
S epaniak, P. S., Heij, C., and De V ies, G. (2010). Modeling and p edic ion o
su gical p ocedu e imes.
S a is ica Nee landica
, 64(1):118.
S um, D. P., May, J. H., and Va gas, L. G. (2000). Modeling he unce ain y o
su gical p ocedu e imes: compa ison o log-no mal and no mal models.
Anes he-
siology
, 92(4):11601167.
Tes i, A., Tan ani, E., and To e, G. (2007). A h ee-phase app oach o ope a ing
hea e schedules.
Heal h Ca e Managemen Science
, 10(2):163172.
Thomas, R. (2003).
The social and heal h sys ems con ex o heal h se ices plan-
ning
. Sp inge .
Tu e, E. R. and Weise Moelle , E. (1997).
Visual explana ions: images and quan-
i ies, e idence and na a i e
. G aphics P ess Cheshi e, CT.
Viei a, S. M., Mendonça, L. F., Fa inha, G. J., and Sousa, J. M. (2013). Modied
bina y pso o ea u e selec ion using s m applied o mo ali y p edic ion o sep ic
pa ien s.
Applied So Compu ing
, 13(8):3494 3504.
Visse s, J., Adan, I. J., and Bekke s, J. A. (2005). Pa ien mix op imiza ion in ac-
ical ca dio ho acic su ge y planning: a case s udy.
IMA Jou nal o Managemen
Ma hema ics
, 16(3):281304.
Wilson, A. M., Thabane, L., and Holb ook, A. (2004). Applica ion o da a min-
ing echniques in pha maco igilance.
B i ish Jou nal o Clinical Pha macology
,
57(2):127134.
W igh , I. H., Koope be g, C., Bona , B. A., and Bashein, G. (1996). S a is ical
modeling o p edic elec i e su ge y ime: compa ison wi h a compu e scheduling
sys em and su geon-p o ided es ima es.
Anes hesiology
, 85(6):12351245.
Wullink, G., Van Houdenho en, M., Hans, E. W., an Oos um, J. M., an de
Lans, M., and Kazemie , G. (2007). Closing eme gency ope a ing ooms imp o es
eciency.
Jou nal o Medical Sys ems
, 31(6):543546.
Zhou, J., Dex e , F., Maca io, A., and Luba sky, D. A. (1999). Relying solely on
his o ical su gical imes o es ima e accu a ely u u e su gical imes is unlikely o
educe he a e age leng h o ime cases nish la e.
Jou nal o Clinical Anes hesia
,
11(7):601 605.
55