The s a scheduling p oblem: a gene al
model and applica ions
Ma a Soa es Fe ei a da Sil a Rocha
A Thesis submi ed o Faculdade de Engenha ia da Uni e sidade do Po o
o he doc o al deg ee in Indus ial Enginee ing and Managemen
Supe iso s
P o esso Jos´e Fe nando da Cos a Oli ei a
P o esso Ma ia An ´onia da Sil a Lopes de Ca a illa
Faculdade de Engenha ia da Uni e sidade do Po o
2013
Abs ac
The scheduling o employees is a complex and ime-consuming ask. I is
complex because i in ol es assigning he igh people o he igh job a
he igh ime. I is condi ioned by se e al legal, wo k and o he o gani-
za ional ules. And i o en copes wi h con lic ing objec i es, such as he
minimiza ion o he labo cos s o he wo k o ce size and he sa is ac ion o
he employees p e e ences, o example. I is ime-consuming because i is
a pe iodic ask and i is s ill manually pe o med in mos o ganiza ions.
The esea ch wo k desc ibed in his hesis deals wi h he de elopmen o
me hods o he au oma ic scheduling o employees, in pa icula o hei
simul aneous assignmen o wo king shi s and days-o . The wo k ocuses
on he design o a gene al in ege p og amming (IP) model ha , ollowing
an op imiza ion app oach, can be easily adap ed and sol e a wide se o
di e en eal-wo ld p oblems. An inno a i e o mula ion o he sequence and
consecu i eness cons ain s gi es he model he lexibili y o accommoda e
a iable ea u es o he p oblems. A cyclic app oach ensu es he gene a ion
o equi able and p edic able wo k schedules.
The applica ion o he gene al model is illus a ed wi h h ee eal-wo ld
case s udies and a collec ion o benchma k ins ances a ailable in he li -
e a u e. Compu a ional esul s demons a e he good pe o mance o he
model, achie ing op imal solu ions o he majo i y o he p oblems in use ul
ime.
A cons uc i e heu is ic is also de eloped o sol ing one o he case-s udies.
Based on a se o simple calcula ions, he p oposed p ocedu e e eals o
be an e icien al e na i e o he IP op imiza ion app oach o sol ing he
p ac ical p oblem conside ed. The good pe o mance achie ed wi h es s on
a se o la ge compu e gene a ed ins ances con i ms he obus ness o his
app oxima e app oach.
Al hough i s appa en pe inency o he ac i i y sec o , s a scheduling
p oblems in hospi ali y managemen ha e been qui e unno iced by he e-
sea ch communi y. This hesis dedica es a chap e o his opic, namely o
he assessmen o he po en ial o hospi ali y managemen as an applica ion
a ea o s a scheduling p oblems and o possible esolu ion app oaches.
i
ii
Resumo
O escalonamen o de pessoal ´e uma a e a complexa e o emen e consumi-
do a de ecu sos. ´
E complexa po que en ol e a a e a¸c˜ao das pessoas ce as
ao abalho ce o no momen o ce o. ´
E condicionada po di e sas eg as de
na u eza legal, labo al ou o ganizacional. Lida no malmen e com obje i os
di e gen es, ais como a mimimiza¸c˜ao de cus os ou a dimens˜ao da equipa
de abalho e a sa is a¸c˜ao das p e e ˆencias dos abalhado es, po exemplo.
Consome ecu sos po que ´e ei a pe iodicamen e e ainda de modo manual,
em mui as o ganiza¸c˜oes.
O abalho de in es iga¸c˜ao desc i o nes a ese abo da o desen ol imen o de
m´e odos pa a o escalonamen o au om´a ico de pessoal, em pa icula com a
sua a e a¸c˜ao simul ˆanea a u nos de abalho e dias de descanso. O abalho
cen a-se no desen ol imen o de um modelo ge al de p og ama¸c˜ao in ei a
que, seguindo uma abo dagem de o imiza¸c˜ao, pode se acilmen e adap ado
e esol e um conjun o ala gado de di e en es p oblemas eais. A o mula¸c˜ao
ino ado a das es i¸c˜oes de sequˆencia e consecu i idade con e e ao modelo
a lexibilidade necess´a ia pa a acomoda ca ac e ´ıs icas a i´a eis dos p ob-
lemas. Uma abo dagem c´ıclica assegu a a ge a¸c˜ao de ho ´a ios equilib ados
e p e is´ı eis.
A aplica¸c˜ao do modelo ge al ´e ilus ada a a ´es de ˆes casos de es udo
baseados em p oblemas eais e de um conjun o de ins ˆancias de benchma k
dispon´ı eis na li e a u a. Os esul ados compu acionais demons am o bom
desempenho do modelo, ob endo as solu¸c˜oes ´o imas pa a a maio pa e dos
p oblemas em empo ´u il.
Uma heu ´ıs ica cons u i a oi amb´em desen ol ida pa a um dos casos de
es udo. Baseado num conjun o de c´alculos simples, o p ocedimen o p o-
pos o e ela se uma al e na i a e icien e `a abo dagem de o imiza¸c˜ao pa a a
esolu¸c˜ao do p oblema p ´a ico conside ado. O bom desempenho conseguido
com es es em ins ˆancias de maio dimens˜ao comp o a a obus ez des e
m´e odo ap oximado.
Apesa da sua apa en e pe inˆencia pa a o sec o de a i idade, os p oble-
mas de escalonamen o de pessoal na ´a ea de ges ˜ao da hospi alidade n˜ao
ˆem me ecido a de ida a en¸c˜ao po pa e da comunidade acad´emica. Es a
ese dedica um dos seus cap´ı ulos a es e ´opico, nomeadamen e `a a alia¸c˜ao
do po encial da ges ˜ao da hospi alidade como uma ´a ea de aplica¸c˜ao pa a
os p oblemas de escalonamen o de pessoal e de poss´ı eis abo dagens de es-
olu¸c˜ao.
iii

i
Acknowledgmen s
This hesis is he culmina ion o he wo k accomplished du ing he mos
demanding phase o my pe sonal li e. Du ing hese ou yea s, I el my
physical and emo ional endu ance being s ained o he limi . I I succeeded
and eached his a I owe i o he people ha suppo ed me in his jou ney,
o whom I he e add ess my since e acknowledgmen s.
Fi s o all, I would like o hank my supe iso s, Jos´e Fe nando Oli ei a
and Ma ia An ´onia Ca a illa, o us ing me his excep ional oppo uni y
o edi ec he cou se o my ca ee . I was a p i ilege o be pa o you
esea ch g oup bu also o be pa o you eaching g oup. I can now know
how i eels o be on he o he side o he class oom desk. I was a eally
en iching expe ience ha allowed me o de elop new compe ences. Thank
you o keeping me always ocused and mo i a ed. Thank you o you
dedica ion. Thank you o ca ing.
My second acknowledgmen goes o all he colleagues om he IO Lab. Some
ha e al eady le . Some ha e jus a i ed. O he s come and go. O he s a e
he e o s ay. Al hough I missed a lo o lunches, dinne pa ies and e ening
ou s, I eally enjoyed he company o e e y one o you. Thank you o you
unde s anding and ca ing.
I mus also hank Miguel Gomes, my “Mac ad ise ”, o his a ailabili y and
help.
A hea el hanks o Ve a, wi h whom I sha ed his pa h since he i s day.
You ha e been an ou s anding iend. Thank you o all he co ees, all he
alks, all he help. Thank you o being always he e.
I hank my pa en s, b o he and in-laws o gi ing me he necessa y condi-
ions o ca y ou his p ojec , especially du ing hese las 1,5 yea s. Thank
you o you uncondi ional suppo .
I dedica e his hesis o And ´e, Ma ilde and Bea iz. Thank you o you
in ini e lo e.
i
Table o Con en s
Abs ac i
Resumo iii
Acknowledgemen s
Table o Con en s ii
Lis o Figu es x
Lis o Tables xi
1 In oduc ion 1
1.1 Mo i a ion ............................ 1
1.2 Resea ch app oach . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Thesisou line........................... 5
2 S a scheduling p oblems 7
2.1 De ining he p oblem . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Modeling he p oblem . . . . . . . . . . . . . . . . . . . . . . 14
2.3 Re iewing ela ed wo ks in he li e a u e . . . . . . . . . . . . 20
2.3.1 Su eys and gene al wo ks . . . . . . . . . . . . . . . . 20
2.3.2 Speci ic wo ks . . . . . . . . . . . . . . . . . . . . . . . 24
2.4 Summa y ............................. 32
ii
LIST OF FIGURES
xi

Lis o Tables
4.1 Example o a possible sequence o shi s . . . . . . . . . . . . 48
5.1 Sequence o shi s o he glass p oduc ion uni . . . . . . . . 57
5.2 Model size and compu a ional imes o a 5- eam schedule . . 60
5.3 Annual numbe o wo k-days o each eam . . . . . . . . . . 61
6.1 Sequence o shi s o he con inuous ca e uni . . . . . . . . . 67
6.2 Model compu a ional pa ame e s and esul s o he con in-
uousca euni ........................... 70
7.1 Minimum/maximum no. o nu ses equi ed daily o each shi 76
7.2 Types o con ac s . . . . . . . . . . . . . . . . . . . . . . . . 76
7.3 Sequence o shi s o he hospi al p oblem . . . . . . . . . . . 77
7.4 Associa ion o index o he ype o con ac . . . . . . . . . 79
7.5 S a is ic analysis o he solu ions . . . . . . . . . . . . . . . . 82
8.1 Fi s ype o allowable sequences . . . . . . . . . . . . . . . . 89
8.2 Allowable sequences . . . . . . . . . . . . . . . . . . . . . . . 89
8.3 Allowable sequences o nS=2 . . . . . . . . . . . . . . . . . . 90
8.4 Compu a ional imes o he benchma king ins ances using
he IP model, MC-T and FCS . . . . . . . . . . . . . . . . . . 94
9.1 Compu a ional esul s o 5 eams . . . . . . . . . . . . . . . 105
9.2 Compu a ional esul s o a se o combina ions o he a io
nS/nT. ..............................110
x
LIST OF TABLES
x i
Chap e 1
In oduc ion
1.1 Mo i a ion
S a scheduling is a common p oblem o mos o ganiza ions, ei he om
he se ice sec o o indus ial plan s. Basically, i seeks o assign employ-
ees o asks, wo k shi s o es pe iods, aking in o accoun o ganiza ional
and legal ules, employees’ skills and p e e ences, demand needs, and o he
applicable equi emen s. I is he e o e a complex p oblem and a op con-
ce n o human esou ce managemen (Enz (2009)). E en nowadays, i is
s ill done manually in se e al ac i i y sec o s, consuming ime and esou ces
ha could be used mo e e icien ly wi h au oma ic scheduling gene a o s.
Thompson (2003) poin s ou h ee easons o ca ing abou s a scheduling:
he ime spen de eloping a schedule by hand lea es he manage less ime
o managing he employees and in e ac ing wi h he cus ome s; a schedule
ha be e sa is ies employees’ p e e ences inc eases he on-job-pe o mance
and consequen ly he p oduc i i y and he se ice quali y; in a good sched-
ule wo k is assigned in he mos e ec i e manne , leading o a cos educ ion
due o o e and unde s a ing and an inc ease in p o i abili y. I is no only a
ma e o educing cos s, bu also a ma e o inding a solu ion ha be e
i s cos minimiza ion, compliance wi h wo k and legal ules, sa is ac ion
1
Chap e 1. In oduc ion
and well- a e o employees. The design o schedules should ake he e o e
in o accoun objec i e ac o s such as labou cos s, applicable legisla ion, o -
ganiza ional ules and demand needs bu also o he sensi i e dimensions like
lexibili y, s abili y, p edic abili y o ai ness. I is gene ally acknowledged
he signi ica i e impac ha hese las a ibu es can ha e on he p oduc-
i i y and engagemen o an employee (Glass and Knigh (2010)). S ess ul
ac o s such as sho pe iods o es and long pe iods o wo k, inadequa e dis-
ibu ion be ween es and wo k pe iods o non-s anda d wo king shi s, o
example, can nega i ely a ec he men al and physical heal h o employees
(To e dell (2005)).
Al hough he s a scheduling p oblem has been in ensi ely explo ed in he
li e a u e, s udies usually ocus on sol ing e y pa icula p oblems ha de-
i e om p ac ical needs. Models a e usually de eloped o speci ic applica-
ions and hei adap a ion o o he cases implies signi ica i e e o mula ion.
I is gene ally conside ed by esea che s ha cyclic scheduling app oaches
a e in lexible because hey impose a igid schedule, no adjus able o unp e-
dic able changes. Wo kload balance is usually ackled as a non-manda o y
o so cons ain o he p oblem. When dealing wi h eal-li e p oblems, he
end has been o use app oxima e solu ion app oaches a he han op i-
miza ion me hods. This is mainly due o hei high complexi y and size.
Howe e such app oxima e p ocedu es a e, by na u e, ailo ed o speci ic
p oblems.
This esea ch has a wo old mo i a ion. F om a business pe spec i e, i
aims o con ibu e o he inc ease in bo h p oduc i i y and p o i abili y o
a company. The de elopmen o an au oma ic scheduling p ocedu e and
he adequa e design o he schedules con ibu es o hese goals. F om an
academic poin o iew, his wo k aims o p o ide a wide- ange app oach
ha is able o ind op imal solu ions o di e en eal-li e p oblems. I
in ends o be inno a i e, combining an o iginal o mula ion o he sequence
2
1.2 Resea ch app oach
and consecu i eness cons ain s wi h a lexible cyclic scheduling app oach.
1.2 Resea ch app oach
The main objec i e o he esea ch wo k desc ibed in his hesis is o de-
elop an op imiza ion model ha can be easily adjus ed o add ess di e en
eal-li e s a scheduling p oblems, om di e en applica ion a eas. This
goal imposes a p elimina y in es iga ion in o he cu en li e a u e on s a
scheduling p oblems in o de o unde s and he p oblem in dep h and o
jus i y he ele ance o he p oposed app oach. An addi ional ou pu o his
li e a u e e iew is he insigh in o he pa icula applica ion o hese p ob-
lems o hospi ali y managemen ope a ions, which is an almos unexplo ed
combina ion.
S imula ed by h ee eal case-s udies, he esea ch concen a es on sol -
ing he p oblem o simul aneously assigning employees o wo k shi s and
days-o in each o he h ee applica ions. The p oblems ha e simila wo k
en i onmen s based on a 24-hou con inuous ope a ion and wo k shi s wi h
ixed s a ing- imes and leng hs. The wo k o ce is single-skilled in wo o
he p oblems, bu in one o he case-s udies mul i-skilled employees a e
g ouped in eams and he scheduling is made o each eam, which is a no el
modelling aspec . While in one o he cases he s a is composed only by
ull- ime employees, he o he wo p oblems conside di e en ypes o la-
bo con ac s. Cons ain s common o all p oblems conce n daily demand
equi emen s, sequences o wo k shi s and days-o and consecu i e numbe
o wo k shi s/days-o . Long weekends-o pe iodici y and planned absences
a e occasionally ackled in di e en case-s udies.
Each one o he h ee p oblems has a di e en sequence o shi s and days-o
ha mus be ollowed and he wo kload mus be e enly dis ibu ed be ween
all he employees. These wo condi ions ep esen he main modelling chal-
3

Chap e 1. In oduc ion
lenges o his wo k. The way hey a e deal wi h in he p oposed o mula ion
in ends o be a wo hy con ibu ion o he esea ch li e a u e. The sequence
and consecu i eness cons ain s a e o mula ed in a e y inno a i e way ha
gi es he model an inc eased lexibili y o ackle any pa e n o wo k shi s
and days o . The wo kload balance is ensu ed by he cyclic scheduling
app oach, h ough a ha d cons ain . To coun e ac he in lexibili y o en
assigned o cyclic scheduling, i is used o success ully sol e p oblems ha
a e ypically add essed wi h acyclic app oaches, namely p oblems wi h a
he e ogeneous wo k o ce and luc ua ing demand le els.
Ins ead o se ing he planning ho izon as an inpu o he p oblem, as is
he common p ac ice in he li e a u e, we s udy se e al planning pe iods
in o de o choose he planning ho izon ha be e i s he goals o he
p oblem. We explo e he in eg a ion o pe iods wi h di e en leng hs in o
a longe planning ho izon. This is ano he o iginal con ibu ion o his
esea ch.
The de eloped in ege p og amming (IP) gene al model is success ully ap-
plied o he h ee case-s udies wi h mino adjus men s, mainly pa ame e i-
za ions. In o de o demons a e i s consis ency and ein o ce i s lexibili y,
he model is also adap ed o sol e a collec ion o benchma k ins ances.
The s udy o a heu is ic app oach aims o en ich he con ibu ion o his
esea ch wi h a compa ison be ween an op imiza ion and an app oxima e
me hod o sol ing one o he eal-wo ld case-s udies. The heu is ic p oce-
du e is based on simple calcula ions and assump ions ha de i e om he
analysis o he p oblem’s inpu da a. Al hough i is buil o a pa icula
p oblem, he heu is ic demons a es a consis en pe o mance when applied
o a se o la ge compu e gene a ed ins ances, which esul om he a i-
a ion o some o he pa ame e s, e ealing o be a iable al e na i e o he
op imiza ion me hod.
4
1.3 Thesis ou line
1.3 Thesis ou line
The hesis is o ganized a ound 9 chap e s, besides he p esen in oduc o y
chap e .
Chap e 2 p esen s a comp ehensi e o e iew on he s a scheduling p ob-
lem, i s main ea u es, a ian s and mos common applica ions. Some el-
e an modeling issues a e add essed and he ela ed li e a u e is e iewed.
The aim is o p o ide essen ial backg ound on he opic.
Chap e 3 is de o ed o a s udy on hospi ali y managemen , wi h he pu pose
o unde s anding he concep o hospi ali y and explo ing he po en ial o
his ac i i y sec o as an applica ion a ea o s a scheduling p oblems.
Chap e s 4, 5, 6, 7 and 8 conce n he de eloped op imiza ion app oach.
The gene al IP model is i s ly in oduced in Chap e 4. The nex h ee
chap e s illus a e he applica ion o he gene al IP model o h ee p ac ical
case s udies, one om an indus ial plan and wo om se ices. Chap e
5 epo s a long- e m s a scheduling p oblem in a glass p oduc ion uni .
Then, he gene al model is adjus ed o he p oblem o scheduling a se o
ca e ake s in a con inuous ca e uni (Chap e 6). Chap e 7 conce ns he
p oblem o nu se scheduling in a po uguese hospi al. In Chap e 8, he
gene al model is adjus ed o a se o benchma k ins ances. The applica ion
o he model is ex ended o a ange o p oblems wi h la ge size, es ing he
consis ency o he model’s pe o mance.
Chap e 9 p esen s a cons uc i e heu is ic o sol e he glass uni p oblem. A
compa ison be ween his app oach and he p e ious op imiza ion app oach
is ca ied ou .
The las chap e (Chap e 10) sums up he accomplished esea ch wo k and
sugges s u u e de elopmen s.
5
Chap e 1. In oduc ion
6
Chap e 2
S a scheduling p oblems
The aim o his chap e is o p o ide some impo an backg ound in o ma-
ion on s a scheduling p oblems o a eade who is no deeply amilia wi h
he subjec . The i s sec ion p esen s he s a scheduling p oblem in de ail,
desc ibing he sub-p oblems and he applica ion a eas ha ha e been mo e
explo ed in he li e a u e. Nex , an o e iew on he main modeling issues
is included. The las sec ion o he chap e goes h ough some o he mos
ele an ela ed wo ks published in he li e a u e o s a scheduling, om
su eys and gene al s udies o mo e speci ic esea ch pape s.
2.1 De ining he p oblem
W en (1996) de ines scheduling as “ he alloca ion, subjec o cons ain s, o
esou ces o objec s being placed in space- ime, in such a way as o mini-
mize he o al cos o some se o he esou ces used” and os e ing as “ he
placing, subjec o cons ain s, o esou ces in o slo s in a pa e n. One may
seek o minimize some objec i e, o simply o ob ain a easible alloca ion.
O en he esou ces will o a e h ough a os e . (...) Once shi s ha e been
p oduced showing he daily wo k o pe sonnel, hese shi s a e placed in o
a os e o show which shi s a e wo ked by indi iduals on pa icula days”.
7
Chap e 2. S a scheduling p oblems
p oblem, whe e ime ables usually epea on a weekly basis. In he oppo-
si e si ua ion a e call cen e s, whe e demand luc ua es e e y week and so
schedules a e ypically acyclic. Cyclic scheduling has he ad an ages o p o-
iding an equal dis ibu ion o shi s and days-o among all employees and
o p o iding s abili y, since employees know hei schedule some ime in ad-
ance and can plan hei li es acco ding o hei u u e a ailabili y. On he
o he hand, hey lack lexibili y, being much less adjus able o las -minu e
changes.
2.2 Modeling he p oblem
Di e en wo k en i onmen s imply di e en equi emen s and, consequen ly,
s a scheduling p oblems wi h dis inc ea u es na u ally a ise. Some o he
main di e en ia ing dimensions ha ha e been explo ed in he li e a u e
a e:
• he adop ed planning pe iod, which can ange om ew days o se e al
weeks o mon hs up o one yea , o can be use -de ined;
• he ope a ing hou s o he o ganiza ion, which can wo k in a 24-hou s
con inuous o in a less han 24-hou s discon inuous ope a ion;
• he wo k o ce, which can be composed o employees wi h: single o
mixed con ac ypes ( ull- ime/pa - ime), di e en skills, dis inc
p oduc i i y le els, di e en a ailabili y and/o indi idual pe sonal
p e e ences; employees subs i u abili y ules, based on hie a chy o on
speci ic skills o example, may be conside ed;
•shi lexibili y: wo king shi s can be ixed o can a y in e ms o
s a ing- ime, leng h, placemen and/o du a ion o b eaks; o e lap
be ween shi s may be conside ed.
14

2.2 Modeling he p oblem
The p oblems add essed by his esea ch wo k ha e a 24-hou s con inuous
mul i-shi en i onmen , wi h all shi s ha ing ixed s a ing- imes, leng hs
and b eaks placemen . The e o e, shi lexibili y is no conside ed. In e ms
o wo k o ce, he p oblems a y: he glass uni and he hospi al conside
only a ixed ull- ime se o wo ke s while he con inuous ca e uni conside s
bo h ull and pa - ime wo k, which can a y acco ding o he demand
equi emen s. Mixed skills a e no conside ed bu in he hospi al case s udy
wo ke s ha e di e en con ac ypes ha mus be aken in o accoun when
modeling he p oblem. The planning pe iod is no ixed. Se e al pe iods
we e es ed in o de o ind he one ha allowed o a be e solu ion, i.e.,
a be e schedule.
When modeling he p oblem, cons ain s and objec i es also a y acco ding
o he p oblem’s ea u es. Types o cons ain s ha a e o en ound in he
li e a u e include:
•co e age: minimum/maximum numbe o assignmen s equi ed/allowed
pe shi o pe week day o o he planning in e al;
•consecu i eness o sequence: manda o y by law o p e e ed by he em-
ployees, ex. maximum/minimum numbe o consecu i e wo king/ es
days, compulso y pa e ns o wo king shi s and days-o (s in s), day(s)
o a e a nigh shi , e c.;
•weekends: weekends o pe iodici y, compensa ion o weekends assign-
men s by week days-o , long weekends;
•wo kload balance: e en dis ibu ion o shi s/days-o be ween all he
employees.
Cons ain s can be ea ed ei he as ha d cons ain s, i hei sa is ac ion
is manda o y, o o he wise as so cons ain s,. The non- ul illmen o so
15
Chap e 2. S a scheduling p oblems
cons ain s is o en penalized, o example in he objec i e unc ion when
using ma hema ical p og amming models o in he e alua ion unc ion in a
me aheu is ic app oach.
The models p oposed in his wo k conside all hese ypes o cons ain s
as ha d cons ain s. Emphasis is ye gi en o he o mula ion o sequence
cons ain s ha , o he bes o ou knowledge, has no been p oposed be o e
in he li e a u e. The wo kload balance is a main conce n o all he p oblems
add essed. Weekend-o pe iodici y cons ain s we e conside ed in he glass
indus y case s udy and he hospi al model was ex ended in o de o accoun
o planned absences.
Types o objec i es ha a e o en used o model he s a scheduling p oblem
include:
• o minimize o al labou cos s;
• o maximize he pe cen age o he con ac ual wo k hou s assigned o
o minimize he pe cen age o he unassigned hou s;
• o minimize wo k o ce size;
• o minimize he gap be ween assignmen s and demand (unde o o e
co e age);
• o minimize he gap be ween assignmen s and employees’ p e e ences;
• o balance he wo kload be ween employees;
• o maximize employees sa is ac ion.
Al hough ha ing di e en objec i e unc ions, all he p oblems s udied in
his wo k sha e he goal o achie ing a balanced and ai schedule o all
wo ke s. In he glass uni p oblem his is di ec ly o mula ed in he objec i e
unc ion. In he con inuous ca e uni p oblem, he objec i e unc ion seeks o
16
2.2 Modeling he p oblem
minimize he pa - ime equi emen s. In he hospi al p oblem, he objec i e
unc ion looks o he minimiza ion o he de ia ion be ween assigned and
con ac ed hou s.
In ege P og amming (IP) has been one o he mos used echniques in he
li e a u e o model he s a scheduling p oblem. Mos o he IP o mula ions
a e based on he se co e ing model in oduced by Dan zig (1954). An
example is he ollowing model o a ou scheduling p oblem, p oposed by
Al a es (2004).
Minimize W=
J
X
j=1
xj
subjec o:
J
X
j=1
aijxj≥ i,i= 1,2, ..., I
xj≥0 and in ege , j= 1,2, ..., J
In his o mula ion he objec i e is o minimize he numbe o employees
assigned o all J ou s. The planning ho izon is a week, while o iginally
in Dan zig’s model i was a day, ep esen ing he decision a iable xj he
numbe o employees assigned o weekly ou j. The coe icien s aij ake he
alue 1 i ime pe iod iis a wo k pe iod o ou j, o he wise equal 0. The
minimum equi ed labou demand is ep esen ed by iand Iis he numbe
o ime pe iods o be scheduled o e he week.
Conside ing, o example, an ope a ing day om 7 a.m. o 2 p.m. and ime
pe iods (i) o 30 minu es, we would ha e 98 ime pe iods (I) o be scheduled
o e he 7 days o he weekly planning ho izon. Figu es 2.7 and 2.8 illus a e
17
Chap e 2. S a scheduling p oblems
his p oblem wi h he co esponden s a needs ( i) o each planning ime
pe iod and he ma ix o coe icien s aij, o J= 1,...,4 ou s.
Figu e 2.7: Example o a weekly scheduling demand equi emen .
Figu e 2.8: Example o he weekly scheduling aij ma ix da a. aij ake he
alue 1 i ime pe iod iis a wo k pe iod o ou j, and 0 o he wise.
The model associa es o each ou (de ined by a shi and b eak pe iods
combina ion) an explici decision a iable xj. In p oblems wi h high shi
lexibili y, ha ing di e en shi s a , inish o b eak imes, di e en shi
leng hs, e c., his o mula ion associa es a sepa a e in ege a iable o each
a ia ion o each o hese ea u es and he e o e, he numbe o a iables
can inc ease in such a way i is e y di icul o e en impossible o ge an
op imal solu ion. To o e come his d awback some au ho s ha e wo ked
on he p oblem o mula ion in o de o educe he model size using, o
example, implici modeling. This echnique associa es each decision a iable
o a shi - ype o a ou - ype. A shi ype can be a possible combina ion o
shi s a ing ime, shi leng h and b eak window (in e al o ime in which
a b eak can s a ), o example. Addi ional cons ain s a e in oduced in
o de o ensu e he co ec placemen o b eaks. A ou - ype can ha e ixed
s a ing- imes o e e y day o he ou o a iable s a ing- imes. In his las
si ua ion, a s a - ime band can be de ined, which is a ange in which shi
s a - imes can a y wi hin a single ou . When s a - ime bands con ain
shi s wi h he same co e age o pe iods hey a e named o e lapping s a -
18
2.2 Modeling he p oblem
ime bands. Implici modeling has p o en o be pa icula ly impo an
in hose s a scheduling p oblems ha deal wi h a iable shi s a ing-
imes and wi h b eaks placemen . Fo de ailed in o ma ion and p ac ical
applica ions o his echnique along he las decades we e e o Bech old
and Jacobs (1990), B usco and Johns (1996), Aykin (2000), Isken (2004),
Addou and Soumis (2007) and Rekik e al. (2010).
In o de o o e come he complexi y o sol ing la ge-size se co e ing p ob-
lems, some au ho s ha e explo ed ne wo k low o mula ions (Balak ishnan
and Wong (1990), C¸ezik e al. (2001), Moz and Pa o (2004)). In a ne wo k
low model, he sou ce node can co espond, o example, o he begin-
ning o he i s day and he sink node o he end o he las day o he
planning pe iod. Each node co esponds, hen, o he end o a day and o
he beginning o he ollowing day. Each wo k shi o es pe iod is ep-
esen ed, in he same example, by an a c. Each pa h om he sou ce o
he sink node ep esen s an al e na i e easible pa e n o wo k and es
pe iods, which sa is ies he sequence and maximum/minimum consecu i e
shi /days-o blocks cons ain s. This op ion allows o a simple isual ep-
esen a ion o e e y easible ou , which can be signi ican ly ad an ageous
in p oblems wi h many sequence cons ain s. The e a e o he al e na i e
ep esen a ions, hough, ha ha e been adop ed by di e en au ho s.
While co e age equi emen s a e ypically o mula ed as ha d cons ain s,
wo kload balance and sequence cons ain s a e o en ea ed as so con-
s ain s, i.e., cons ain s ha can be iola ed, hough a a de ined cos added
o he objec i e unc ion. Goal p og amming o mul i-objec i e echniques
a e used o inco po a e hese cons ain s in o he scheduling models. De ia-
ions om desi ed pa e ns o shi s, pa e ns o wo king and es days, a io
be ween numbe o nigh and day shi s o o he equi emen s a e penalized
in he objec i e unc ion, which seeks he minimiza ion o he sum o he
weigh ed de ia ions (see, o example, he wo k o Topaloglu and Ozka a-
19

Chap e 2. S a scheduling p oblems
han (2004), Azaiez (2005), Bu ke e al. (2010b) o Cas illo e al. (2009)).
Wi h hese o mula ions he use can analyze he impac o gi ing di e en
weigh s o each o he goals. This sensi i i y analysis can be e y help ul in
suppo ing he decision o choosing he mos con enien solu ion om a se
o easible solu ions.
Cˆo ´e e al. (2009) di ide ma hema ical p og amming o mula ions in o h ee
ca ego ies: compac assignmen , explici se co e ing and implici se co -
e ing o mula ions. The las wo ha e al eady been b ie ly p esen ed in his
sec ion. Compac assignmen o mula ions “use decision a iables o assign
ac i i ies o each employee a each pe iod” o ime. I is ou con ic ion
ha he models p oposed in his wo k can be classi ied as compac assign-
men o mula ions as will be explained in de ail in Chap e s 4 o 8. Ou
o mula ion uses bina y a iables o assign he wo king and es shi s o
each employee in each o he days o he planning pe iod. I canno be de-
ined as a common assignmen p oblem since, excep ion made o he glass
uni p oblem, he e is no a one o one assignmen ela ionship. Al hough
each employee can be assigned o only one shi , ei he a wo k o a es
shi , he same shi can be alloca ed o mo e han one employee. Demand
co e age, consecu i eness and sequence es ic ions a e add essed as ha d
cons ain s. Wo kload balance is also ackled by ha d cons ain s, imposing
a cyclic scheduling app oach o he model.
2.3 Re iewing ela ed wo ks in he li e a u e
2.3.1 Su eys and gene al wo ks
The de elopmen s on s a scheduling p oblems, hei applica ions, models
and solu ion me hods epo ed in he li e a u e, ha e been collec ed and
e iewed by se e al au ho s o e he las ou decades.
20
2.3 Re iewing ela ed wo ks in he li e a u e
E ns e al. (2004a) p esen one o he mos comp ehensi e su eys o he
s a scheduling p oblem. Mo e han 700 published pape s a e classi ied ac-
co ding o: he p oblem ype (o sub-p oblem) add essed, he solu ion ap-
p oach and he applica ion a ea. In o de o classi y he sub-p oblems, E ns
e al. p opose a amewo k based in se e al ca ego ies, which include, by o -
de o ep esen a i eness: c ew scheduling, ou scheduling, lexible demand,
wo k o ce planning, c ew os e ing, shi scheduling, cyclic os e ing, days-
o scheduling, shi demand, ask based demand, demand modeling, ask
assignmen , shi assignmen , among o he s. Some o hese sub-p oblems
ha e al eady been desc ibed in 2.1. Fo a de ailed desc ip ion o all he
ca ego ies see E ns e al. (2004b).
In a e y ecen wo k, Van den Be gh e al. (2012) e iew 291 a icles pub-
lished om 2004 onwa ds. Pape s a e ca ego ised acco ding o ou main
opics: 1) pe sonnel cha ac e is ics (con ac ype, skills, indi idual/ eam)
decision delinea ion and shi s de ini ion (o e lap, s a - ime, leng h); 2)
cons ain s (ha d/so , co e age, ime- ela ed, ai ness and balance), pe -
o mance measu es (di e en cos s) and lexibili y ( ela ed o cons ain s);
3) solu ion me hod and unce ain y inco po a ion (unce ain y o demand,
a i al and capaci y) and 4) applica ion a ea and applicabili y o esea ch.
A lis o he jou nals wi h mo e han 3 publica ions on pe sonnel scheduling
is also included. All manusc ip s a e lis ed and ca ego ised in 16 de ailed
ables, allowing o a s aigh o wa d usage o he in o ma ion. Some ele-
an indings abou he e iewed pape s can be highligh ed. The co e age
cons ain is a key cons ain , wi h almos 75% o he au ho s de ining i
as a ha d cons ain . When conside ed, he balance cons ain is modelled
as a so cons ain by almos all he esea che s. The consecu i eness and
sequence cons ain s a e ackled as so o ha d acco ding o he o igin o he
imposi ion, whe he i i is a legal se ing o a p e e ence scena io, o exam-
ple. In e ms o solu ion me hods, ma hema ical p og amming app oaches
21
Chap e 2. S a scheduling p oblems
and me aheu is ics lead he choices o he au ho s. In a inno a i e pe spec-
i e, his su ey wo k also add esses he in eg a ion o unce ain y in he
decision-making p ocess as well as he applicabili y o he s a scheduling
esea ch in he eal-wo ld se ing.
T anspo a ion sys ems, nu se scheduling and call-cen e s a e among he
mos explo ed applica ion a eas o he s a scheduling p oblem in he li -
e a u e. Wi hin he anspo a ion sec o , he ai line c ew scheduling and
he bus d i e scheduling appea as he mos s udied p oblems. Su eys
on he ai line c ew scheduling can be ound in A abey e e al. (1969), in
E schmaie and Ma haisel (1985) and mo e ecen ly in Gopalak ishnan and
Johnson (2005). Fo an o e iew o ad ances in he bus d i e scheduling
p oblem see W en and Rousseau (1995) and W en (1998). Re e ence e iew
s udies in nu se scheduling a e he wo ks o Wa ne (1976), Sil es o and
Sil es o (2001) and Bu ke e al. (2004). A u o ial and s a e-o - he a on
elephone call cen e s is p esen ed in Gans e al. (2003).
In a ou scheduling scope su ey, Al a es (2004) e iews o e 70 pape s pub-
lished be ween 1990 and 2001, compa ing ma hema ical models and classi y-
ing he s udies, acco ding o he solu ion me hods adop ed, in en ca ego ies:
manual solu ion, IP, implici modeling, decomposi ion, goal p og amming,
wo king se gene a ion, LP-based solu ion, cons uc ion/imp o emen , me a-
heu is ics and o he me hods (ne wo k- low models, expe sys ems, heu is-
ics, e c.). Du ing he pe iod conside ed in he su ey, me aheu is ics (mainly
simula ed annealing) we e he mos used echniques, ollowed by cons uc-
i e/imp o emen me hods, decomposi ion, manual solu ion and IP. How-
e e , when conside ing only he second hal o he su ey pe iod, he end
seems o be mo e a o able o he use o me aheu is ics, IP and manual
solu ions a he han o he o he me hods. In an e a o echnology ad-
ances, i is qui e su p isingly ha manual solu ions appea as one o he
mos popula me hods, bu he u h is ha s a scheduling is s ill done
22
2.3 Re iewing ela ed wo ks in he li e a u e
manually in some ac i i y sec o s, like hospi al wa ds, o example. Lapo e
(1999) sugges ed he manual design o cyclical schedules, a guing ha IP
o mula ions a e oo igid o be applicable o eal-wo ld p oblems.
In an ea lie wo k, Bake (1976) e iews ma hema ical p og amming o mu-
la ions o he shi and he days-o scheduling p oblems wi h cyclic demand
pa e ns. Bake highligh s he impo ance o demand modeling as a c ucial
s age wi hin he shi and he days-o p oblems. Al hough hey we e yp-
ically ea ed sepa a ely, Bake sugges s he de elopmen o an in eg a ed
model o bo h p oblems, since hey sha e a common con ex and a depen-
dency in e ms o s a equi emen s. In he same wo k, Bake discusses
he end o he esea che s o simpli y eal p oblems, ea ing demand in
a de e minis ic way, e en when he p oblem has p obabilis ic ea u es. Ap-
plica ion a eas o s a scheduling p oblems ackled in his su ey include
mainly se ice ac i i ies as baggage handle s, bus d i e s, elephone ope a-
o s o oll collec o s.
Conside ing he complexi y o he s a scheduling p oblem and i s a ian s,
i is easy o o esee he di icul y in inding a homogeneous p oblem clas-
si ica ion app oach among he se e al su eys published in he li e a u e.
E e y au ho p oposes i s own de ini ions scheme, which makes i ha de
o he compa ison o p oblems and he e alua ion o achie ed esul s. In
a ecen wo k, De Causmaecke and Vanden Be ghe (2011) o e come his
gap, p oposing a amewo k o he classi ica ion o s a scheduling p ob-
lems in se ices. I conside s h ee ca ego ies: pe sonnel en i onmen , which
includes di e en ypes o pe sonnel cons ain s and skills; wo k cha ac e -
is ics, which e e s o co e age cons ain s and shi ypes; and op imisa ion
objec i es. Such a classi ica ion sys em allows he benchma king o p ob-
lems, he e alua ion o he ins ances in e ms o ha dness and complexi y
and also he compa ison o solu ion app oaches.
23
Chap e 2. S a scheduling p oblems
o mos o he models. Making use o his wide p ac ical expe ience, Lapo e
(1999) a gues ha cyclical scheduling is mo e o “an a han a science”,
sugges ing ha in o de o ge wo kable solu ions, some o he p oblem’s
ules mus be iola ed.
Chan e al. (2001) p opose a cons ain p og amming app oach o sol e a
cyclic scheduling p oblem conside ing an annual planning ho izon. In ad-
di ion o common wo k ules and legal cons ain s, annual lea es a e also
included in his case. Wo k cycles a e no jus epea ed along he planning
ho izon, bu a he elaxed (ex ended o sho ened) o allow o days-o .
The cons ain s de eloped in his app oach we e embedded in a mo e com-
ple e so wa e applica ion ha has been success ully implemen ed in eal
wo k con ex , p oducing annual schedules o 150 employees. Ano he con-
s ain p og amming algo i hm is p oposed by Lapo e and Pesan (2004).
Beaumon (1997) uses a mul i-objec i e mixed in ege o mula ion o model
he days-o scheduling p oblem in a long- e m planning ho izon (47 and 48
weeks cycle). Cons ain s a e imposed on consecu i e wo king and o days
and on he weekly mean wo kload. The objec i e unc ion is a weigh ed
sum o h ee componen s: he p e e ence o employees o long wo k pe iods
and long b eaks, he balance o he wo kload among employees in a 30-
day pe iod and he managemen decision o ha ing a numbe o employees
on du y on each day o he week p opo ional o he demand on ha day.
The decision a iables de ined a e bina y a iables ha indica e whe he
a speci ic day is a wo kday o a day-o . This is a simple p oblem han
he ones conside ed in ou wo k, since he assignmen o shi s o wo king
days and o each employee is no conside ed. The model was sol ed wi h a
CPLEX sol e . Th ee schedules we e gene a ed o each cycle, conside ing
di e en goal weigh s, o be analyzed by he clien .
Al a es (1998) add esses he days-o scheduling p oblem wi h i e wo king
30

2.3 Re iewing ela ed wo ks in he li e a u e
days and wo days-o cycles. The p oblem is decomposed in wo s ages.
In a i s phase, an exp ession o calcula e he minimum wo k o ce size
is de e mined. In a la e phase, ha alue is included as a cons ain in
he linea p og amming model o he p oblem, which is a elaxa ion o he
IP model, ensu ing an op imal in ege solu ion. This app oach has he
ad an age o being applicable o p oblems wi h di e en days-o pa e n
cos s.
A decomposi ion wo-phase amewo k is also de eloped by Balak ishnan
and Wong (1990), who p opose a ne wo k low o mula ion o sol e a cyclic
scheduling p oblem wi h ixed shi s. The op imal solu ion is ound using a
sho es pa h based echnique. A no el app oach is p esen ed by Hao and Lai
(2004), who sol e a cyclic scheduling p oblem o ai po g ound s a wi h
a neu al ne wo k me hodology. Expe imen s e ealed encou aging esul s
when compa ed wi h he solu ions ob ained by simula ed annealing, abu
sea ch and gene ic algo i hms.
Heu is ics and me aheu is ics based me hods ha e also been used o sol e
he cyclic scheduling p oblem, as o example in he wo k o Mo a and Mus-
liu (2004) and Musliu (2006). Mo a and Musliu (2004) p opose a gene ic
algo i hm based me hodology while Musliu (2006) explo es he abu-sea ch
po en iali ies o de elop and compa e a se o heu is ic p ocedu es o au-
oma ically gene a e cyclic schedules. In he las men ioned wo k, Mus-
liu uses a benchma k da a se o compa e esul s, which is a ailable in
h p://www.dbai. uwien.ac.a /s a /musliu/benchma ks. These examples
a e used o analyze he pe o mance o ou o mula ion, as will be desc ibed
in de ail in Chap e 8.
31
Chap e 2. S a scheduling p oblems
2.4 Summa y
This chap e in oduced he s a scheduling p oblem: main concep s, ea-
u es and applica ions. The aim was no only o p o ide backg ound on he
opic, bu also o si ua e he p oblems add essed by his esea ch wo k. An
o e iew o modeling aspec s was p esen ed, wi h emphasis on IP echniques.
The ela ed li e a u e was e iewed, ocusing on hose wo ks ha sha ed
ea u es wi h he p oblems s udied in ou wo k. This analysis e ealed an
exis ing end o de elop IP models o speci ic applica ions and jus i ied he
oppo uni y o build a gene al model ha could be easily adap ed o sol e
di e en p oblems. This model should be lexible o accommoda e complex
bu ele an cons ain s, such as employee p e e ences and he equi y o he
s a schedules. The main challenge was o o mula e such a gene al model
using IP echniques and apply i o di e en eal-li e p oblems, sol ing hem
o op imali y.
32
Chap e 3
Hospi ali y managemen
This chap e is dedica ed o he desc ip ion o hospi ali y managemen as a
po en ial applica ion a ea o s a scheduling p oblems. The i s sec ion in-
oduces he concep o hospi ali y and gi es an o e iew on how hospi ali y
managemen is discussed in he esea ch li e a u e. A e e ence o he con-
ex ualiza ion o hospi ali y ac i i ies in he Po uguese se ing is included.
A e wa ds, some insigh s on he s a scheduling p oblem applied o hospi-
ali y managemen ope a ions a e p esen ed. Fi s ly, i s main ea u es a e
poin ed ou and an a emp o app oxima e i o applica ions in o he a eas
ha ha e been al eady ex ensi ely s udied in he li e a u e is made. This
exe cise is ollowed by a li e a u e e iew o he ela ed wo ks. To close he
chap e , a inal ou look on he esul s o he esea ch wo k desc ibed in his
chap e is gi en.
3.1 Hospi ali y managemen
Hospi ali y is no a ecen ac i i y. In he social sense o he concep i
da es om ancien imes, whe e many socie ies had adi ions o a ele s
p o ec ion and welcoming. King (1995) o e iews his o ical and sociological
oo s o hospi ali y and p oposes a model emphasizing he impo ance o
33
Chap e 3. Hospi ali y managemen
ela ionships be ween indi iduals (hos s, gues s/ cus ome s, employees) in
any hospi ali y con ex , whe he i akes place in a p i a e o in a comme cial
se ing.
Hospi ali y and hospi ali y managemen ha e been he scope o many e-
sea ch a icles, essen ially in he social sciences ield, whe e he discussion
has been ocused on de ining a common, gene ically accep ed, de ini ion
and on he de elopmen o a amewo k o be he basis o an independen
academic discipline.
Al hough s ill being o en me ged wi h ou ism and leisu e sec o ac i i-
ies, hospi ali y se ices a e a g owing ac i i y sec o in a socie y whe e
cus ome ’s sa is ac ion and well-being un he ma ke . They usually in-
clude ho els, es au an s and o he so o lodging, ood and d inks se ices
p o ide s. Due o he speci ica ions o he kind o se ice p o ided, hos-
pi ali y managemen has o deal wi h complex a iables and cons ain s.
An unp edic able cus ome demand, a mul iskilled wo k o ce, di e en s a
labou con ac s’ demands, employees sa is ac ion and cos s minimiza ion
a e jus some o he condi ioning issues ha an o ganiza ion has o deal
wi h in o de o achie e a lexible, p o i able and high quali y se ice p o i-
sion.
A su ey unde aken by Enz (2009), in coope a ion wi h he Cen e o
Hospi ali y Resea ch o Co nell Uni e si y, iden i ied human esou ces man-
agemen as he subjec o mos conce n o ho el manage s, abo e o he
aspec s such as economic o en i onmen al p oblems, and ega dless o he
geog aphical loca ion. The s udy was based on he s a emen o 243 expe-
ienced ho el execu i es om six coun ies. This highligh s he impo ance
and wo ldwide ele ance o human esou ce managemen o a hospi ali y o -
ganiza ion. S a scheduling a e ypical p oblems o sol e wi hin his a ea.
The e is howe e a big lack o published a icles ocusing on hese p oblems
34
3.1 Hospi ali y managemen
applied o he hospi ali y sec o , as ealized by E ns e al. (2004a), in op-
posi ion o o he applica ion a eas such as hospi als, anspo a ion o call
cen e s.
One o he easons o he lack o esea ch a icles ocusing on s a scheduling
p oblems in hospi ali y is pe haps he lack o a consensual and gene ically
accep ed de ini ion o he ac i i y i sel . E ymologically, he wo d hospi al-
i y, in La in hospi ali ies, has i s o igin in hospes o hospi is (geni i e), which
means o eigne o gues . Dic iona y de ini ions include “co dial and gene -
ous ecep ion o o disposi ion owa d gues s” (“hospi ali y”, The Ame ican
He i age Dic iona y o he English Language) and “kindness in welcoming
s ange s o gues s” (“hospi ali y”, Collins Essen ial English Dic iona y).
I is synonym o hospi ableness and widely used o de ine welcoming hos -
gues ela ionships, being hus adi ionally associa ed wi h cul u al and
social alues o each communi y.
In he indus ial con ex , he e m hospi ali y has been adop ed mainly in
he English-speaking coun ies o e e o he ac i i y o ho els, es au an s
and o he so o lodging, ood and d inks se ices’ p o ide s, whe he i
akes place in a public/ comme cial o in a p i a e/ social con ex . Lashley
(2008) a gues ha his amewo k can be unde s ood as an e o o “c ea e
a mo e a o able imp ession” o hese ac i i ies, p omo ing a u he hos-
pi able comme cial ac i i y and le ing he p o i p o ision mo i a ion e-
main in he backg ound. While B i ish esea che s ha e adi ionally based
he discussion on his de ini ion, Ame ican academics end o use a b oade
meaning o hospi ali y, associa ing hese ac i i ies wi h o he s unde he
ou ism ield, such as a el, leisu e o en e ainmen .
In a i s essay, hospi ali y managemen would hen be in ui i ely de ined as
he managemen o hose hospi ali y ac i i ies. In acco dance, B o he on
and Wood (2008) w i e ha hospi ali y managemen is a gene ically used ex-
35

Chap e 3. Hospi ali y managemen
p ession o easily eplace o he labels such as “ho el managemen ”, “ es au-
an managemen ” o “ca e ing managemen ”, bu consequen ly none o ew
e lec ion has been gi en o he genuine meaning o na u e o hospi ali y.
They s a e ha hospi ali y esea ch has been cha ac e ized h oughou he
yea s by an unsys ema ic and sca e ed analysis, ende ing a meaning ul
syn hesis e y ha d o achie e.
In he academic communi y, esea che s ha e been seeking ou he de el-
opmen o he specialis discipline o hospi ali y managemen ha would
embody a heo e ical amewo k and link i o he indus y sec o , bu he
lack o a consensual de ini ion o hospi ali y has e ec i ely been a ba ie
bo h o esea ch p og ess (Jones (1996), Taylo and Edga (1996)) and o
he c ea ion o a obus and ma u e b anch o knowledge. The discussion
has been d i en by some au ho s in o he ield o cul u al and social sciences
(B o he on (1999), Hemming on (2007), Jones (2004), Lashley (2008)), in-
co po a ing in he deba e he impo ance o s udying hospi ali y om a
wide pe spec i e a he han he comme cial one. The con ibu ion o
au ho s om di e en ields o esea ch and hei ision’s di e si y could
po en ially be a majo alue bu i could also be unde s ood as a e lex o a
agmen ed and uns uc u ed hospi ali y esea ch.
King (1995) in oduces a hospi ali y model based on he in e ac ion o so-
cial “ i uals” in he comme cial ope a ion, associa ed wi h he p ocess o he
gues a i al, welcoming and depa u e. The au ho de ines hospi ali y as
a hos -gues ela ionship be ween indi iduals, aking place in a comme cial
o p i a e se ing, whose success is assessed by he clea pe cep ion o he
gues needs and hei genuine sa is ac ion by he hos . This pe spec i e un-
de lies an uncondi ional mo al du y o hospi able beha io ha can, a he
edge, me ge he meanings o hospi ali y and hospi ableness, which B o he -
on (1999) con es s, a guing ha hospi ableness has a much b oade scope
han hospi ali y ac i i ies. In ac , hospi able conce ns a e a compe i i e
36
3.1 Hospi ali y managemen
ad an age in any ac i i y whe e he e is a “se ice” ela ionship wi h he
cus ome s, whe he i is om he hospi ali y sec o o no .
Belie ing ha hospi ali y is a ime e ol ing phenomenon, i.e, ha hospi al-
i y’ cha ac e is ics change o e ime, B o he on (2006) p esen s a concep-
ual model o hospi ali y comp ising ou dimensions: spa ial, beha io al,
empo al and physical. These dimensions help o analyze he ex en o
hospi ali y in e ms o place o occu ence, mo i a ional aspec s, ime and
ma e ial ea u es in ol ed. In his concep ual model, he na u e, incidence
and o ms o hospi ali y in a pa icula socie y in any gi en ime pe iod,
exp essed by domes ic o comme cial hospi ali y beha io , a e a unc ion o
he human and na u al esou ces a ailable, which in u n a e condi ioned
by he economic, socio-cul u al, poli ico-legal and echnological conjunc u e.
The au ho ied o ope a ionalize his model h ough case s udies (B o h-
e on and Wood (2008)) in wo ho els and la e in wo as ood es au an s,
whe e gues s/cus ome s whe e asked o pa icipa e h ough an in e iew,
associa ing wo ds ha bes i ed hei no ion o hospi ali y. Al hough his
exe cise did no p oduce s a is ically signi ican esul s in e ms o he in-
luence o social ac o s (like age, gende , occupancy, e c.), i did p o ide
inpu s o unde s anding gues s’ pe cep ion o he meaning o hospi ali y
ha s ill needs o be u he explo ed.
The comp ehensi e app oach o s udying he comme cial hospi ali y ac i i y
om a wide social sciences pe spec i e has indeed been qui e con o e sial,
as i u ned ou o happen a e he publica ion o he book “In sea ch o
hospi ali y: heo e ical pe spec i es and deba es” by Lashley and Mo ison
(2000). The e e ed wo k p esen s he na u e o hospi ali y om se e al
iews, om An h opology o Ma ke ing, and p oposes an in eg a ed “ h ee-
domains app oach”: he p i a e, he social and he comme cial domains.
The main idea o his concep ualiza ion is o conside and e alua e he
e ec o he social and cul u al dimensions o hospi ali y in he comme cial
37
Chap e 3. Hospi ali y managemen
o business ac i i y, despi e hei blu ed bounda ies. The book also de ends
he exis ence o hospi ali y managemen as an independen ac i i y, apa
om any o he managemen ac i i y.
Sla e y (2002) is one o he esea che s who is mos c i ical o his app oach,
a guing ha i o e es ima es he social side in ela ion o he economic one
and “excludes he hospi ali y indus y con ex ”. His classi ica ion model o
hospi ali y indus y is based on he place whe e ac i i ies e ec i ely ake
place: F ee-S anding Hospi ali y Business (ho els, es au an s, ba s), Hos-
pi ali y in Leisu e Venues (casinos, cinemas, heal h clubs), Hospi ali y in
T a el Venues (ai po s, bus s a ions, ains, e ies) and Subsidia y Hospi-
ali y (wo kplaces, heal h ca e, educa ion). He hus conside s ha con ining
hospi ali y o lodging, ood and d inks ac i i ies alls sho since hospi ali y
necessa ily unde akes he managemen o se e al o he so o associa ed
leisu e ac i i ies, in o de o espond o he inc easing complexi y o cus-
ome demand.
In his e iew, Jones (2004) iden i ies i e main hospi ali y schools o hough :
science model, managemen , s udies, ela ionship and sys ems, a es ing
ha he s a e o hospi ali y esea ch is no ye consolida ed and he e is
a lack o consensus conce ning i s de ini ion. E en hough his di e si y
o hough s pe sis s, he managemen pe spec i e was ecognized o be in a
dominan posi ion in ela ion o o he eme ging iews. Bu e en om a man-
agemen poin o iew he au ho inds h ee di e en app oaches, wi h hei
main di e gence in he ocus o he esea ch. While he adi ional poin
o iew conside s hospi ali y o be a sub-discipline inside he main man-
agemen disciplines, a di e en con ic ion uses hospi ali y as an applica ion
o he main discipline and a hi d pe spec i e assumes a “mul idisciplina y
app oach” s udying hospi ali y om se e al di e en main managemen sub-
jec s.
38
3.1 Hospi ali y managemen
In a ecen a icle, O enbache e al. (2009) analyze he pedagogical and e-
sea ch implica ions o de ining he hospi ali y discipline. Based on a se ices
ma ke ing pe spec i e, he au ho s de end a axonomical classi ica ion, con-
side ing hospi ali y as a ield suppo ed by he economic ou pu o a g oup o
six ela ed indus ies: lodging, ood se ices, leisu e, a el, a ac ions and
con en ions. Each o hese independen indus ies akes, in u n, “inpu
om hospi ali y ei he di ec ly o indi ec ly o i s su i al and success.”
The a icle sugges s he need o explo ing sepa a ely each one o hese ac-
i i ies, which a e o en igno ed in he li e a u e, ecognizing he di e si y
o hei cons i u i e ma ke segmen s.
In he Po uguese con ex a ansla ion o he concep s o hospi ali y o
hospi ali y managemen is s ill missing and consequen ly he e is no a con-
solida ed esea ch ac i i y ocused in his hema ic a ea, o a leas wi h
an acknowledged published wo k. A ew excep ions include o ins ance
he wo k on ho el managemen e iciency using Da a En elopmen Analy-
sis (Ba os and Masca enhas (2005), Ba os e al. (2008)). A hospi ali y
associa ion was c ea ed - Hospi ali y Managemen Ins i u e (HMI (2008)),
as a esul o he coope a ion be ween Tu ismo de Po ugal, ISCTE (In-
s i u o Supe io de Ciˆencias do T abalho e da Emp esa), Uni e sidade do
Alga e and ESHTE (Escola Supe io de Ho ela ia e Tu ismo do Es o il),
sponso ed by he Po uguese Go e nmen and he Na ional S a egic Coun-
cil o Educa ion and T aining in Tou ism, ha aims o p omo e ad anced
managemen aining and o suppo applied esea ch in ou ism.
Po uguese ho el and es au an indus ies ha e adi ionally been consid-
e ed as a pa o he ou ism sec o , o s a is ics, economic indica o s and
sec o ial s a egies, as well as se e al o he se ice p o ide s connec ed o
ou is ic se ices, such as a el agencies, ou is ic ope a o s o leisu e ac-
i i ies p omo o s. The e a e many di e en associa ions: Po uguese Ho-
39
Chap e 3. Hospi ali y managemen
o unde s and and sa is y hei needs. The s a mus be mo i a ed and
engaged. S a scheduling sys ems shall he e o e accoun o he wo k o ce
well- a e, conside ing employees’ p e e ences in e ms o wo k and es days,
weekends o and holidays, shi s assignmen , shi s change, shi s s a ing
and inishing imes lexibili y, compa ibili y o incompa ibili y wi h o he
s a elemen s, e c. Possible app oaches o he s a scheduling and os e ing
p oblem in hospi ali y managemen , o i s sub-p oblems, may be inspi ed
by he wo k ha has been comp ehensi ely done bo h in ou scheduling
and nu se os e ing. As exposed be o e in his chap e , nu se os e ing and
hospi ali y a e wo ac i i y a eas wi h many simila i ies conce ning os e ing
issues. Examples o he ew di e gences be ween hem include he seasonal-
i y, he weekly and daily cycles ope a ion inhe en o hospi ali y ac i i ies,
ha con as wi h he Win e /Summe seasonal wo kload dis ibu ion o
hospi als. Thompson (1999a) gi es a e y impo an con ibu ion o s a
scheduling and os e ing in hospi ali y managemen . I should ha e ig-
ge ed he in e es o esea che s in his a ea, namely in he de elopmen o
quan i a i e app oaches, bu he u h is ha i didn’ , acco ding o he
la es e iews on his subjec ha ha e been analyzed. This wo k aims o
be a ecall, as he e is s ill a lo o be done. Fu u e wo k may be based on
he adap a ion o ou scheduling, nu se os e ing o e en shi scheduling
models and solu ion me hods o hospi ali y ope a ions. Schedules should
be lexible enough o be easily adap able o ac ual wo kplace en i onmen s
changes and social aspec s should be conside ed.
46

Chap e 4
Gene al Model
This chap e p esen s he model de eloped o a gene al s a scheduling
p oblem. A se o ea u es, which a e ele an and common o many a ian s
o he p oblem a e conside ed. Those a e desc ibed in Sec ion 4.1. Nex ,
Sec ion 4.2 in oduces and explains he p oposed IP o mula ion. Finally,
in Sec ion 4.3 we highligh some special ea u es o he model ha , o he
bes o ou knowledge, ep esen a no el and alid con ibu ion o his ield
o esea ch.
4.1 P oblem desc ip ion
The gene al model was de eloped o he s a scheduling p oblem o an
o ganiza ion ha wo ks con inuously, 24 hou s a day. The day is di ided in
nS wo king shi s. The model conside s a se o nT eams o homogeneous
(single skilled and ull- ime) employees, ha mus be assigned o ei he a
wo k o a b eak shi , in each o he nD planning pe iod days. Daily shi
demand le els mus be sa is ied, meaning ha he model mus gua an ee
a equi ed numbe o eams wo king in each shi on each day. Wo k ules
include a minimum and a maximum numbe o consecu i e wo king days o
each eam, as well as a p ede ined sequence o wo king shi s o be espec ed.
47
Chap e 4. Gene al Model
Each shi change mus ha e a b eak o non-wo king day in be ween. The
objec i e is o minimize and o le el he numbe o days each eam wo ks
in each shi , in o de o balance he wo kload.
4.2 Ma hema ical model
The ollowing no a ion was de ined:
Indices
d∈ {1, . . . , nD}, day;
∈ {1, . . . , nT}, eam;
s∈ {1, . . . , nS}, wo king shi ;
s0∈ {1,...,2×nS}, ex ended shi .
Shi s s00 ∈ {nS + 1,...,2×nS}a e non-wo king shi s ha ca y he
in o ma ion on he las wo king shi o he eam;
n(s0) is he ex ended shi ha ollows he ex ended shi s0in a gi en se-
quence;
Fo example, conside ing 3 wo king shi s {1,2,3}and 3 non-wo king
shi s {4,5,6}a possible sequence could be 1-4-2-5-3-6-1-4-..., as de-
ined in Table 4.1.
s0123456
n(s0)456231
Table 4.1: Example o a possible sequence o shi s
48
4.2 Ma hema ical model
The indices and dshould ake alues in a ci cula lis . The lis o index d
should o ins ance be {1, . . . , nD −1, nD, 1, . . . , nD −1, nD, . . .}. Fo im-
plemen a ion pu poses index dshould be eplaced by [(d−1) mod (nD)]+1
and index should be eplaced by [( −1) mod (nT)] + 1.
Pa ame e s
nT numbe o eams;
nS numbe o shi s;
nD numbe o days in he planning pe iod;
demandsdaily demand o each wo king shi s;
maxD maximum numbe o consecu i e wo king days;
minD minimum numbe o consecu i e wo king days.
Decision a iables
x s0d=


1 i eam is assigned o shi s0on day d
0 o he wise
Decision a iables (auxilia y)
b dm =









1 i eam wo ks a leas minD consecu i e days,
s a ing on day d+m−1
0 o he wise
Objec i e unc ion
min max
s X
d
x sd (4.1)
49
Chap e 4. Gene al Model
Linea ized objec i e unc ion
min Z(4.2)
Cons ain s
∀ s X
d
x sd −Z≤0 (4.3)
∀ d X
s0
x s0d= 1 (4.4)
∀sd X
x sd ≥demands(4.5)
∀ d
maxD
X
q=0 X
s
x s(d+q)≤maxD (4.6)
∀ d
minD
X
m=1
b dm −X
s
x s(d+minD−1) ≥0 (4.7)
∀ d ∀minD
m=1 X
s
m+minD−1
X
q=m
x s(d+q−1) −minD ×b dm ≥0 (4.8)
∀ s0dx s0d−x s0(d+1) −x n(s0)(d+1) ≤0 (4.9)
∀ s0dm x s0d, b dm ∈ {0,1}(4.10)
The objec i e unc ion seeks he minimiza ion o he maximum numbe o
days ha a eam wo ks in each shi . I le els he wo king days o each
eam, leading o a solu ion in which each eam wo ks he same numbe o
days in each shi . The linea iza ion o (4.1) esul s in he linea objec i e
unc ion exp essed in (4.2), whe e Z ep esen s he maximum numbe o
days ha a eam wo ks in each shi , and also in Equa ions 4.3.
Equa ions (4.4) s a e ha each day e e y eam has exac ly one shi as-
signed, ei he a wo king shi o a b eak shi .
50
4.2 Ma hema ical model
Equa ions (4.5) a e co e age cons ain s, making su e ha each shi daily
equi emen s a e ul illed.
Equa ions (4.6) ensu e ha no eam wo ks mo e han maxD consecu i e
days. Fo each day da window o leng h maxD + 1 is opened and a leas
one o he co esponding x sd mus be 0, independen ly o he wo king shi
s.
Days!1!2!3!4!5!6!7!8!9!10!11!12!13!14!15!16!17!18!19!20!21!22!23!24!
25!
Team !M" M" M" B" A" A" A" B" N" N" N" B" B" M" M" B" B" A" A" B" B" N" N" B" B"
maxD+1!maxD+1!maxD+1!
Figu e 4.1: Illus a ion o Eqs. (4.6)
Equa ions (4.7) and (4.8) gua an ee ha each eam wo ks a leas minD
consecu i e wo king days. The second e m on he le -hand-side o Eq.
(4.7) sums up he wo king days x s(d+minD−1) wi hin a window o wid h
minD, s a ing a d. I all x s(d+minD−1) a e ze o no cons ain is imposed
o he a iables b dm. Howe e , i a leas one x s(d+minD−1) = 1 hen a
leas one o he a iables b dm mus be equal o 1. When he a iable b dm
equals ze o, he co esponding Eq. (4.8) is ul illed. Howe e i Eq. (4.7)
imposes ha a a iable b dm equals one, hen he i s e m on he le -hand-
side o Eq. (4.8) has o sum-up a leas minD, i.e. he eam has o wo k
a leas minD consecu i e days. The meaning o mis ha i a eam wo ks
one day wi hin a window o wid h minD, hen i has o wo k a leas minD
consecu i e days, s a ing a m= 1 o m= 2 o . . . o a m=minD. Figu e
4.2 illus a es his p ocess o shi M.
Equa ions (4.9) ensu e ha he equi ed shi sequence is ollowed. The
basic sequencing equi emen is de ined o e he wo king shi s ha ollow
he sequence: 1,2,3,1. . ., bu , as he e a e b eaks be ween he wo king
shi s, he b eaks mus ca y he memo y o he las wo king shi . This is
51

Chap e 4. Gene al Model
Days!
Team !M" M" M" M"
d!
m=1!m=2!m=minD!
minD!
minD!
minD!
b d1=1!
b d2=1!b dminD=1!
M"
Figu e 4.2: Illus a ion o Eqs. (4.7) and (4.8)
ob ained h ough he “ex ended shi ” s0. Fo ins ance, i a eam has an
ex ended shi s0= 4 assigned, i means ha he eam is ha ing a b eaking
shi a e a wo king shi 1. I he same shi is assigned on days dand d+1,
hen he co esponding Eq. (4.9) is sa is ied independen ly o he alue o
x n(s0)(d+1). Howe e i he shi ends, i.e., a di e en shi is assigned on
days dand d+ 1, hen he nex possible shi is imposed by he ec o o
indices n(s0) and he Eq. (4.9). Figu e 4.3 illus a es he applica ion o Eqs.
(4.9) o he sequence o shi s de ined in he example o Table 4.1.
Days!1!2!3!4!5!6!7!8!
Team !M" M" B" A" B" N" B" B"
Days!1!2!3!4!5!6!7!8!
Team !1" 1" 4" 2" 5" 3" 6" 6"
Figu e 4.3: Illus a ion o Eqs. (4.9)
52
4.3 Special ea u es
4.3 Special ea u es
Emphasis mus be gi en o he wide scope and lexibili y in oduced wi h
he o mula ion o he sequence shi es ic ion (Eqs. 4.9). Any desi ed
sequence pa e n o wo king shi s and days-o can be imposed h ough he
p ope de ini ion o he ec o o indices n(s0).
The limi s on he maximum and minimum numbe o consecu i e days o
each shi enable he dis inc ion be ween he leng h o he wo king and es
pe iods, bu also be ween he wo k shi s’ leng h i sel . Some ac i i ies ha e
wo k ules ha impose di e en maximum allowable numbe s o consecu-
i e wo king shi s, o ins ance nigh s day shi s. Bu hose pa ame e s,
oge he wi h he shi sequence cons ain s, also allow o con ol he pe iod-
ici y o days-o , as well as he leng h o he ou o sub-pe iod o sub-cycle
o he planning ho izon. I is possible o impose a schedule wi h sub-cycles
o equal leng h (i i is a di iso o he planning pe iod) o gi e he model
lexibili y o cons uc sub-cycles wi h di e en leng hs.
The lexible applica ion o hese ea u es is demons a ed in he case s udies
ha a e desc ibed in he nex chap e s.
53
Chap e 4. Gene al Model
54
Chap e 5
Applica ion o he gene al
model o a glass
p oduc ion uni
The gene al model p esen ed in Chap e 4 was i s adap ed o he eal-
li e p oblem o a glass indus y. This chap e desc ibes ha expe ience
and is o ganized as ollows. Sec ion 5.1 in oduces he acili y, he wo k
en i onmen and he ea u es o his pa icula p oblem. Then, in Sec ion 5.2
he adjus men s ha we e made o he gene al model a e desc ibed, ollowed
by he achie ed compu a ional esul s, which a e indica ed in Sec ion 5.3.
An illus a ion o he de eloped solu ions is shown in Sec ion 5.4. Sec ion 5.5
sums up he con en s o his chap e , emphasizing some impo an ou comes
o he wo k ha was ca ied ou .
5.1 P oblem desc ip ion
The acili y p oduces glass bo les using wo u naces, wi h ou lines each.
The wo k o ce was dis ibu ed in 4 eams bu he managemen wan ed o
es he scena io o ha ing a highe numbe o eams. They we e con inced
his change would inc ease he scheduling lexibili y and p o ide a mo e
55
Chap e 5. Applica ion o he gene al model o a glass
p oduc ion uni
pa o he cons ain s, as well as some quali y indica o s o he solu ion.
5.5 Conclusions
This chap e desc ibed he applica ion o he gene al IP model o he eal-li e
p oblem o a glass p oduc ion uni . The main adjus men was he in oduc-
ion o he o se cons ain s (Eqs. 5.2), which ensu e he wo kload balance
be ween he eams and allow o a educ ion in he o e all numbe o he
emaining cons ain s, imp o ing he model’s pe o mance. A new sequence
o shi s and days-o was imposed, by simply de ining a co esponding ec o
o indices n(s0). This demons a es he lexibili y o he app oach de eloped
o he sequence cons ain s. Expe imen s ocused on he e alua ion o di -
e en op imal solu ions achie ed o di e en planning pe iods and allowed
o he selec ion o hose ha be e sui ed he company’s goals, namely
in e ms o holiday dis ibu ion along he yea . An in eg a ed long- e m
scheduling solu ion was p oposed, h ough he eplica ion o wo di e en
planning pe iods, one o he win e mon hs and ano he o he summe
pe iod. Compu a ional imes e ealed he high e iciency o he model o
his pa icula applica ion, which was embedded in a mo e complex decision
suppo sys em o be used o he glass indus y managemen .
62

5.5 Conclusions
1/jan/10
2/jan/10
3/jan/10
4/jan/10
5/jan/10
6/jan/10
7/jan/10
8/jan/10
9/jan/10
10/jan/10
11/jan/10
12/jan/10
13/jan/10
14/jan/10
15/jan/10
16/jan/10
17/jan/10
18/jan/10
19/jan/10
20/jan/10
21/jan/10
22/jan/10
23/jan/10
24/jan/10
25/jan/10
26/jan/10
27/jan/10
28/jan/10
29/jan/10
30/jan/10
31/jan/10
1/ e /10
2/ e /10
3/ e /10
4/ e /10
5/ e /10
6/ e /10
7/ e /10
8/ e /10
9/ e /10
10/ e /10
11/ e /10
12/ e /10
13/ e /10
14/ e /10
15/ e /10
16/ e /10
17/ e /10
18/ e /10
19/ e /10
20/ e /10
21/ e /10
22/ e /10
23/ e /10
24/ e /10
25/ e /10
26/ e /10
27/ e /10
28/ e /10
1/ma /10
2/ma /10
3/ma /10
4/ma /10
5/ma /10
6/ma /10
7/ma /10
8/ma /10
9/ma /10
10/ma /10
11/ma /10
M N A
T1 !! ! """" !###!!!!! ! ! """ !####!!!! ! ! """" !###!!!!! ! ! """ !####!! ! 14 14 14
T2 ####!!!! ! ! """" !###!!!!! ! ! """!!!!####!!!! ! ! """" !###!!!!! ! ! """ !!!! 14 14 14
T3 """!!!!####!!!! ! ! """" !###!!!!! ! ! """ !!!!####!!!! ! ! """" !###!!!!! ! ! 14 14 14
T4 !!!!! ! ! """!!!!####!!!! ! ! """" !###!!!!! ! ! """ !!!!####!!!! ! ! """" !### 14 14 14
T5 !###!!!!! ! ! """!!!!####!!!! ! ! """" !###!!!!! ! ! """ !!!!####!!!! ! ! """" 14 14 14
12/ma /10
13/ma /10
14/ma /10
15/ma /10
16/ma /10
17/ma /10
18/ma /10
19/ma /10
20/ma /10
21/ma /10
22/ma /10
23/ma /10
24/ma /10
25/ma /10
26/ma /10
27/ma /10
28/ma /10
29/ma /10
30/ma /10
31/ma /10
1/ab /10
2/ab /10
3/ab /10
4/ab /10
5/ab /10
6/ab /10
7/ab /10
8/ab /10
9/ab /10
10/ab /10
11/ab /10
12/ab /10
13/ab /10
14/ab /10
15/ab /10
16/ab /10
17/ab /10
18/ab /10
19/ab /10
20/ab /10
21/ab /10
22/ab /10
23/ab /10
24/ab /10
25/ab /10
26/ab /10
27/ab /10
28/ab /10
29/ab /10
30/ab /10
1/mai/10
2/mai/10
3/mai/10
4/mai/10
5/mai/10
6/mai/10
7/mai/10
8/mai/10
9/mai/10
10/mai/10
11/mai/10
12/mai/10
13/mai/10
14/mai/10
15/mai/10
16/mai/10
17/mai/10
18/mai/10
19/mai/10
20/mai/10
T1 !! ! """" !###!!!!! ! ! """ !####!!!! ! ! """" !###!!!!! ! ! """ !####!! ! 14 14 14
T2 ####!!!! ! ! """" !###!!!!! ! ! """!!!!####!!!! ! ! """" !###!!!!! ! ! """ !!!! 14 14 14
T3 """!!!!####!!!! ! ! """" !###!!!!! ! ! """ !!!!####!!!! ! ! """" !###!!!!! ! ! 14 14 14
T4 !!!!! ! ! """!!!!####!!!! ! ! """" !###!!!!! ! ! """ !!!!####!!!! ! ! """" !### 14 14 14
T5 !###!!!!! ! ! """!!!!####!!!! ! ! """" !###!!!!! ! ! """ !!!!####!!!! ! ! """" 14 14 14
21/mai/10
22/mai/10
23/mai/10
24/mai/10
25/mai/10
26/mai/10
27/mai/10
28/mai/10
29/mai/10
30/mai/10
31/mai/10
1/jun/10
2/jun/10
3/jun/10
4/jun/10
5/jun/10
6/jun/10
7/jun/10
8/jun/10
9/jun/10
10/jun/10
11/jun/10
12/jun/10
13/jun/10
14/jun/10
15/jun/10
16/jun/10
17/jun/10
18/jun/10
19/jun/10
20/jun/10
21/jun/10
22/jun/10
23/jun/10
24/jun/10
25/jun/10
26/jun/10
27/jun/10
28/jun/10
29/jun/10
30/jun/10
1/jul/10
2/jul/10
3/jul/10
4/jul/10
5/jul/10
6/jul/10
7/jul/10
8/jul/10
9/jul/10
10/jul/10
11/jul/10
12/jul/10
13/jul/10
14/jul/10
15/jul/10
16/jul/10
17/jul/10
18/jul/10
19/jul/10
20/jul/10
21/jul/10
22/jul/10
23/jul/10
24/jul/10
25/jul/10
26/jul/10
27/jul/10
28/jul/10
29/jul/10
T1 !! ! """" !###!!!!! ! ! """ !####!! ! ! ! " " " " # # # # ! ! # # 11 11 13
T2 ####!!!! ! ! """" !###!!!!! ! ! """!!!! # # # # ! ! ! ! " " " " # # # # ! ! ! ! " " " " 15 15 15
T3 """!!!!####!!!! ! ! """" !###!!!!! ! ! " " " " # # # # ! ! ! ! " " " " # # # # ! ! ! ! " " " 15 18 15
T4 !!!!! ! ! """!!!!####!!!! ! ! """" !# # # # ! ! ! ! " " " " # # # # ! ! ! ! " " " " # # # # ! 16 15 16
T5 !###!!!!! ! ! """!!!!####!!!! ! ! " " " " ! ! " " " " # # # # ! ! ! ! 13 11 11
30/jul/10
31/jul/10
1/ago/10
2/ago/10
3/ago/10
4/ago/10
5/ago/10
6/ago/10
7/ago/10
8/ago/10
9/ago/10
10/ago/10
11/ago/10
12/ago/10
13/ago/10
14/ago/10
15/ago/10
16/ago/10
17/ago/10
18/ago/10
19/ago/10
20/ago/10
21/ago/10
22/ago/10
23/ago/10
24/ago/10
25/ago/10
26/ago/10
27/ago/10
28/ago/10
29/ago/10
30/ago/10
31/ago/10
1/se /10
2/se /10
3/se /10
4/se /10
5/se /10
6/se /10
7/se /10
8/se /10
9/se /10
10/se /10
11/se /10
12/se /10
13/se /10
14/se /10
15/se /10
16/se /10
17/se /10
18/se /10
19/se /10
20/se /10
21/se /10
22/se /10
23/se /10
24/se /10
25/se /10
26/se /10
27/se /10
28/se /10
29/se /10
30/se /10
1/ou /10
2/ou /10
3/ou /10
4/ou /10
5/ou /10
6/ou /10
7/ou /10
T1 # # ! ! ! ! " " " " # # # # ! ! ! ! " " " " # # # # ! ! ! ! " " " " !###!!!!! ! ! """ !####!! ! 18 15 17
T2 " " " " # # # # ! ! ! ! " " " " # # # # ! ! ! ! " " " " !###!!!!! ! ! """!!!! 12 15 11
T3 " # # # # ! ! ! ! # ! ! ! ! " " " " # # # # !!!! ! ! """" !###!!!!! ! ! 15 9 12
T4 ! ! ! " " " " # # # # ! ! ! ! " " " " # # # !!!!####!!!! ! ! """" !### 10 12 14
T5 " " " " # # # # ! ! ! ! " " " " # # # # ! ! ! ! " " " " # # # # ! ! ! ! ! ! """ !!!!####!!!! ! ! """" 15 19 16
8/ou /10
9/ou /10
10/ou /10
11/ou /10
12/ou /10
13/ou /10
14/ou /10
15/ou /10
16/ou /10
17/ou /10
18/ou /10
19/ou /10
20/ou /10
21/ou /10
22/ou /10
23/ou /10
24/ou /10
25/ou /10
26/ou /10
27/ou /10
28/ou /10
29/ou /10
30/ou /10
31/ou /10
1/no /10
2/no /10
3/no /10
4/no /10
5/no /10
6/no /10
7/no /10
8/no /10
9/no /10
10/no /10
11/no /10
12/no /10
13/no /10
14/no /10
15/no /10
16/no /10
17/no /10
18/no /10
19/no /10
20/no /10
21/no /10
22/no /10
23/no /10
24/no /10
25/no /10
26/no /10
27/no /10
28/no /10
29/no /10
30/no /10
1/dez/10
2/dez/10
3/dez/10
4/dez/10
5/dez/10
6/dez/10
7/dez/10
8/dez/10
9/dez/10
10/dez/10
11/dez/10
12/dez/10
13/dez/10
14/dez/10
15/dez/10
16/dez/10
T1 !! ! """" !###!!!!! ! ! """ !####!!!! ! ! """" !###!!!!! ! ! """ !####!! ! 14 14 14
T2 ####!!!! ! ! """" !###!!!!! ! ! """!!!!####!!!! ! ! """" !###!!!!! ! ! """ !!!! 14 14 14
T3 """!!!!####!!!! ! ! """" !###!!!!! ! ! """ !!!!####!!!! ! ! """" !###!!!!! ! ! 14 14 14
T4 !!!!! ! ! """!!!!####!!!! ! ! """" !###!!!!! ! ! """ !!!!####!!!! ! ! """" !### 14 14 14
T5 !###!!!!! ! ! """!!!!####!!!! ! ! """" !###!!!!! ! ! """ !!!!####!!!! ! ! """" 14 14 14
17/dez/10
18/dez/10
19/dez/10
20/dez/10
21/dez/10
22/dez/10
23/dez/10
24/dez/10
25/dez/10
26/dez/10
27/dez/10
28/dez/10
29/dez/10
30/dez/10
31/dez/10
1/jan/11
2/jan/11
3/jan/11
T1 !! ! """" !###!!!! 4 4 3
T2 ####!!!! ! ! """" !3 4 4
T3 """!!!!####!!!! ! ! "3 4 4
T4 !!!!! ! ! """!!!!#### 4 3 4
T5 !###!!!!! ! ! """!4 3 3
Figu e 5.4: Annual schedule o he glass p oduc ion uni
63
Chap e 5. Applica ion o he gene al model o a glass
p oduc ion uni
64
Chap e 6
Applica ion o he gene al
model o a con inuous ca e
uni
The gene al model desc ibed in Chap e 4 was in a second phase adap ed o
he eal-wo ld p oblem o a con inuous ca e uni . This chap e p esen s ha
wo k and is o ganized as ollows. Sec ion 6.1 in oduces he se ice ype,
he wo k en i onmen and he ea u es o his pa icula p oblem. Then, in
Sec ion 6.2 he adjus men s ha we e made o he gene al model a e ex-
plained, ollowed by he achie ed compu a ional esul s, which a e p esen ed
in Sec ion 6.3. A p oposed solu ion is shown in Sec ion 6.4. Sec ion 6.5 e-
sumes his chap e , highligh ing some impo an ou comes o he de eloped
esea ch wo k.
6.1 P oblem desc ip ion
The o ganiza ion p o ides p i a e lodging and nu sing home se ices, di-
ec ed mainly o he elde ly. This wo k add esses he scheduling o only
pa o he wo k o ce ha is composed by ca e ake s, which a e employees
wi h no speci ic quali ica ions ha a e esponsible o he daily basic needs
65
Chap e 6. Applica ion o he gene al model o a con inuous
ca e uni
o he gues s/pa ien s, such as pe sonal hygiene.
The uni wo ks con inuously, a ound he clock, 24h a day, in a mul i-shi
wo king scheme: M - mo ning ( om 8:00 a.m. o 2:00 p.m.), A - a e noon
( om 2:00 p.m. o 8:00 p.m.), N - nigh ( om 8:00 p.m. o 0:00 a.m.)
and D - a e -nigh ( om 0:00 a.m. o 8:00 a.m.). In opposi ion o he
p e ious case s udy, he demand is now di e en o each shi and he
maximum and minimum numbe o consecu i e wo king (o es ) days is
now indexed o each shi . Again, no daily meal b eaks a e conside ed, as
well as weekends-o es ic ions. Employees’ p e e ed sequence o shi s
and b eaks (B) mus be assu ed (M-A-N-D-B) and p e e ence is gi en o a
balanced schedule be ween employees. The wo k o ce is conside ed single
skilled bu is now he e ogeneous in e ms o con ac ypes. I combines a
ixed wo k o ce o 49 ull- ime, pe manen , employees wi h a a iable pool
o pa - ime wo ke s. The objec i e o he model is o minimize he pa -
ime equi emen s, assuming ha ull- ime con ac ed hou s mus be as ully
assigned as possible. Pa - ime wo ke s a e no subjec o any cons ain s.
6.2 Ma hema ical model
In o de o adap he gene al model o his new p oblem, he ollowing
adjus men s we e made.
Indices
n(s0) is he ex ended shi ha ollows he ex ended shi s0in a gi en se-
quence;
Conside ing 4 wo king shi s {1,2,3,4}and 1 non-wo king shi {5}
he new sequence M-A-N-D-B is now de ined as shown in Table 6.1.
66
6.2 Ma hema ical model
s012345
n(s0)23451
Table 6.1: Sequence o shi s o he con inuous ca e uni
maxDs0maximum numbe o consecu i e wo king (shi s 1 o 4) and es
(shi 5) days o each shi ;
minDs0minimum numbe o consecu i e wo king (shi s 1 o 4) and es
(shi 5) days o each shi ;
p Cos shou ly cos o a pa - ime employee wo king in shi s;
hsnumbe o wo king hou s o shi s.
Pa ame e s
δD o se be ween he wo king cycles o he eams (in numbe o days).
Objec i e unc ion Minimiza ion o he cos wi h pa - ime wo k.
min PdPsp Cos s×hs×(demands−P x sd) (6.1)
Cons ain s
∀sd X
x sd ≤demands(6.2)
Equa ions (6.2) s a e ha each day, he numbe o ull- ime employees as-
signed o e e y wo king shi is less han o equal o he demand. The
di e ence be ween he assigned and he demanded wo k will be assu ed by
pa - ime wo ke s.
The cyclic app oach in oduced in Chap e 5 was also adop ed in his o -
mula ion. The e o e, he model cons ain s include Eqs. (5.2), (5.3), (5.4),
67

Chap e 6. Applica ion o he gene al model o a con inuous
ca e uni
(5.5) and (5.6). See Sec ion 5.2 o a de ailed desc ip ion o each one o he
equa ions.
Equa ions (5.3), (5.4), (5.5) we e adjus ed o conside ex ended shi s, which
implied he eplacemen o he pa ame e s maxD and minD by he indexed
pa ame e s maxDs0and minDs0. These ep esen mino adjus men s, bu
in o de o allow o an easie eading he new Eqs. (6.3), (6.4) and (6.5)
a e p esen ed nex .
∀s0dPmaxDs0
q=0 x1s0(d+q)≤maxDs0(6.3)
∀s0dPminDs0
m=1 b1dm −x1s0(d+minDs0−1) ≥0 (6.4)
∀s0d∀minDs0
m=1 Pm+minDs0−1
q=mx1s0(d+q−1) −minDs0×b1dm ≥0 (6.5)
6.3 Compu a ional expe imen s
The model was coded in OPL S udio e sion 6.3 and sol ed using he CPLEX
12.1.0 sol e on a se e machine powe ed by 2 In el R
Xeon R
p ocesso s
o 2,4 GHz and 1,39 GHz, and wi h 2 GB RAM. The numbe o employees
(nT) is 49 and he wo king shi s (nS) a e now 4. The daily shi demand
(demands) is 20 M, 17 A, 11 N and 11 D. Tes s we e conduc ed o planning
pe iods o 25, 28 and 30 days, conside ing di e en combina ions o he
pa ame e s minDs0,maxDs0and p Cos s. The choice o he alues o hese
pa ame e s ook in o accoun he desi ed leng h o he sub-pe iods, he
assu ance o he minimum o one day-o e e y 7 days, and also ha he
wo king hou s assigned o each employee should all below 160h in a 30-
day pe iod in o de o espec labo con ac s. The easoning made in he
p e ious case s udy, conce ning he alue o he o se pa ame e , does no
make sense in his p oblem, since he planning pe iod is now sho e han
he numbe o employees. The e o e, he o se was se o 1, as i achie ed
sa is ac o y esul s.
68
6.3 Compu a ional expe imen s
In e ms o dimension, he numbe o decision a iables o his p oblem
a ies be ween 6125 o nD=25 and 7350 o nD=30 and he numbe o
cons ain s eaches he maximum o 8250 o nD=30 and maxD1=maxD2
= 3, maxD3=maxD4=maxD5= 1.
Table 6.2 epo s he compu a ional esul s o a se o di e en alues o
inpu pa ame e s. The column ”solu ion pa e n” con ains he schedule o
one employee o he whole planning pe iod conside ed, as illus a ed in he
nex examples. Figu es 6.1 and 6.2 show he schedule o E1 in a nD = 25
days scena io.
!" # $ % & ' ( ) * + #, ## #$ #% #& #' #( #) #* #+ $, $# $$ $% $& $'
-# . . / / 0 " 1. . / / 0 " 1. . / 0 " 1. / 0 " 1
Figu e 6.1: Schedule o E1 o nD=25 days; maxD1=maxD2= 2 and
maxD3=maxD4=maxD5= 1; minD1=minD2=minD3=minD4=
minD5= 1; p Cos 1=p Cos 2=p Cos 3=p Cos 4= 1.
nD 12345678910 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
E1 M A N D FM A N D FM A N D FM A N D FM A N D F
Figu e 6.2: Schedule o E1 o nD=25 days; maxD1=maxD2=maxD3
=maxD4=maxD5= 1; minD1=minD2=minD3=minD4=minD5
= 1; p Cos 1=p Cos 2=p Cos 3=p Cos 4= 1.
The abili y o con ol he solu ion pa e n wi h he a ia ion o inpu pa-
ame e s is no iceable. Fo his scena io, o example, i is possible o ge
a balanced solu ion, wi h sub-pe iods o equal leng h, wi h a educ ion o
maxDs0, o cing he model o assign exac ly 1 day o each shi . In his
solu ion he numbe o sub-pe iods inc eases om 4 in Fig. 6.1 o 5 in
Fig. 6.2, meaning ha he numbe o b eaks o days-o o ull- ime em-
ployees will also inc ease, as well as he equi emen s o pa - ime se ice
(highe /poo e solu ion alue).
The esul s o he uning o maxDs0and minDs0can also be checked o
a 30 days planning ho izon. In his case, ixing o 2 he minimum numbe
69
Chap e 6. Applica ion o he gene al model o a con inuous
ca e uni
nD maxDsminDsp Cos sSolu ion Pa e n PT Req.
s = M A N D B s = M A N D B s = M A N D (sub-pe iods) (hou s)
25 2 2 1 1 1 1 1 1 1 1 1 1 1 1 MMAANDB-MMAANDB-MMANDB-MANDB 2676
25 1 1 1 1 1 1 1 1 1 1 1 1 1 1 MANDB-MANDB-MANDB-MANDB-MANDB 2970
28 3 3 1 1 1 1 1 1 1 1 1 1 1 1 MMMAANDB-MMAANDB-MMAAANDB-MANDB 2856
28 2 2 1 1 1 1 1 1 1 1 1 1 1 1 MMAANDB-MMAANDB-MMAANDB-MMAANDB 2856
28 2 2 1 1 1 1 1 1 1 1 1 1 3 3 MAANDB-MANDB-MAANDB-MANDB-MAANDB 3150
28 2 2 1 1 1 1 1 1 1 1 1 5 1000 1000 MAANDB-MANDB-MAANDB-MAANDB-MANDB 3150
30 3 3 1 1 1 1 1 1 1 1 1 1 1 1 MMMANDB-MMMAANDB-MMMANDB-MMAAANDB 2976
30 2 2 1 1 1 1 1 1 1 1 1 1 1 1 MANDB-MANDB-MAANDB-MMAANDB-MMAANDB 3270
30 2 1 1 1 1 2 1 1 1 1 1 1 1 1 MMANDB-MMANDB-MMANDB-MMANDB-MMANDB 3270
30 1 1 1 1 1 1 1 1 1 1 1 1 1 1 MANDB-MANDB-MANDB-MANDB-MANDB-MANDB 3564
30 3 3 1 1 1 1 1 1 1 1 1 1 1000 1000 MANDB-MANDB-MANDB-MANDB-MANDB-MANDB 3564
Table 6.2: Model compu a ional pa ame e s and esul s o he con inuous ca e uni
70
6.3 Compu a ional expe imen s
o consecu i e days o shi M, esul s in a balanced solu ion bu wi h he
same numbe o sub-pe iods and, he e o e, wi h he same solu ion alue.
Figu es 6.3 and 6.4 illus a e his example.
nD 12345678910 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
E1 M A N D FM A N D FM A A N D FM M A A N D FM M A A N D F
Figu e 6.3: Schedule o E1 o nD=30 days; maxD2=maxD2= 2 and
maxD3=maxD4=maxD5= 1; minD1=minD2=minD3=minD4=
minD5= 1; p Cos 1=p Cos 2=p Cos 3=p Cos 4= 1.
nD 12345678910 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
E1 M M A N D FM M A N D FM M A N D FM M A N D FM M A N D F
Figu e 6.4: Schedule o E1 o nD=30 days; maxD1= 2 and maxD2=
maxD3=maxD4=maxD5= 1; minD1= 2 and minD2=minD3=
minD4=minD5= 1; p Cos 1=p Cos 2=p Cos 3=p Cos 4= 1.
The in luence o he p Cos spa ame e can be e i ied in he 28 days plan-
ning ho izon case. The inc ease om 1 (Fig. 6.5) o 3 (Fig. 6.6) uni s,
esul s in a highe numbe o sub-pe iods and he e o e, in a highe numbe
o days-o o ull ime employees and highe pa - ime needs, leading o a
wo se solu ion.
!" # $ % & ' ( ) * + #, ## #$ #% #& #' #( #) #* #+ $, $# $$ $% $& $' $( $) $*
-# . . / / 0 " 1. . / / 0 " 1. . / / 0 " 1. . / / 0 " 1
Figu e 6.5: Schedule o E1 o nD=28 days; maxD1=maxD2= 2 and
maxD3=maxD4=maxD5= 1; minD1=minD2=minD3=minD4=
minD5= 1; p Cos 1=p Cos 2=p Cos 3=p Cos 4= 1.
The same happens in he nD=30 case, whe e an inc ease om 1 (Fig. 6.7)
o 1000 (Fig. 6.8), in he hou ly cos o he pa - ime nigh and a e -nigh
shi s, achie es a solu ion wi h 2 addi ional sub-pe iods, which means mo e
pa - ime equi emen s and consequen ly a wo se solu ion alue. In e ms
o execu ion imes, each un ook less han 4 seconds.
71
Chap e 7. Applica ion o he gene al model o a hospi al
min P |[(h −a )−PsPd(ps×x sd)]|(7.1)
Cons ain s
∀sd P x sd ≥dMinsd (7.2)
∀sd P x sd ≤dMaxsd (7.3)
Equa ions (7.2) and (7.3) s a e ha each day, he equi ed numbe o wo k-
ing nu ses o each shi is ensu ed.
∀ d Pw−1
i=0 P5
s0=4 x s0(d+i)≥2 (7.4)
Equa ion (7.4) imposes a minimum o wo non-wo king days (D o B) in
each window w.
The cyclic app oach in oduced in Chap e 5 was once mo e adop ed. The
model cons ain s include Eqs. (5.2), (5.3), (5.4), (5.5) and (5.6). See Sec-
ion 5.2 o a de ailed desc ip ion.
Equa ions (5.3), (5.4), (5.5) we e adjus ed o conside he indexed pa ame-
e s maxDks0and minDks0. These pa ame e s can be se o di e en alues
in o de o e alua e di e en pa e ns o he sequence o shi s o he di e -
en ypes o con ac s. These ep esen mino adjus men s, bu in o de o
allow o an easie eading he new Eqs. (7.5), (7.6) and (7.7) a e p esen ed
nex .
∀ks0dPmaxDks0
q=0 x1s0(d+q)≤maxDks0(7.5)
∀ks0dPminDks0
m=1 b1dm −x1s0(d+minDks0−1) ≥0 (7.6)
∀ks0d∀minDks0
m=1 Pm+minDks0−1
q=mx1s0(d+q−1) −minDks0×b1dm ≥0 (7.7)
78

7.3 Compu a ional expe imen s and solu ions
The scheduling cons ain s ha ensu e a maximum o 6 consecu i e wo k
days o each nu se a e imposed by he uning o he pa ame e s maxDks0
and minDks0.
7.3 Compu a ional expe imen s and solu ions
The model was coded in OPL S udio e sion 6.3 and sol ed using he CPLEX
12.1.0 sol e on a se e machine powe ed by 2 In el R
Xeon R
p ocesso s o
2,4 GHz and 1,39 GHz, and wi h 2 GB RAM. In his p oblem he wo k o ce
is composed by 42 nu ses wi h di e en con ac ypes. Fo implemen a ion
pu poses, he 42 nu ses we e di ided in 5 g oups, as shown in Fig. 7.4.
Type o con ac
1. . . 5 1
6. . . 36 2
37. . . 38 3
39. . . 40 4
41. . . 42 5
Table 7.4: Associa ion o index o he ype o con ac
Since each ype o con ac is linked o a numbe o con ac ed hou s, each
nu se is hus ini ially connec ed o a numbe o con ac ed hou s pe plan-
ning pe iod. This app oach led o a lowe numbe o decision a iables han
he al e na i e o indexing each decision a iable o a nu se. In opposi ion o
he p e ious case s udies, as he e a e nu ses wi h di e en con ac ed hou s,
i was no easonable o impose he same o se o all he schedules. The e-
o e, each g oup o nu ses o he same ype had i s own o se . In e ms o
size, his model deal wi h 5880 decision a iables and 952 cons ain s. Jus
o gi e an idea o he in luence o he o se cons ain s in he simpli ica ion
o he model, i hese cons ain s we e no conside ed he o e all numbe o
79
Chap e 7. Applica ion o he gene al model o a hospi al
cons ain s would be 37 imes highe , inc easing om 952 o 35392. Fig-
u e 7.1 shows a solu ion ob ained o his case s udy in 1170.9 seconds (20
minu es). In his case, maxDks0= 5 o k=1,. . . ,5 and s0=1,. . . ,4; maxD15
=maxD25 = 5 and maxD35 =maxD45 =maxD55 = 7; minDks0= 1, o
k=1,. . . ,5 and s0=1,. . . ,5.
The o mula ion o he pa ame e s maxDks0and minDks0allows us o con-
ol he ela ion be ween he numbe o wo k and es days o each ype
o nu se. In his case, i makes sense o allow o mo e b eaks o hose
nu se ypes ha ha e less con ac ed wo k hou s (maxD35 =maxD45 =
maxD55 = 7).
This solu ion does no conside planned absences o holidays. Al hough
his cons ain has no been ea ed in he p e ious applica ions o he IP
model, we decided o in oduce i in he hospi al case s udy since i was
add essed in he solu ion p oposed in he o iginal wo k o An unes and Moz
(2011) and, he e o e, i makes he compa ison be ween app oaches easie
and mo e ealis ic. In o de o conside his scena io, he decision a iables
co esponding o each planned day-o we e ini ially se o 0 and he o se
cons ain s could no be applied o he eams ha had planned days-o .
Sequence and maximum/minimum consecu i e days cons ain s we e also
adjus ed indi idually o each o hose eams in o de o exclude he days-o .
Figu e 7.2 shows he solu ion ob ained when conside ing he planned days-
o o his pa icula mon h. As expec ed, he execu ion ime inc eased, as
he model ge s mo e cons ained, and i akes now 2256.3 seconds (abou
38 minu es) o ob ain his solu ion.
80
7.3 Compu a ional expe imen s and solu ions
!"#$%&'(
))
*)
+)
,)
-)
)*
**
+*
,*
-*
.*
/*
0*
1*
)2*
))*
)**
)+*
),*
)-*
).*
)/*
)0*
)1*
*2*
*)*
***
*+*
*,*
*-*
*.*
*/*
*0*
*1*
+2*
+)*
)+
*+
),
*,
)-
*-
3
4
!
) * + , - . / 0 1 )2 )) )* )+ ), )- ). )/ )0 )1 *2 *) ** *+ *, *- *. */ *0
! " #$$%! ! " #$%! ! " ##$$$ %! " #$$$%
%! " #$ $ %! ! " #$%! ! " ##$$$ %! " #$$$
$%! " #$ $ %! ! " #$%! ! " ##$$$ %! " #$ $
$ $ %! " #$ $ %! ! " #$%! ! " ##$$$ %! " #$
$$$%! " #$ $ %! ! " #$%! ! " ##$$$%! " #
! ! " #$%! ! " " #$%! ! " " #$% % ! ! ! " #$%
%! ! " #$%! ! " " #$%! ! " " #$% % ! ! ! " #$
$%! ! " #$%! ! " " #$%! ! " " #$% % ! ! ! " #
#$%! ! " #$%! ! " " #$%! ! " " #$% % ! ! ! "
"#$%! ! " #$%! ! " " #$%! ! " " #$% % !!!
! " #$%! ! " #$%! ! " " #$%! ! " " #$% % ! !
! ! " #$%! ! " #$%! ! " " #$%! ! " " #$% % !
! ! ! " #$%! ! " #$%! ! " " #$%! ! " " #$% %
%! ! ! " #$%! ! " #$%! ! " " #$%! ! " " #$%
% % ! ! ! " #$%! ! " #$%! ! " " #$%! ! " " #$
$% % ! ! ! " #$%! ! " #$%! ! " " #$%! ! " " #
#$% % ! ! ! " #$%! ! " #$%! ! " " #$%! ! " "
"#$% % ! ! ! " #$%! ! " #$%! ! " " #$%! ! "
" " #$% % ! ! ! " #$%! ! " #$%! ! " " #$%! !
! " " #$% % ! ! ! " #$%! ! " #$%! ! " " #$%!
! ! " " #$% % ! ! ! " #$%! ! " #$%! ! " " #$%
%! ! " " #$% % ! ! ! " #$%! ! " #$%! ! " " #$
$%! ! " " #$% % ! ! ! " #$%! ! " #$%! ! " " #
#$%! ! " " #$% % ! ! ! " #$%! ! " #$%! ! " "
"#$%! ! " " #$% % ! ! ! " #$%! ! " #$%! ! "
" " #$%! ! " " #$% % ! ! ! " #$%! ! " #$%! !
! " " #$%! ! " " #$% % ! ! ! " #$%! ! " #$%!
! ! " " #$%! ! " " #$% % ! ! ! " #$%! ! " #$%
%! ! " " #$%! ! " " #$% % ! ! ! " #$%! ! " #$
$%! ! " " #$%! ! " " #$% % ! ! ! " #$%! ! " #
#$%! ! " " #$%! ! " " #$% % ! ! ! " #$%! ! "
"#$%! ! " " #$%! ! " " #$% % ! ! ! " #$%! !
! " #$%! ! " " #$%! ! " " #$% % ! ! ! " #$%!
! ! " #$%! ! " " #$%! ! " " #$% % ! ! ! " #$%
%! ! " #$%! ! " " #$%! ! " " #$% % ! ! ! " #$
$%! ! " #$%! ! " " #$%! ! " " #$% % ! ! ! " #
#$%! ! ! " ##$%! " ###$%! ! ! " #$%! " #
##$%! ! ! " ##$%! " ###$%! ! ! " #$%! "
$%! ! " ### $%! ! " #$ $ %! ! " ###$%! " #
#$%! ! " ###$%! ! " #$ $ %! ! " ###$%! "
"#$% % % % % % ! " " #$% % ! ! " #$%! " #$%!
! " #$% % % % % % ! " " #$% % ! ! " #$%! " #$%
&' &' &( &) &( && &' &( &( &( &( &( &' &' &( &( &( &( &( &' && &' &( &) &' &( && &*
+,,,-,++,-&*&*&*,+,---,++,,-,&*,
-,+.+++......++...+,-,.+++-,
4$$56'%7
89':#;<:%7
8"##%':
=9"#$ =9"#$ >;?;'<%
&., &., * /'0(
&., &., * /*01
&., &., * /*0'
&., &., * /(
&., &., * /&
&1+ &.* /( )0&
&1+ &.* /( &0&
&1+ &.* /( *0-
&1+ &.* /( /)0-
&1+ &.* /( /&&0&
&1+ &.* /( *0&
&1+ &.* /( /'0.
&1+ &.* /( *0(
&1+ &.* /( /'0,
&1+ &.* /( /)01
&1+ &.* /( /(0(
&1+ &.* /( /.0,
&1+ &.* /( '0'
&1+ &.* /( /.0&
&1+ &.* /( /1
&1+ &.* /( &0&
&1+ &.* /( /10.
&1+ &.* /( /.0&
&1+ &.* /( /*0+
&1+ &.* /( /10,
&1+ &.* /( /'0+
&1+ &.* /( /&
&1+ &.* /( '0+
&1+ &.* /( /&'0'
&1+ &.* /( /10+
&1+ &.* /( /.0'
&1+ &.* /( '0(
&1+ &.* /( /)01
&1+ &.* /( /*0'
&1+ &.* /( /.0.
&1+ &.* /( /(0)
&() &(' ' &0.
&() &(' ' &01
&(. &', , &(
&(. &', , )0'
&&+01 &') /.01 /10&
&&+01 &') /.01 /1
(%@5;:59'
Figu e 7.1: Schedule o he hospi al case s udy wi hou planned absences
81
Chap e 7. Applica ion o he gene al model o a hospi al
In bo h solu ions, he de ia ion be ween assigned and con ac ed hou s
ans e ed om he p e ious mon h was se om eal da a. Column “De ia-
ion” da a e e s only o he p esen mon h’s de ia ion and column “Cu en
balance” shows he ac ual de ia ion balance a e he p esen mon h’s as-
signmen . We conside his las column in o de o compa e ou IP solu ion
wi h he one achie ed by An unes and Moz (2011) and also wi h he eal
schedule ha was made by hand by he head nu se o he hospi al. We will
name hem IP, An unes and Real solu ions espec i ely. Table 7.5 shows
some s a is ical da a o he de ia ion balance in he h ee solu ions.
De ia ion balance Solu ions
(hou s) IP An unes Real
Maximum 13.8 8 19.4
Median 4.7 4.8 5.5
A e age 4.8 4.7 5.8
Table 7.5: S a is ic analysis o he solu ions
The ma hema ical model p oposed by An unes and Moz (2011) limi s he
maximum de ia ion balance o each nu se o 8 hou s. In he An unes solu-
ion, his alue is eached in he schedules o wo o he nu ses. In he Real
solu ion his 8 hou s- alue is exceeded in 12 si ua ions, which co esponds
o app oxima ely 29% o he wo k o ce, and he maximum de ia ion is 19.4
hou s. In ou IP solu ion, he e a e 8 nu ses (19%) wi h a de ia ion balance
abo e 8 hou s, bu he maximum alue is 13.8. Ne e heless, he IP solu ion
ob ains a de ia ion below 4 hou s o 45% o he nu ses, agains 31% o he
An unes solu ion and 43% o he Real solu ion. Al hough he a e age and
he median alues a e no e y dis an , he ac is ha high de ia ions a e
ha de o manage and should be a oided. In ou app oach, we had o make
a ade-o be ween he esolu ion ime and he minimiza ion o he sum o
82
7.3 Compu a ional expe imen s and solu ions
!"#$%&'(
))
*)
+)
,)
-)
)*
**
+*
,*
-*
.*
/*
0*
1*
)2*
))*
)**
)+*
),*
)-*
).*
)/*
)0*
)1*
*2*
*)*
***
*+*
*,*
*-*
*.*
*/*
*0*
*1*
+2*
+)*
)+
*+
),
*,
)-
*-
3
4
!
) * + , - . / 0 1 )2 )) )* )+ ), )- ). )/ )0 )1 *2 *) ** *+ *, *- *. */ *0
! ! " ##$%! ! " #$ $ %! " " #$ $ %! ! " #$ $ %
%! ! " # # $%! ! " #$ $ %! " " #$ $ %! ! " #$ $
$%! ! " ##$%! ! " #$ $ %! " " #$ $ %! ! " #$
! ! ! " " # # %%%%%%%! ! ! ! ! " " " " #$ $ % %
$$$% % % % ! ! ! ! ! " " " " " %%%%%%%%%%%
"#$%! ! " " #$%! ! ! " #$%! ! " " #$%!!!
! " #$%! ! " " #$%! ! ! " #$%! ! " " #$%! !
! ! " #$%! ! " " #$%! ! ! " #$%! ! " " #$%!
! ! ! " #$%! ! " " #$%! ! ! " #$%! ! " " #$%
%! ! ! " #$%! ! " " #$%! ! ! " #$%! ! " " #$
$%! ! ! " #$%! ! " " #$%! ! ! " #$%! ! " " #
#$%! ! ! " #$%! ! " " #$%! ! ! " #$%! ! " "
"#$%! ! ! " #$%! ! " " #$%! ! ! " #$%! ! "
" " #$%! ! ! " #$%! ! " " #$%! ! ! " #$%! !
! " " #$%! ! ! " #$%! ! " " #$%! ! ! " #$%!
! ! " " #$%! ! ! " #$%! ! " " #$%! ! ! " #$%
%! ! " " #$%! ! ! " #$%! ! " " #$%! ! ! " #$
$%! ! " " #$%! ! ! " #$%! ! " " #$%! ! ! " #
#$%! ! " " #$%! ! ! " #$%! ! " " #$%! ! ! "
"#$%! ! " " #$%! ! ! " #$%! ! " " #$%!!!
! " #$%! ! " " #$%! ! ! " #$%! ! " " #$%! !
! ! " #$%! ! " " #$%! ! ! " #$%! ! " " #$%!
! ! ! " #$%! ! " " #$%! ! ! " #$%! ! " " #$%
%! ! ! " #$%! ! " " #$%! ! ! " #$%! ! " " #$
$%! ! ! " #$%! ! " " #$%! ! ! " #$%! ! " " #
#$%! ! ! " #$%! ! " " #$%! ! ! " #$%! ! " "
"#$%! ! ! " #$%! ! " " #$%! ! ! " #$%! ! "
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%! " " ####$$$$%! "
" " #$$% % ! " #$$$ % % !!!! " #%%%%%%%
"""""##$$$$%%%%!!!! " ###$%! " #
!"""%%%%%%%%%%%%%%! " " #$%! ! " "
%! " #$ $ %! " " ###$$$%! " #$%! ! ! " #$
$%! ! " #$%! " #$ $ %%%%%%%%%%%%%%%
%%%%%%%%! ! " " ###$$$$$%%%! ! ! " #
% % ! ! ! " # # $$$$% % !""""##$%! ! ! " #
###$$$$% % ! ! ! " " ###$ $ % % !""""# #
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
! " #$%%%!""""###$ $ %%%%! " #$$$ %
#$% % ! " #$%! ! ! " #$%! " " ###$% % ! " #
#$%! ! " " #$%! ! " " ###$% % ! ! ! " ####
##$%! ! " " #$%! ! " " ###$% % ! ! ! " ###
&' &' &( &' &( &) * &' &' &( &' &( + * &' &' &( &' &( + + &' &' &( &' &( + *
,****,,,*+**++,*+***,,****&),
---------,-,,-----,---------
4$$56'%7
89':#;<:%7
=>;''%7? 8"##%':
@9"#$ @9"#$ ;A$%'<%$ A;>;'<%
&-(./ &-* 01./ ) 0-.*
&-(./ &-* 01./ ) 0/
&-(./ &-* 01./ ) 01.,
&'+ &-* 0(+ 1( &
&),./ &-* 0-)./ -, /./
&-/ &-) / ) &'.&
&-/ &-) / ) +.&
&-/ &-) / ) *.+
&-/ &-) / ) (.&
&-/ &-) / ) 0(.&
&-/ &-) / ) *.&
&-/ &-) / ) /.1
&-/ &-) / ) *.(
&-/ &-) / ) /.'
&-/ &-) / ) (./
&-/ &-) / ) 1.,
&-/ &-) / ) &.'
&-/ &-) / ) &).'
&-/ &-) / ) &.+
&-/ &-) / ) (
&-/ &-) / ) +.&
&-/ &-) / ) '.1
&-/ &-) / ) &.+
&-/ &-) / ) ,.(
&-/ &-) / ) '.'
&-/ &-) / ) /.(
&-/ &-) / ) ,
) &-) 0&-) &-) /.,
,*./ &-) 0*&./ *, 0(.,
&') &-) 01) 1( ).(
&1'./ &-) 0&,./ '( '.(
+1./ &-) 0-/./ -- /.*
&//./ &-) 01./ ,./ &./
,+ &-) 0*& +' &(.*
&&'./ &-) 01,./ /& 0).&
&/& &-) 0+ &- -.-
&(, &(' / ) 1.-
) &(' 0&(' &(' 0)./
&'+ &'* & ) -
&'/./ &'* 0'./ ,./ &.'
&'(./ &'1 0)./ ) ).+
&'(./ &'1 0)./ ) &
(%B5;:59'
Figu e 7.2: Schedule o he hospi al case s udy conside ing planned absences
83

Chap e 7. Applica ion o he gene al model o a hospi al
hese de ia ions ( ansla ed by he objec i e unc ion). In o de o ge an
op imal solu ion in a easonable ime, a lowe bound o he objec i e unc-
ion was imposed. A e es ing se e al alues, he bes comp omise was
ound o he solu ion o Fig. 7.2, wi h an objec i e unc ion o 200.
The limi s on he daily shi equi emen s dMaxDsd and dMinDsd ha e
also a signi ican in luence on he model’s pe o mance. The close o eal
da a hese pa ame e s a e se , he igh e he model ge s and he longe
i akes o each a solu ion. In ou app oach, only he dMinDsd eal da a
was imposed. The limi s on dMaxDsd had o be elaxed in o de o ge a
solu ion in a easonable amoun o ime. Looking again in o he solu ion o
Fig. 7.2, he in o ma ion on he daily assigned hou s can be checked in he
ows below he schedule, o each one o he wo king shi s. A compa ison o
hese igu es wi h he ini ial demand equi emen s p o es ha he minimum
daily equi emen s a e sa is ied, whe eas he maximum limi s a e iola ed
in 6 di e en days: one ex a mo ning shi on day 6, one ex a a e noon
shi on days 10, 13, 14 and 17, and wo a e noon shi s in excess on day 27.
This d awback does no seem e y ep esen a i e when we look a he eal
solu ion, whe e he numbe o simila iola ions is much highe , eaching 23
si ua ions, mos ly a ec ing he a e noon and nigh shi s. Ne e heless, we
do no ha e enough in o ma ion o e alua e he impac o hese iola ions
in he eal se ing.
7.4 Conclusions
This chap e desc ibed he applica ion o he gene al IP model o he p ob-
lem o nu se scheduling in a Po uguese hospi al (An unes and Moz (2011)).
This p oblem di e s om he o he s al eady desc ibed in he p e ious wo
chap e s (Chap e s 5 and 6) in wo main ea u es: he wo k o ce compo-
si ion and he objec i e. The wo k o ce is now composed o 5 g oups o
84
7.4 Conclusions
nu ses, which a e g ouped acco ding o hei con ac ypes. The objec-
i e is o minimize he gap be ween assigned and con ac ed hou s. The
cyclic app oach in oduced in Chap e 5 was adop ed in o de o ensu e a
balanced solu ion wi hin each g oup o nu ses. Demand cons ain s (Eqs.
4.5, 7.2 and 7.3) we e adap ed in o de o conside minimum and maximum
daily equi emen s o each shi . Equa ions (5.3), (5.4) and (5.5) o each
con ac ype (index k) made i possible o impose di e en limi s on he
numbe o consecu i e wo king/ es days o each g oup o nu ses. In his
p oblem, i was mo e easonable o allow he g oups wi h less con ac ed
hou s o ha e mo e days-o assignmen s han he o he s. A new sequence
o shi s and days-o ha me he p e e ences o he nu ses was imposed, by
simply de ining a new ec o o indices n(s0). Al hough i was no conside ed
in his p oblem, we could de ine di e en sequence pa e ns o each g oup
o nu ses by simply indexing he sequence cons ain s (Eqs. 5.6) o each
ype o con ac . This example illus a es he lexibili y and po en ial o he
p oposed o mula ion. Expe imen s ocused on inding a ade-o be ween
he alue o he op imal solu ion and he compu a ional ime. In o de o
compa e ou solu ion wi h he one p oposed by An unes and Moz (2011)
and he eal solu ion manually de eloped by he head nu se o he hospi-
al, we adjus ed he model o conside he absences planned o he p esen
mon h. An op imal solu ion was buil in 38 minu es, conside ably mo e
han he 0.38 seconds aken by he op imal solu ion p oposed by An unes
and Moz (2011), which was speci ically ailo ed o his p oblem, bu much
less han he 8 hou s he head nu se needed o de elop i by hand. Resul s
a e encou aging, demons a ing ha ou o mula ion can also accommoda e
es ic ions on planned absences, such as holiday o aining.
85
Chap e 7. Applica ion o he gene al model o a hospi al
86
Chap e 8
Benchma k ins ances
In o de o e alua e he lexibili y and wide scope o he de eloped o mula-
ion and o compa e esul s wi h o he app oaches, expe imen s we e ca ied
ou on a collec ion o 20 o a ing wo k o ce scheduling p oblems a ailable
in h p://www.dbai. uwien.ac.a /s a /musliu/benchma ks and p esen ed in
Musliu (2006). This chap e desc ibes he applica ion o he gene al model
in oduced in Chap e 4 o hose benchma k p oblems. Sec ion 8.1 p esen s
he ea u es o he p oblems. Nex , he adjus men s ha we e made o he
gene al o mula ion a e explained in Sec ion 8.2, gi ing special a en ion o
he sequence cons ain s adap a ion. Sec ion 8.3 shows he compu a ional
esul s and a compa ison wi h o he me hods. Solu ions a e discussed in
Sec ion 8.4, ollowed by some concluding ema ks ha end he chap e .
8.1 P oblem desc ip ion
In hese ins ances, he numbe o employees a y om 7 o 163. The num-
be o s anda d shi s is ei he 2 (day and a e noon) o 3 (day, a e noon
and nigh ). The leng h o wo king and days-o blocks is now limi ed by a
minimum and a maximum numbe o consecu i e days, as well as he leng h
o each sequence o days assigned o he same shi . In he p e ious case
87
Chap e 8. Benchma k ins ances
Time(sec.)
Ex. nD nT nS IP MC-T FCS
1 63 9 3 7.94 0.07 0.90
2 63 9 3 2.90 0.07 0.40
3 119 17 3 907.40 0.42 1.90
4 91 13 3 1.59 0.11 1.70
5 77 11 3 2.47 0.43 3.50
6 49 7 3 1.23 0.08 2.00
7 203 29 3 - 52.79 16.10
8 112 16 3 7.60 0.74 124.00
9 329 47 3 - 15.96 -
10 189 27 3 - 0.60 9.50
11 210 30 3 - 13.15 367.00
12 140 20 2 310.00 1.17 -
13 49 7 3 255.95 0.87 -
14 91 13 3 73.14 0.76 0.54
15 448 64 3 - 159.04 -
16 203 29 3 1923.00 0.54 2.44
17 231 33 2 29.64 2.16 -
18 371 53 3 - 6.83 2.57
19 840 120 3 - 75.83 -
20 1141 163 3 - 71.38 -
Table 8.4: Compu a ional imes o he benchma king ins ances using he
IP model, MC-T and FCS
94

Chap e 9
Heu is ic app oach
An op imiza ion app oach is ypically limi ed in e ms o pe o mance o
eal-li e la ge dimension p oblems. The challenge o de eloping a heu is-
ic p ocedu e na u ally a ose as a means o sys ema ically o e coming ha
handicap and o compa e esul s. In his chap e we p opose a cons uc-
i e heu is ic o sol e he p oblem o he glass uni add essed in Chap e 5.
Sec ion 9.1 desc ibes he heu is ic p ocedu e, explaining he ini ial assump-
ions and he de eloped algo i hms. Compu a ional esul s o he glass uni
p oblem a e shown in Sec ion 9.2 and a compa ison o he pe o mance o
bo h app oaches, heu is ic and op imiza ion, is ca ied ou . In o de o an-
alyze he consis ency o he heu is ic, a se o compu e gene a ed ins ances
was also used, a ying in size wi h he numbe o eams and he numbe
o shi s. The solu ions gene a ed o he glass uni p oblem a e p esen ed
in Sec ion 9.2. Sec ion 9.3 d aws some conclusions and e lexions o u u e
ex ensions o his wo k.
95
Chap e 9. Heu is ic app oach
9.1 Heu is ic
9.1.1 Ini ial assump ions
F om ou p e ious expe ience wi h he op imiza ion model, desc ibed in
Chap e 5, we ealized ha a key issue ha gua an ees he exis ence o ea-
sible solu ions is he a ailabili y o a su icien numbe o b eaks, o allow
o an adequa e sequence o wo king days and days-o o each eam. This
b eak a ailabili y condi ion is on he basis o he p oposed heu is ic. When
he condi ion is alid, o a se o inpu pa ame e s, he heu is ic de ines
a easible schedule o he i s eam, which will be a e wa ds eplica ed
o he emaining eams, wi h a ime lag o o se days in be ween. In he
de elopmen o he i s eam’s schedule, wo king-day blocks a e assigned
ollowing he sequence o he shi s in which he eams mus wo k. The
leng h o he wo king blocks is limi ed by he minimum and maximum num-
be s o allowable consecu i e wo king days. I may occu , he e o e, ha all
wo king blocks ha e he same leng h, i.e. he same numbe o consecu i e
days, o ha blocks ha e di e en leng hs. Be ween each wo consecu i e
wo king blocks, i.e., be ween each change o wo king shi s, he e mus be
a leas one b eak day. The heu is ic assu es ha blocks o wo king days
plus b eaks ha e always he same leng h. The e o e, in he case o a sched-
ule wi h wo king-day blocks wi h di e en leng hs, mo e han one b eak is
assigned a e he wo king blocks wi h sho e leng hs, in o de o ha e a
block o wo king days plus b eaks wi h he same leng h as he block wi h he
maximum leng h plus one b eak. The heu is ic es s di e en combina ions
o wo king blocks un il a easible solu ion is eached. These p ocedu es a e
nex explained in de ail.
96
9.1 Heu is ic
9.1.2 Algo i hm 1 - checkA ailableB eaks
The i s s ep o he heu is ic is he e i ica ion o he a ailable b eaks con-
di ion, desc ibed in Algo i hm 1 - checkA ailableB eaks, whe e:
nD is he numbe o days in he planning pe iod;
nT is he numbe o eams;
nS is he numbe o wo king shi s;
minD is he minimum equi ed numbe o consecu i e wo king days;
maxD is he maximum allowed numbe o consecu i e wo king days;
wdis he numbe o wo king days o he planning pe iod o be assigned
o each eam, o each shi ;
nblocks is he numbe o blocks o wo king days, o each eam and o each
shi ;
maxBlock is he block o wo king days wi h he maximum leng h o be consid-
e ed;
F o is he o al numbe o a ailable b eaks in he planning pe iod, o each
eam;
Fmin is he minimum numbe o equi ed b eaks in he planning pe iod, o
each eam, conside ing he equi ed numbe o wo king-day blocks.
The algo i hm i s calcula es he alues o F o and wd. I , in each day,
he e a e 3 shi s o be assigned o exac ly 3 eams, he emaining 2 eams a e
necessa ily assigned o b eaks. So, 2 b eaks a e a ailable in each day. These
2 b eaks mul iplied by he numbe o days in he planning pe iod (nD) and
di ided by he numbe o eams (nT) esul in he o al numbe o a ailable
97
Chap e 9. Heu is ic app oach
Algo i hm 1 checkA ailableB eaks
F o ←nD ∗(nT −nS)/nT
wd←(nD −F o )/nS
o i= 0 →(minD +i)do
i wdis a mul iple o (minD +i) hen
nblocks ←wd/(minD +i)
Fmin ←nblocks ∗nS
i Fmin ≤F o hen
solu ionExis s
maxBlock ←(minD +i)
equalBlocks
Exi
end i
end i
end o
es BlocksCombina ion()
i solu ionExis s hen
Exi
else
noFeasibleSolu ionAssu ed
Exi
end i
b eaks pe eam, F o . This igu e ep esen s he maximum numbe o b eaks
he p ocedu e has a ailable o assign o each eam, and mus be enough o
ensu e he manda o y minimum numbe o b eaks o assign be ween shi
changes. Taking F o ou o nD and di iding i by he numbe o shi s (nS)
we ge he numbe o wo king days, in each shi , o assign o each eam,
wd. Figu es 9.1, 9.2 and 9.3 illus a e he easoning o hese calcula ions
o nD = 20 days, b eaks a e ep esen ed by he blank cells. Algo i hm 1
p oceeds by checking he possibili y o assigning only wo king blocks wi h
equal leng h: (minD +i). Looking in o he same example o nD = 20
days, wi h minD = 2 days and maxD = 4 days, he numbe o days in
each o he wo king blocks is achie ed o i= 0, hus wd/2 = 2. When
ha is no easible, he unc ion es BlocksCombina ion() is called and
98
9.1 Heu is ic
combina ions o wo king blocks wi h di e en leng hs a e e alua ed. This
is he case illus a ed in Fig. 9.4, o a planning pe iod o 25 days. In his
scena io, wd= 5 days, which is no di isible o any minD +i, o any i.
The e o e, a combina ion o blocks o minD and minD + 1 days, 2 days
and 3 days espec i ely, is used. I no combina ion o blocks sa is ies he
condi ion Fmin ≤F o , hen he p oblem may no ha e a easible solu ion.
Consequen ly, he ollowing s a emen can be made:
I he inpu pa ame e s selec ed e i y he condi ion: Fmin ≤
F o , hen i has a easible solu ion. O he wise, i may ha e o
no a easible solu ion.
This condi ion is hus su icien bu no necessa y.
Teams/Days 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
T1 !" !" !! #" #" !! $" $" !! !! !" !" !! #" #" !! $" $" !! !!
T2 !! !! !" !" !! #" #" !! $" $" !! !! !" !" !! #" #" !! $" $"
T3 $" $" !! !! !" !" !! #" #" !! $" $" !! !! !" !" !! #" #" !!
T4 #" !! $" $" !! !! !" !" !! #" #" !! $" $" !! !! !" !" !! #"
T5 !! #" #" !! $" $" !! !! !" !" !! #" #" !! $" $" !! !! !" !"
Figu e 9.1: Example: calcula ion o he numbe o a ailable b eaks/day.
Teams/Days 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
T1 !" !" !! #" #" !! $" $" !! !! !" !" !! #" #" !! $" $" !! !!
T2 !! !! !" !" !! #" #" !! $" $" !! !! !" !" !! #" #" !! $" $"
T3 $" $" !! !! !" !" !! #" #" !! $" $" !! !! !" !" !! #" #" !!
T4 #" !! $" $" !! !! !" !" !! #" #" !! $" $" !! !! !" !" !! #"
T5 !! #" #" !! $" $" !! !! !" !" !! #" #" !! $" $" !! !! !" !"
Figu e 9.2: Example: calcula ion o he numbe o a ailable b eaks/ eam.
99

Chap e 9. Heu is ic app oach
Teams/Days 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
T1 !" !" !! #" #" !! $" $" !! !! !" !" !! #" #" !! $" $" !! !!
T2 !! !! !" !" !! #" #" !! $" $" !! !! !" !" !! #" #" !! $" $"
T3 $" $" !! !! !" !" !! #" #" !! $" $" !! !! !" !" !! #" #" !!
T4 #" !! $" $" !! !! !" !" !! #" #" !! $" $" !! !! !" !" !! #"
T5 !! #" #" !! $" $" !! !! !" !" !! #" #" !! $" $" !! !! !" !"
Figu e 9.3: Example: calcula ion o he numbe o wo king days/shi / eam.
Teams/Days 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
T1 ! ! ! " " " # # # ! ! " " # #
T2 # # ! ! ! " " " # # # ! ! " "
T3 " " # # ! ! ! " " " # # # ! !
T4 # ! ! " " # # ! ! ! " " " # #
T5 " " # # # ! ! " " # # ! ! ! "
Figu e 9.4: Example: solu ion o nD=25 days.
9.1.3 Algo i hm 2 - gene a eSchedule
I he condi ion is me we p opose a cons uc i e heu is ic o build a ea-
sible solu ion, as desc ibed in Algo i hm 2 - gene a eSchedule. I s a s
by checking he ela ion be ween he inpu pa ame e s nD and nT. The
p ocedu e only p oceeds when nD is a mul iple o nT. Then he unc-
ion checkA ailableB eaks is called in o de o e i y i he e a e enough
a ailable b eaks o gua an ee he exis ence o a easible solu ion, as ex-
plained be o e. A e his condi ion is ull iled, he schedule is gene a ed,
ei he wi h only wo king blocks wi h he same leng h, h ough he unc ion
gene a eEqualBlocksSchedule o combining wo king blocks wi h di e en
leng h, calling he unc ion gene a eCombina ionBlocksSchedule.
9.1.4 Algo i hm 3 - gene a eEqualBlocksSchedule
The pseudo code o gene a eEqualBlocksSchedule is desc ibed in Algo-
i hm 3. The idea is o build a easible solu ion o he i s eam and hen
eplica e i o he emaining (nT −1) eams. In his scena io, all wo king
100
9.1 Heu is ic
Algo i hm 2 gene a eSchedule
i nD is no a mul iple o nT hen
Msg: ”Change inpu pa ame e s”
end i
checkA ailableB eaks
i solu ionExis s hen ini ializeSchedule
i equalBlocks hen
gene a eEqualBlocksSchedule
else
gene a eCombina ionBlocksSchedule
end i
else i noFeasibleSolu ionAssu ed hen
Msg: ”Fmin > F o , he p oblem may no ha e a easible solu ion!”
end i
blocks ha e he same leng h o maxBlock days and a e sepa a ed by one
b eak. The p ocedu e begins by assigning he i s block o he i s wo king
shi o all eams, wi h a ime lag, δD, equal o minD days be ween hem,
i maxBlock ≤minD o , o he wise, equal o nD/nT days. I p oceeds by
assigning he i s blocks o he emaining shi s o he i s eam, sepa a ed
by a b eak. In o de o sa is y he shi daily demand, which o ces each
wo king shi o be assigned o only one eam in each day o he planning
pe iod, he second sub-pe iod can only begin when he i s shi is a ailable
again, and o maxBlock consecu i e days. This means ha he second
wo king block o he i s shi can only be assigned o eam 1 in a slo wi h,
a leas , maxBlock consecu i e days whe e he e isn’ any eam assigned
o ha shi . The i s sub-pe iod is hen eplica ed o he i s eam un il
he whole planning pe iod is ul illed, esul ing in he schedule o he i s
eam. This schedule is eplica ed o all he emaining (nT −1) eams, wi h
a ime lag o δD days be ween hem.
101
Chap e 9. Heu is ic app oach
Algo i hm 3 gene a eEqualBlocksSchedule
Use wo king blocks o maxBlock days
Assign he i s wo king block o he i s shi o eam 1
Use a ime lag: δD =minD o nD/nT days o assign he i s block o
he i s shi o all emaining (nT −1) eams
Assign he i s blocks o he emaining wo king shi s o eam 1, sepa a -
ing each block wi h one b eak
Inse b eaks a he end o he las shi block o wai un il he i s shi
is a ailable again, in o de o close he i s sub-pe iod
Replica e he i s sub-pe iod o he i s eam as many imes as necessa y
o ul ill he planning pe iod
Replica e he schedule o he i s eam o he emaining (nT −1) eams,
wi h a ime lag o δD =nD/nT days
9.1.5 Algo i hm 4 - gene a eCombina ionBlocksSchedule
Algo i hm 4 p esen s he p ocedu e gene a eCombina ionBlocksSchedule.
The p ocess is simila o he one ollowed in he p e iously desc ibed unc-
ion gene a eEqualBlocksSchedule p ocedu e, bu in his case, he wo k-
ing blocks can ha e di e en leng hs: maxBlock (maxBlock −1) and/o
(maxBlock−2) days. The ime lag δD o be used be ween eams’ schedules
is nD/nT days. The p ocedu e i s assigns he wo king blocks o maxBlock
days, hen o (maxBlock−1) days and ends up wi h he assignmen o blocks
wi h (maxBlock −2) days, i applicable. An impo an aspec o ake in o
accoun is he numbe o b eaks o inse be ween wo king blocks, ha mus
be 1 be ween maxBlock blocks, 2 be ween (maxBlock −1) blocks and 3 be-
ween (maxBlock −2) blocks. This makes all blocks o (wo king days plus
b eaks) o ha e he same leng h, equal o (maxBlock + 1) days. Again,
we mus ensu e ha no wo king shi is assigned o mo e han one eam in
each day, as al eady s a ed in Algo i hm 3. This is achie ed by inse ing
102
9.2 Compu a ional expe imen s and solu ions
Algo i hm 4 gene a eCombina ionBlocksSchedule
Use a combina ion o wo king blocks o maxBlock, (maxBlock−1) and/o
(maxBlock −2) days, i applicable
o i= 0 →2do
Assign he i s (maxBlock−i) wo king block o he i s shi o eam
1
Use a ime lag: δD =nD/nT o assign he i s (maxBlock −i) block
o he i s shi o all emaining (nT −1) eams
Assign he i s (maxBlock −i) block o he emaining wo king shi s
o eam 1, sepa a ing each block wi h (i+ 1) b eaks
Inse b eaks a he end o he las shi block o wai un il he i s
shi is a ailable again, in o de o close he i s sub-pe iod
end o
Replica e he i s sub-pe iod o he i s eam as many imes as necessa y
o ul ill he planning pe iod
Replica e he schedule o he i s eam o he emaining (nT −1) eams,
wi h a ime lag o δD =nD/nT days
b eaks a he end o he las wo king block o he i s sub-pe iod un il he
i s shi is a ailable again o he second sub-pe iod assignmen . The i s
sub-pe iod is hen eplica ed o he i s eam as many imes as necessa y
in o de o comple e he whole planning pe iod, esul ing in he schedule
o he i s eam. This schedule is eplica ed o all he emaining (nT −1)
eams, wi h a ime lag o δD days be ween hem.
9.2 Compu a ional expe imen s and solu ions
The heu is ic was coded using VBA o Excel 2011 and an on a se e
machine powe ed by 2 In el R
Xeon R
p ocesso s o 2,4 GHz and 1,39 GHz,
103
Chap e 9. Heu is ic app oach
No. Planning No. Execu ion ime (sec.)
shi s pe iod (days) eams Heu is ic IP
21 70 35 3.30 7086.50
24 120 30 3.52 14164.00
24 96 32 2.48 –
24 102 34 3.27 –
24 80 40 3.13 –
27 108 36 3.91 –
27 136 34 3.53 –
27 114 38 3.38 –
27 90 45 4.94 –
30 152 38 4.23 –
30 120 40 4.09 –
30 129 43 3.98 –
30 100 50 4.69 –
Table 9.2: Compu a ional esul s o a se o combina ions o
he a io nS/nT.
9.3 Conclusions
In his chap e a new cons uc i e heu is ic was p oposed o sol ing he s a
scheduling p oblem o he glass manu ac u e uni in oduced in Chap e 5.
The de eloped p ocedu es we e desc ibed and a compa ison o he esul s
achie ed by bo h heu is ic and op imiza ion app oaches was p esen ed, high-
ligh ing a consis en ou pe o mance o he heu is ic o e he op imiza ion
app oach, wi h all esul s alling below 5 seconds.
An impo an and no el con ibu ion o his wo k is he app oach in oduced
wi h Algo i hm 1 - checkA ailableB eaks. Wi h some simple calcula ions
110

9.3 Conclusions
o e he p oblem’s inpu da a, i is possible o o esee he exis ence o a
easible solu ion. Al hough he p oposed heu is ic was de eloped o his
speci ic ins ance, i is lexible enough o accoun o a ia ions in some o
he p oblem’s pa ame e s and cons ain s. Tha is he case o he sequence
o wo king shi s, which can be any ha he use de ines, as well as he
minimum and maximum numbe o consecu i e wo king days. Wi h sligh
adjus men s, he numbe o b eaks o in e pose be ween wo king blocks
can also be ede ined. Ne e heless, he p oposed p ocedu e has limi a ions
when conside ing i s di ec applicabili y o o he ins ances. I imposes he
exis ence o a leas one b eak day be ween each change o wo king shi s, so
i does no allow o he possibili y o ha ing di e en shi s on consecu i e
days. The shi daily demand, o example, is a e y s ong cons ain o his
pa icula p oblem since i is on he basis o he calcula ion o he numbe
o a ailable b eaks, as i was p e iously explained, which is a condi ioning
ac o o he exis ence o a easible solu ion. In p oblems wi h mo e han
one eam wo king simul aneously on he same shi , o wi h di e en daily
equi emen s o each shi , his cons ain would ha e o be e o mula ed
and would imply deepe adjus men s in he p ocedu es p oposed, bu he
base easoning would be he same. As s a ed be o e, he “wo king-shi s
sequence” app oach is a s eng h o his wo k, o p oblems whe e a unique
p ede ined sequence mus be ollowed. Bu i can also be a limi a ion be-
cause, in p oblems whe e a se o sequences should be a oided, he heu is ic
may no espond acco dingly, unless a p e e ed sequence can be chosen.
As a conclusion, we belie e ha he achie ed esul s a e p omising and
encou aging o u he ex ensions o he heu is ic in o de o conside , o
example, di e en shi daily demands o o bidden sequences o shi s.
111
Chap e 9. Heu is ic app oach
112
Chap e 10
Conclusions
10.1 Con ibu ions o his wo k
In his hesis, we p oposed an op imiza ion me hod o simul aneously as-
signing wo k shi s and days-o o each employee. A gene al IP model was
de eloped and applied, wi h sligh adjus men s, o h ee eal-wo ld p ob-
lems: a glass p oduc ion uni , a con inuous ca e uni and a hospi al. A se
o benchma k ins ances was also used in o de o e alua e he model’s pe -
o mance when sol ing la ge p oblems and o compa e esul s wi h o he
me hods. Two main goals o he model we e o ensu e a balanced and eq-
ui able schedule be ween all employees, in e ms o wo kload, and also o
espec a p ede ined sequence o wo k shi s and days-o , ei he ollowing
wo k ules o employees’ p e e ences. The i s goal was achie ed, ini ially,
h ough he le elling o he numbe o days ha each eam wo ks in each
shi , as imposed by he objec i e unc ion de ined o he gene al model and
in a nex phase, h ough he imposi ion o equal schedules o all employ-
ees, wi h a ime lag, o a p ede ined numbe o days, be ween hem. This
ea u e gi es a cyclic dimension o he schedule. The second condi ion was
achie ed h ough he o mula ion o an a ay o indices ha , oge he wi h
he de ini ion o a maximum and a minimum numbe o consecu i e days,
113
Chap e 10. Conclusions
enable he imposi ion o any desi ed pa e n o wo k shi s and days-o .
This pa e n can be he same o all employees o can be de ined acco ding
o con ac ypes, skills, employees p e e ences, e c. This o iginal o mu-
la ion also makes i possible o con ol he pe iodici y o days-o , as well
as he leng h o he ou o sub-pe iod o he planning ho izon. The de i-
ni ion o he planning pe iod is no a e y explo ed issue in he li e a u e,
since i is closely ela ed o demand o ecas pe iods and i is o en an inpu
pa ame e . Bu he ini ially se planning pe iod may no be he one ha
be e i s he p oblem’s ea u es and so i is pe inen o s udy which is he
“ideal” planning pe iod o a speci ic ins ance. This expe imen was ca ied
ou . E en hough cons ain s on he pe iodici y o long-weekends and on
planned absences we e no an ini ial issue, he model was able o handle
hem as well, as shown in wo o he case-s udies.
The model de eloped in his wo k demons a ed o be gene al and lexible,
wi h se e al deg ees o eedom and wi h he capaci y o being easily applied
o di e en eal-li e s a scheduling p oblems, bu a he same ime wi h a
cyclic ea u e ha ensu es he equi ableness and p edic abili y o he sched-
ule. The cyclic app oach, o en conside ed o be in lexible and no easily
adjus able, p o ed o be lexible enough o success ully sol e p oblems ha
a e ypically add essed wi h acyclic scheduling, namely wi h he e ogeneous
s a and luc ua ing demand le els. This is a new insigh and ep esen s a
no el con ibu ion o he academic li e a u e.
F om a company’s poin o iew, he use o he au oma ic scheduling model
p oposed in his esea ch wo k can ep esen a powe ul ool o inc easing
bo h he e iciency and he e ec i i y o he s a scheduling p ocess, leading
o highe p o i abili y and p oduc i i y. Howe e , he implemen a ion o
such a solu ion in o p ac ice is no always easy, i deeply depends on he
in ol emen o he company in he whole de elopmen p ocess.
114
10.2 Fu u e esea ch di ec ions
The de eloped heu is ic app oach ep esen s an al e na i e me hod o sol -
ing one o he eal-wo ld p oblems s udied in his hesis, allowing also o a
compa a i e e alua ion o he op imiza ion model’s pe o mance. An o igi-
nal con ibu ion o he heu is ic is ha wi h some simple calcula ions o e
he p oblem’s inpu da a, i is possible o o esee he exis ence o a easible
solu ion. This educes he solu ion sea ch space.
Addi ionally, he comp ehensi e s udy on he s a scheduling p oblem and
he insigh in o hospi ali y managemen ope a ions cons i u e wo asse s o
esea che s looking o backg ound on hese opics.
As a conclusion, we p oposed a gene ic, no el and aluable app oach o
s a scheduling. We de eloped gene ic me hodologies, showed hei lexibil-
i y and sol ed a se o di e en p oblems. We challenged he po en ial o
cyclic scheduling and p o ed i can be lexible. We de eloped an inno a i e
o mula ion o sequence and consecu i eness o shi s. And we belie e his
esea ch wo k can add alue o a company by leading o cos educ ion and
an inc ease in he p oduc i i y.
10.2 Fu u e esea ch di ec ions
In o de o consolida e ou indings, u u e esea ch could add ess he appli-
ca ion o he p oposed IP model o mo e eal-wo ld p oblems, om di e en
ac i i y sec o s. Hospi ali y managemen is a p omising a ea ha should be
mo e explo ed, namely ho els (housekeeping s a ) and es au an s.
Conce ning he p oblems’ ea u es, all he p oblems s udied in his wo k
had ixed shi s. I would be in e es ing o ex end he IP model o conside
he case o a iable shi s, in e ms o s a ing- imes, leng h o e en he
placemen o b eaks.
One o he d awbacks ha a e usually poin ed ou in he li e a u e o cyclic
115

Chap e 10. Conclusions
scheduling app oaches is hei di icul y in handling non p edic ed absences.
In Chap e 5 absen ees we e eplaced wi hin hei eam. We ha e also shown
how he IP model can ocasionally accommoda e planned absences (Chap e
7). A sys ema ic way o add essing his cons ain could be wo hy o u he
esea ch.
Al hough he p oposed heu is ic was de eloped o a speci ic p oblem, i
p o ed o be lexible enough o accoun o a ia ions in some o he p ob-
lem’s pa ame e s and cons ain s. The achie ed esul s encou age u he
ex ensions o he p ocedu e in o de o conside , o example, di e en shi
daily demands o o bidden sequences o shi s.
116
Re e ences
Abdennadhe , S. and Schlenke , H. (1999). Nu se scheduling using con-
s ain logic p og amming. In P oceedings o he 11 h Con e ence on In-
no a i e Applica ions o A i icial In elligence, pages 838–843.
Addou, I. and Soumis, F. (2007). Bech old-Jacobs gene alized model o shi
scheduling wi h ex ao dina y o e lap. Annals o Ope a ions Resea ch,
155:177–205.
Aickelin, U. and Whi e, P. (2004). Building Be e Nu se Scheduling Algo-
i hms. Annals o Ope a ions Resea ch, 128(1-4):159–177.
Al a es, H. (2004). Su ey, ca ego iza ion, and compa ison o ecen ou
scheduling li e a u e. Annals o Ope a ions Resea ch, 127(1):145–175.
Al a es, H. K. (1998). An e icien wo-phase algo i hm o cyclic days-o
scheduling. Compu e s & Ope a ions Resea ch, 25(11):913 – 923.
An unes, A. F. and Moz, M. (2011). Op imiza¸c˜ao do escalonamen o de en-
e mei os numa unidade hospi ala . In INESC-COIMBRA, edi o , Li o
de Ac as do 15 Cong esso da Associa¸c˜ao Po uguesa de In es iga¸c˜ao Op-
e acional (IO2011), pages 25–36.
A abey e, J., Fea nley, J., S eige , F., and Tea he , W. (1969). The ai line
c ew scheduling p oblem: A su ey. T anspo a ion Science, 3(2):140–163.
Aykin, T. (2000). A compa a i e e alua ion o modeling app oaches o he
117
REFERENCES
labo shi scheduling p oblem. Eu opean Jou nal o Ope a ional Resea ch,
125(2):381–397.
Azaiez, M. (2005). A 0-1 goal p og amming model o nu se scheduling.
Compu e s & Ope a ions Resea ch, 32(3):491–507.
Bake , K. R. (1976). Wo k o ce Alloca ion in Cyclical Scheduling P oblems:
A Su ey. Ope a ional Resea ch Qua e ly (1970-1977), 27(1):155.
Balak ishnan, N. and Wong, R. T. (1990). A ne wo k model o he o a ing
wo k o ce scheduling p oblem. Ne wo ks, 20:25–42.
Ba d, J. F., Binici, C., and DeSil a, A. H. (2003). S a scheduling a
he Uni ed S a es Pos al Se ice. Compu e s & Ope a ions Resea ch,
30(5):745–771.
Ba os, C. P. and Masca enhas, M. J. (2005). Technical and alloca i e
e iciency in a chain o small ho els. In e na ional Jou nal o Hospi ali y
Managemen , 24(3):415 – 436.
Ba os, C. P., Peypoch, N., and Solonand asana, B. (2008). E iciency and
p oduc i i y g ow h in ho el indus y. In e na ional Jou nal o Tou ism
Resea ch.
Beaulieu, H., Fe land, J. A., Gend on, B., and Michelon, P. (2000). A ma he-
ma ical p og amming app oach o scheduling physicians in he eme gency
oom. Heal h ca e managemen science, 3(3):193–200.
Beaumon , N. (1997). Using mixed in ege p og amming o design employee
os e s. Jou nal o he Ope a ional Resea ch Socie y, 48(6):585–590.
Bech old, S. and Jacobs, L. (1990). Implici modeling o lexible b eak as-
signmen s in op imal shi scheduling. Managemen Science, 36(11):1339–
1351.
118
REFERENCES
B o he on, B. (1999). Towa ds s de ini i e iew o he na u e o hospi al-
i y and hospi ali y managemen . In e na ional Jou nal o Con empo a y
Hospi ali y Managemen , 11(4):165–173.
B o he on, B. (2006). Some hough s on a gene al heo y o hospi ali y.
Tou ism Today, (6):7–19.
B o he on, B. and Wood, R. C. (2008). The na u e and meanings o ‘hos-
pi ali y’. In The SAGE Handbook o Hospi ali y Managemen , chap e 1,
pages 35–61. SAGE.
B ucke , P., Bu ke, E. K., Cu ois, T., Qu, R., and Vanden Be ghe, G.
(2008). A shi sequence based app oach o nu se scheduling and a new
benchma k da ase . Jou nal o Heu is ics, 16(4):559–573.
B usco, M. and Johns, T. (1996). A sequen ial in ege p og amming me hod
o discon inuous labo ou scheduling. Eu opean Jou nal o Ope a ional
Resea ch, 95(3):537–548.
Bu ke, E. (2003). A Tabu-Sea ch hype heu is ic o ime abling and os e -
ing. Jou nal o Heu is ics, 9(6):451–470.
Bu ke, E., Cowling, P., De Causmaecke , P., and Vanden Be ghe, G. (2001).
A meme ic app oach o he nu se os e ing p oblem. Applied in elligence,
15(3):199–214.
Bu ke, E., De Causmaecke , P., and Vanden Be ghe, G. (1999). A Hyb id
Tabu Sea ch Algo i hm o he Nu se Ros e ing P oblem. In e Al., B. M.,
edi o , Lec u e No es in A i icial In elligence, olume 1585, pages 187–
194. Sp inge .
Bu ke, E., Hyde, M., Kendall, G., Ochoa, G., Ozcan, E., and Woodwa d,
J. R. (2010a). A classi ica ion o hype -heu is ic app oaches. In Gend eau,
M. and Po in, J.-Y., edi o s, Handbook o Me aheu is ics, olume 146
119
REFERENCES
Schedules in Real Time. Co nell Ho el and Res au an Adminis a ion
Qua e ly, 40(3):85.
Thompson, G. M. (2003). Labo Scheduling: A Commen a y. Co nell
Hospi ali y Qua e ly, 44(5-6):149–155.
Thompson, G. M. and Goodale, J. C. (2006). Va iable employee p oduc i -
i y in wo k o ce scheduling. Eu opean Jou nal o Ope a ional Resea ch,
170(2):376 – 390.
Topaloglu, S. and Ozka ahan, I. (2004). An Implici Goal P og amming
Model o he Tou Scheduling P oblem Conside ing he Employee Wo k
P e e ences. Annals o Ope a ions Resea ch, 128(1-4):135–158.
To e dell, P. (2005). Wo k schedules. Handbook o wo k s ess, page 53.
Ulusam Se¸ckine , S., G¨ok¸cen, H., and Ku , M. (2007). An in ege p o-
g amming model o hie a chical wo k o ce scheduling p oblem. Eu opean
Jou nal o Ope a ional Resea ch, 183(2):694–699.
Valouxis, C. and Housos, E. (2000). Hyb id op imiza ion echniques o he
wo kshi and es assignmen o nu sing pe sonnel. A i icial in elligence
in medicine, 20(2):155–75.
Van den Be gh, J., Beli¨en, J., De B uecke , P., Demeulemees e ,
E., and De Boeck, L. (2012). Pe sonnel scheduling: A
li e a u e e iew. Eu opean Jou nal o Ope a ional Resea ch,
h p://dx.doi.o g/10.1016/j.ejo .2012.11.029.
Wa ne , D. M. (1976). Scheduling nu sing pe sonnel acco ding o nu sing
p e e ence: a ma hema ical p og amming app oach. Ope a ions Resea ch,
24(5).
W en, A. (1996). Scheduling, ime abling and os e ing - a special ela-
ionship? In Selec ed pape s om he Fi s In e na ional Con e ence on
126

REFERENCES
P ac ice and Theo y o Au oma ed Time abling, pages 46–75, London,
UK. Sp inge -Ve lag.
W en, A. (1998). Heu is ics ancien and mode n: T anspo scheduling
h ough he ages. Jou nal o Heu is ics, 4:87–100.
W en, A. and Rousseau, J. (1995). Bus d i e scheduling - an o e iew.
Technical Repo July, Uni e si y o Leeds, School o Compu e S udies.
127