The staff scheduling problem: a general model and applications

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