The staff scheduling problem: a general model and applications

The staff scheduling problem: a general model and applications Marta Soares Ferreira da Silva Rocha A Thesis submitted to Faculdade de Engenharia da Universidade do Porto for the doctoral degree in Industrial Engineering and Management Supervisors Professor Jos´e Fernando da Costa Oliveira Professor Maria Ant´onia da Silva Lopes de Carravilla Faculdade de Engenharia da Universidade do Porto 2013 Abstract The scheduling of employees is a complex and time-consuming task. It is complex because it involves assigning the right people to the right job at the right time. It is conditioned by several legal, work and other organizational rules. And it often copes with conflicting objectives, such as the minimization of the labor costs or the workforce size and the satisfaction of the employees preferences, for example. It is time-consuming because it is a periodic task and it is still manually performed in most organizations. The research work described in this thesis deals with the development of methods for the automatic scheduling of employees, in particular for their simultaneous assignment to working shifts and days-off. The work focuses on the design of a general integer programming (IP) model that, following an optimization approach, can be easily adapted and solve a wide set of different real-world problems. An innovative formulation of the sequence and consecutiveness constraints gives the model the flexibility to accommodate variable features of the problems. A cyclic approach ensures the generation of equitable and predictable work schedules. The application of the general model is illustrated with three real-world case studies and a collection of benchmark instances available in the literature. Computational results demonstrate the good performance of the model, achieving optimal solutions for the majority of the problems in useful time. A constructive heuristic is also developed for solving one of the case-studies. Based on a set of simple calculations, the proposed procedure reveals to be an efficient alternative to the IP optimization approach for solving the practical problem considered. The good performance achieved with tests on a set of larger computer generated instances confirms the robustness of this approximate approach. Although its apparent pertinency to the activity sector, staff scheduling problems in hospitality management have been quite unnoticed by the research community. This thesis dedicates a chapter to this topic, namely to the assessment of the potential of hospitality management as an application area for staff scheduling problems and of possible resolution approaches. i ii Resumo O escalonamento de pessoal ´e uma tarefa complexa e fortemente consumidora de recursos. ´ E complexa porque envolve a afeta¸c˜ao das pessoas certas ao trabalho certo no momento certo. ´ E condicionada por diversas regras de natureza legal, laboral ou organizacional. Lida normalmente com objetivos divergentes, tais como a mimimiza¸c˜ao de custos ou a dimens˜ao da equipa de trabalho e a satisfa¸c˜ao das preferˆencias dos trabalhadores, por exemplo. Consome recursos porque ´e feita periodicamente e ainda de modo manual, em muitas organiza¸c˜oes. O trabalho de investiga¸c˜ao descrito nesta tese aborda o desenvolvimento de m´etodos para o escalonamento autom´atico de pessoal, em particular com a sua afeta¸c˜ao simultˆanea a turnos de trabalho e dias de descanso. O trabalho centra-se no desenvolvimento de um modelo geral de programa¸c˜ao inteira que, seguindo uma abordagem de otimiza¸c˜ao, pode ser facilmente adaptado e resolver um conjunto alargado de diferentes problemas reais. A formula¸c˜ao inovadora das restri¸c˜oes de sequˆencia e consecutividade confere ao modelo a flexibilidade necess´aria para acomodar caracter´ısticas vari´aveis dos problemas. Uma abordagem c´ıclica assegura a gera¸c˜ao de hor´arios equilibrados e previs´ıveis. A aplica¸c˜ao do modelo geral ´e ilustrada atrav´es de trˆes casos de estudo baseados em problemas reais e de um conjunto de instˆancias de benchmark dispon´ıveis na literatura. Os resultados computacionais demonstram o bom desempenho do modelo, obtendo as solu¸c˜oes ´otimas para a maior parte dos problemas em tempo ´util. Uma heur´ıstica construtiva foi tamb´em desenvolvida para um dos casos de estudo. Baseado num conjunto de c´alculos simples, o procedimento proposto revela ser uma alternativa eficiente `a abordagem de otimiza¸c˜ao para a resolu¸c˜ao do problema pr´atico considerado. O bom desempenho conseguido com testes em instˆancias de maior dimens˜ao comprova a robustez deste m´etodo aproximado. Apesar da sua aparente pertinˆencia para o sector de atividade, os problemas de escalonamento de pessoal na ´area de gest˜ao da hospitalidade n˜ao tˆem merecido a devida aten¸c˜ao por parte da comunidade acad´emica. Esta tese dedica um dos seus cap´ıtulos a este t´opico, nomeadamente `a avalia¸c˜ao do potencial da gest˜ao da hospitalidade como uma ´area de aplica¸c˜ao para os problemas de escalonamento de pessoal e de poss´ıveis abordagens de resolu¸c˜ao. iii iv Acknowledgments This thesis is the culmination of the work accomplished during the most demanding phase of my personal life. During these four years, I felt my physical and emotional endurance being strained to the limit. If I succeeded and reached this far I owe it to the people that supported me in this journey, to whom I here address my sincere acknowledgments. First of all, I would like to thank my supervisors, Jos´e Fernando Oliveira and Maria Ant´onia Carravilla, for trusting me this exceptional opportunity to redirect the course of my career. It was a privilege to be part of your research group but also to be part of your teaching group. I can now know how it feels to be on the other side of the classroom desk. It was a really enriching experience that allowed me to develop new competences. Thank you for keeping me always focused and motivated. Thank you for your dedication. Thank you for caring. My second acknowledgment goes to all the colleagues from the IO Lab. Some have already left. Some have just arrived. Others come and go. Others are there to stay. Although I missed a lot of lunches, dinner parties and evening outs, I really enjoyed the company of every one of you. Thank you for your understanding and caring. I must also thank Miguel Gomes, my “Mac adviser”, for his availability and help. A heartfelt thanks to Vera, with whom I shared this path since the first day. You have been an outstanding friend. Thank you for all the coffees, all the talks, all the help. Thank you for being always there. I thank my parents, brother and in-laws for giving me the necessary conditions to carry out this project, especially during these last 1,5 years. Thank you for your unconditional support. I dedicate this thesis to Andr´e, Matilde and Beatriz. Thank you for your infinite love. v vi Table of Contents Abstract i Resumo iii Acknowledgements v Table of Contents vii List of Figures x List of Tables xiv 1 Introduction 1 1.1 Motivation ............................ 1 1.2 Research approach . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Thesisoutline........................... 5 2 Staff scheduling problems 7 2.1 Defining the problem . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Modeling the problem . . . . . . . . . . . . . . . . . . . . . . 14 2.3 Reviewing related works in the literature . . . . . . . . . . . . 20 2.3.1 Surveys and general works . . . . . . . . . . . . . . . . 20 2.3.2 Specific works . . . . . . . . . . . . . . . . . . . . . . . 24 2.4 Summary ............................. 32 vii LIST OF FIGURES xiv List of Tables 4.1 Example of a possible sequence of shifts . . . . . . . . . . . . 48 5.1 Sequence of shifts for the glass production unit . . . . . . . . 57 5.2 Model size and computational times for a 5-team schedule . . 60 5.3 Annual number or work-days for each team . . . . . . . . . . 61 6.1 Sequence of shifts for the continuous care unit . . . . . . . . . 67 6.2 Model computational parameters and results for the continuouscareunit........................... 70 7.1 Minimum/maximum no. of nurses required daily for each shift 76 7.2 Types of contracts . . . . . . . . . . . . . . . . . . . . . . . . 76 7.3 Sequence of shifts for the hospital problem . . . . . . . . . . . 77 7.4 Association of index tto the type of contract . . . . . . . . . 79 7.5 Statistic analysis of the solutions . . . . . . . . . . . . . . . . 82 8.1 First type of allowable sequences . . . . . . . . . . . . . . . . 89 8.2 Allowable sequences . . . . . . . . . . . . . . . . . . . . . . . 89 8.3 Allowable sequences for nS=2 . . . . . . . . . . . . . . . . . . 90 8.4 Computational times for the benchmarking instances using the IP model, MC-T and FCS . . . . . . . . . . . . . . . . . . 94 9.1 Computational results for 5 teams . . . . . . . . . . . . . . . 105 9.2 Computational results for a set of combinations of the ratio nS/nT. ..............................110 xv LIST OF TABLES xvi Chapter 1 Introduction 1.1 Motivation Staff scheduling is a common problem to most organizations, either from the service sector or industrial plants. Basically, it seeks to assign employees to tasks, work shifts or rest periods, taking into account organizational and legal rules, employees’ skills and preferences, demand needs, and other applicable requirements. It is therefore a complex problem and a top concern for human resource management (Enz (2009)). Even nowadays, it is still done manually in several activity sectors, consuming time and resources that could be used more efficiently with automatic scheduling generators. Thompson (2003) points out three reasons for caring about staff scheduling: the time spent developing a schedule by hand leaves the manager less time for managing the employees and interacting with the customers; a schedule that better satisfies employees’ preferences increases the on-job-performance and consequently the productivity and the service quality; in a good schedule work is assigned in the most effective manner, leading to a cost reduction due to over and understaffing and an increase in profitability. It is not only a matter of reducing costs, but also a matter of finding a solution that better fits cost minimization, compliance with work and legal rules, satisfaction 1 Chapter 1. Introduction and well-fare of employees. The design of schedules should take therefore into account objective factors such as labour costs, applicable legislation, organizational rules and demand needs but also other sensitive dimensions like flexibility, stability, predictability or fairness. It is generally acknowledged the significative impact that these last attributes can have on the productivity and engagement of an employee (Glass and Knight (2010)). Stressful factors such as short periods of rest and long periods of work, inadequate distribution between rest and work periods or non-standard working shifts, for example, can negatively affect the mental and physical health of employees (Totterdell (2005)). Although the staff scheduling problem has been intensively explored in the literature, studies usually focus on solving very particular problems that derive from practical needs. Models are usually developed for specific applications and their adaptation to other cases implies significative reformulation. It is generally considered by researchers that cyclic scheduling approaches are inflexible because they impose a rigid schedule, not adjustable to unpredictable changes. Workload balance is usually tackled as a non-mandatory or soft constraint of the problem. When dealing with real-life problems, the trend has been to use approximate solution approaches rather than optimization methods. This is mainly due to their high complexity and size. However such approximate procedures are, by nature, tailored for specific problems. This research has a twofold motivation. From a business perspective, it aims to contribute to the increase in both productivity and profitability of a company. The development of an automatic scheduling procedure and the adequate design of the schedules contributes to these goals. From an academic point of view, this work aims to provide a wide-range approach that is able to find optimal solutions for different real-life problems. It intends to be innovative, combining an original formulation of the sequence 2 1.2 Research approach and consecutiveness constraints with a flexible cyclic scheduling approach. 1.2 Research approach The main objective of the research work described in this thesis is to develop an optimization model that can be easily adjusted to address different real-life staff scheduling problems, from different application areas. This goal imposes a preliminary investigation into the current literature on staff scheduling problems in order to understand the problem in depth and to justify the relevance of the proposed approach. An additional output of this literature review is the insight into the particular application of these problems to hospitality management operations, which is an almost unexplored combination. Stimulated by three real case-studies, the research concentrates on solving the problem of simultaneously assigning employees to work shifts and days-off in each of the three applications. The problems have similar work environments based on a 24-hour continuous operation and work shifts with fixed starting-times and lengths. The workforce is single-skilled in two of the problems, but in one of the case-studies multi-skilled employees are grouped in teams and the scheduling is made for each team, which is a novel modelling aspect. While in one of the cases the staff is composed only by full-time employees, the other two problems consider different types of labor contracts. Constraints common to all problems concern daily demand requirements, sequences of work shifts and days-off and consecutive number of work shifts/days-off. Long weekends-off periodicity and planned absences are occasionally tackled in different case-studies. Each one of the three problems has a different sequence of shifts and days-off that must be followed and the workload must be evenly distributed between all the employees. These two conditions represent the main modelling chal3 Chapter 1. Introduction lenges of this work. The way they are dealt with in the proposed formulation intends to be a worthy contribution to the research literature. The sequence and consecutiveness constraints are formulated in a very innovative way that gives the model an increased flexibility to tackle any pattern of work shifts and days off. The workload balance is ensured by the cyclic scheduling approach, through a hard constraint. To counteract the inflexibility often assigned to cyclic scheduling, it is used to successfully solve problems that are typically addressed with acyclic approaches, namely problems with a heterogeneous workforce and fluctuating demand levels. Instead of setting the planning horizon as an input of the problem, as is the common practice in the literature, we study several planning periods in order to choose the planning horizon that better fits the goals of the problem. We explore the integration of periods with different lengths into a longer planning horizon. This is another original contribution of this research. The developed integer programming (IP) general model is successfully applied to the three case-studies with minor adjustments, mainly parameterizations. In order to demonstrate its consistency and reinforce its flexibility, the model is also adapted to solve a collection of benchmark instances. The study of a heuristic approach aims to enrich the contribution of this research with a comparison between an optimization and an approximate method for solving one of the real-world case-studies. The heuristic procedure is based on simple calculations and assumptions that derive from the analysis of the problem’s input data. Although it is built for a particular problem, the heuristic demonstrates a consistent performance when applied to a set of larger computer generated instances, which result from the variation of some of the parameters, revealing to be a viable alternative to the optimization method. 4 1.3 Thesis outline 1.3 Thesis outline The thesis is organized around 9 chapters, besides the present introductory chapter. Chapter 2 presents a comprehensive overview on the staff scheduling problem, its main features, variants and most common applications. Some relevant modeling issues are addressed and the related literature is reviewed. The aim is to provide essential background on the topic. Chapter 3 is devoted to a study on hospitality management, with the purpose of understanding the concept of hospitality and exploring the potential of this activity sector as an application area for staff scheduling problems. Chapters 4, 5, 6, 7 and 8 concern the developed optimization approach. The general IP model is firstly introduced in Chapter 4. The next three chapters illustrate the application of the general IP model to three practical case studies, one from an industrial plant and two from services. Chapter 5 reports a long-term staff scheduling problem in a glass production unit. Then, the general model is adjusted to the problem of scheduling a set of care takers in a continuous care unit (Chapter 6). Chapter 7 concerns the problem of nurse scheduling in a portuguese hospital. In Chapter 8, the general model is adjusted to a set of benchmark instances. The application of the model is extended to a range of problems with larger size, testing the consistency of the model’s performance. Chapter 9 presents a constructive heuristic to solve the glass unit problem. A comparison between this approach and the previous optimization approach is carried out. The last chapter (Chapter 10) sums up the accomplished research work and suggests future developments. 5 Chapter 1. Introduction 6 Chapter 2 Staff scheduling problems The aim of this chapter is to provide some important background information on staff scheduling problems to a reader who is not deeply familiar with the subject. The first section presents the staff scheduling problem in detail, describing the sub-problems and the application areas that have been more explored in the literature. Next, an overview on the main modeling issues is included. The last section of the chapter goes through some of the most relevant related works published in the literature of staff scheduling, from surveys and general studies to more specific research papers. 2.1 Defining the problem Wren (1996) defines scheduling as “the allocation, subject to constraints, of resources to objects being placed in space-time, in such a way as to minimize the total cost of some set of the resources used” and rostering as “the placing, subject to constraints, of resources into slots in a pattern. One may seek to minimize some objective, or simply to obtain a feasible allocation. Often the resources will rotate through a roster. (...) Once shifts have been produced showing the daily work of personnel, these shifts are placed into a roster to show which shifts are worked by individuals on particular days”. 7 Chapter 2. Staff scheduling problems problem, where timetables usually repeat on a weekly basis. In the opposite situation are call centers, where demand fluctuates every week and so schedules are typically acyclic. Cyclic scheduling has the advantages of providing an equal distribution of shifts and days-off among all employees and of providing stability, since employees know their schedule some time in advance and can plan their lives according to their future availability. On the other hand, they lack flexibility, being much less adjustable to last-minute changes. 2.2 Modeling the problem Different work environments imply different requirements and, consequently, staff scheduling problems with distinct features naturally arise. Some of the main differentiating dimensions that have been explored in the literature are: •the adopted planning period, which can range from few days to several weeks or months up to one year, or can be user-defined; •the operating hours of the organization, which can work in a 24-hours continuous or in a less than 24-hours discontinuous operation; •the workforce, which can be composed of employees with: single or mixed contract types (full-time/part-time), different skills, distinct productivity levels, different availability and/or individual personal preferences; employees substitutability rules, based on hierarchy or on specific skills for example, may be considered; •shift flexibility: working shifts can be fixed or can vary in terms of starting-time, length, placement and/or duration of breaks; overlap between shifts may be considered. 14 2.2 Modeling the problem The problems addressed by this research work have a 24-hours continuous multi-shift environment, with all shifts having fixed starting-times, lengths and breaks placement. Therefore, shift flexibility is not considered. In terms of workforce, the problems vary: the glass unit and the hospital consider only a fixed full-time set of workers while the continuous care unit considers both full and part-time work, which can vary according to the demand requirements. Mixed skills are not considered but in the hospital case study workers have different contract types that must be taken into account when modeling the problem. The planning period is not fixed. Several periods were tested in order to find the one that allowed for a better solution, i.e., a better schedule. When modeling the problem, constraints and objectives also vary according to the problem’s features. Types of constraints that are often found in the literature include: •coverage: minimum/maximum number of assignments required/allowed per shift or per week day or other planning interval; •consecutiveness or sequence: mandatory by law or preferred by the employees, ex. maximum/minimum number of consecutive working/rest days, compulsory patterns of working shifts and days-off (stints), day(s) off after a night shift, etc.; •weekends: weekends off periodicity, compensation for weekends assignments by week days-off, long weekends; •workload balance: even distribution of shifts/days-off between all the employees. Constraints can be treated either as hard constraints, if their satisfaction is mandatory, or otherwise as soft constraints,. The non-fulfillment of soft 15 Chapter 2. Staff scheduling problems constraints is often penalized, for example in the objective function when using mathematical programming models or in the evaluation function in a metaheuristic approach. The models proposed in this work consider all these types of constraints as hard constraints. Emphasis is yet given to the formulation of sequence constraints that, to the best of our knowledge, has not been proposed before in the literature. The workload balance is a main concern for all the problems addressed. Weekend-off periodicity constraints were considered in the glass industry case study and the hospital model was extended in order to account for planned absences. Types of objectives that are often used to model the staff scheduling problem include: •to minimize total labour costs; •to maximize the percentage of the contractual work hours assigned or to minimize the percentage of the unassigned hours; •to minimize workforce size; •to minimize the gap between assignments and demand (under or over coverage); •to minimize the gap between assignments and employees’ preferences; •to balance the workload between employees; •to maximize employees satisfaction. Although having different objective functions, all the problems studied in this work share the goal of achieving a balanced and fair schedule for all workers. In the glass unit problem this is directly formulated in the objective function. In the continuous care unit problem, the objective function seeks to 16 2.2 Modeling the problem minimize the part-time requirements. In the hospital problem, the objective function looks for the minimization of the deviation between assigned and contracted hours. Integer Programming (IP) has been one of the most used techniques in the literature to model the staff scheduling problem. Most of the IP formulations are based on the set covering model introduced by Dantzig (1954). An example is the following model for a tour scheduling problem, proposed by Alfares (2004). Minimize W= J X j=1 xj subject to: J X j=1 aijxj≥ri,i= 1,2, ..., I xj≥0 and integer, j= 1,2, ..., J In this formulation the objective is to minimize the number of employees assigned to all Jtours. The planning horizon is a week, while originally in Dantzig’s model it was a day, representing the decision variable xjthe number of employees assigned to weekly tour j. The coefficients aij take the value 1 if time period iis a work period for tour j, otherwise equal 0. The minimum required labour demand is represented by riand Iis the number of time periods to be scheduled over the week. Considering, for example, an operating day from 7 a.m. to 2 p.m. and time periods (i) of 30 minutes, we would have 98 time periods (I) to be scheduled over the 7 days of the weekly planning horizon. Figures 2.7 and 2.8 illustrate 17 Chapter 2. Staff scheduling problems this problem with the correspondent staff needs (ri) for each planning time period and the matrix of coefficients aij, for J= 1,...,4 tours. Figure 2.7: Example of a weekly scheduling demand requirement. Figure 2.8: Example of the weekly scheduling aij matrix data. aij take the value 1 if time period iis a work period for tour j, and 0 otherwise. The model associates to each tour (defined by a shift and break periods combination) an explicit decision variable xj. In problems with high shift flexibility, having different shift start, finish or break times, different shift lengths, etc., this formulation associates a separate integer variable to each variation of each of these features and therefore, the number of variables can increase in such a way it is very difficult or even impossible to get an optimal solution. To overcome this drawback some authors have worked on the problem formulation in order to reduce the model size using, for example, implicit modeling. This technique associates each decision variable to a shift-type or a tour-type. A shift type can be a possible combination of shift starting time, shift length and break window (interval of time in which a break can start), for example. Additional constraints are introduced in order to ensure the correct placement of breaks. A tour-type can have fixed starting-times for every day of the tour or variable starting-times. In this last situation, a start-time band can be defined, which is a range in which shift start-times can vary within a single tour. When start-time bands contain shifts with the same coverage of periods they are named overlapping start18 2.2 Modeling the problem time bands. Implicit modeling has proven to be particularly important in those staff scheduling problems that deal with variable shift startingtimes and with breaks placement. For detailed information and practical applications of this technique along the last decades we refer to Bechtold and Jacobs (1990), Brusco and Johns (1996), Aykin (2000), Isken (2004), Addou and Soumis (2007) and Rekik et al. (2010). In order to overcome the complexity of solving large-size set covering problems, some authors have explored network flow formulations (Balakrishnan and Wong (1990), C¸ezik et al. (2001), Moz and Pato (2004)). In a network flow model, the source node can correspond, for example, to the beginning of the first day and the sink node to the end of the last day of the planning period. Each node corresponds, then, to the end of a day and to the beginning of the following day. Each work shift or rest period is represented, in the same example, by an arc. Each path from the source to the sink node represents an alternative feasible pattern of work and rest periods, which satisfies the sequence and maximum/minimum consecutive shift/days-off blocks constraints. This option allows for a simple visual representation of every feasible tour, which can be significantly advantageous in problems with many sequence constraints. There are other alternative representations, though, that have been adopted by different authors. While coverage requirements are typically formulated as hard constraints, workload balance and sequence constraints are often treated as soft constraints, i.e., constraints that can be violated, though at a defined cost added to the objective function. Goal programming or multi-objective techniques are used to incorporate these constraints into the scheduling models. Deviations from desired patterns of shifts, patterns of working and rest days, ratio between number of night and day shifts or other requirements are penalized in the objective function, which seeks the minimization of the sum of the weighted deviations (see, for example, the work of Topaloglu and Ozkara19 Chapter 2. Staff scheduling problems han (2004), Azaiez (2005), Burke et al. (2010b) or Castillo et al. (2009)). With these formulations the user can analyze the impact of giving different weights to each of the goals. This sensitivity analysis can be very helpful in supporting the decision of choosing the most convenient solution from a set of feasible solutions. Cˆot´e et al. (2009) divide mathematical programming formulations into three categories: compact assignment, explicit set covering and implicit set covering formulations. The last two have already been briefly presented in this section. Compact assignment formulations “use decision variables to assign activities to each employee at each period” of time. It is our conviction that the models proposed in this work can be classified as compact assignment formulations as will be explained in detail in Chapters 4 to 8. Our formulation uses binary variables to assign the working and rest shifts to each employee in each of the days of the planning period. It cannot be defined as a common assignment problem since, exception made for the glass unit problem, there is not a one to one assignment relationship. Although each employee can be assigned to only one shift, either a work or a rest shift, the same shift can be allocated to more than one employee. Demand coverage, consecutiveness and sequence restrictions are addressed as hard constraints. Workload balance is also tackled by hard constraints, imposing a cyclic scheduling approach to the model. 2.3 Reviewing related works in the literature 2.3.1 Surveys and general works The developments on staff scheduling problems, their applications, models and solution methods reported in the literature, have been collected and reviewed by several authors over the last four decades. 20 2.3 Reviewing related works in the literature Ernst et al. (2004a) present one of the most comprehensive surveys of the staff scheduling problem. More than 700 published papers are classified according to: the problem type (or sub-problem) addressed, the solution approach and the application area. In order to classify the sub-problems, Ernst et al. propose a framework based in several categories, which include, by order of representativeness: crew scheduling, tour scheduling, flexible demand, workforce planning, crew rostering, shift scheduling, cyclic rostering, daysoff scheduling, shift demand, task based demand, demand modeling, task assignment, shift assignment, among others. Some of these sub-problems have already been described in 2.1. For a detailed description of all the categories see Ernst et al. (2004b). In a very recent work, Van den Bergh et al. (2012) review 291 articles published from 2004 onwards. Papers are categorised according to four main topics: 1) personnel characteristics (contract type, skills, individual/team) decision delineation and shifts definition (overlap, start-time, length); 2) constraints (hard/soft, coverage, time-related, fairness and balance), performance measures (different costs) and flexibility (related to constraints); 3) solution method and uncertainty incorporation (uncertainty of demand, arrival and capacity) and 4) application area and applicability of research. A list of the journals with more than 3 publications on personnel scheduling is also included. All manuscripts are listed and categorised in 16 detailed tables, allowing for a straightforward usage of the information. Some relevant findings about the reviewed papers can be highlighted. The coverage constraint is a key constraint, with almost 75% of the authors defining it as a hard constraint. When considered, the balance constraint is modelled as a soft constraint by almost all the researchers. The consecutiveness and sequence constraints are tackled as soft or hard according to the origin of the imposition, whether if it is a legal setting or a preference scenario, for example. In terms of solution methods, mathematical programming approaches 21 Chapter 2. Staff scheduling problems and metaheuristics lead the choices of the authors. In a innovative perspective, this survey work also addresses the integration of uncertainty in the decision-making process as well as the applicability of the staff scheduling research in the real-world setting. Transportation systems, nurse scheduling and call-centers are among the most explored application areas of the staff scheduling problem in the literature. Within the transportation sector, the airline crew scheduling and the bus driver scheduling appear as the most studied problems. Surveys on the airline crew scheduling can be found in Arabeyre et al. (1969), in Etschmaier and Mathaisel (1985) and more recently in Gopalakrishnan and Johnson (2005). For an overview of advances in the bus driver scheduling problem see Wren and Rousseau (1995) and Wren (1998). Reference review studies in nurse scheduling are the works of Warner (1976), Silvestro and Silvestro (2001) and Burke et al. (2004). A tutorial and state-of-the art on telephone call centers is presented in Gans et al. (2003). In a tour scheduling scope survey, Alfares (2004) reviews over 70 papers published between 1990 and 2001, comparing mathematical models and classifying the studies, according to the solution methods adopted, in ten categories: manual solution, IP, implicit modeling, decomposition, goal programming, working set generation, LP-based solution, construction/improvement, metaheuristics and other methods (network-flow models, expert systems, heuristics, etc.). During the period considered in the survey, metaheuristics (mainly simulated annealing) were the most used techniques, followed by constructive/improvement methods, decomposition, manual solution and IP. However, when considering only the second half of the survey period, the trend seems to be more favorable to the use of metaheuristics, IP and manual solutions rather than to the other methods. In an era of technology advances, it is quite surprisingly that manual solutions appear as one of the most popular methods, but the truth is that staff scheduling is still done 22 2.3 Reviewing related works in the literature manually in some activity sectors, like hospital wards, for example. Laporte (1999) suggested the manual design of cyclical schedules, arguing that IP formulations are too rigid to be applicable to real-world problems. In an earlier work, Baker (1976) reviews mathematical programming formulations for the shift and the days-off scheduling problems with cyclic demand patterns. Baker highlights the importance of demand modeling as a crucial stage within the shift and the days-off problems. Although they were typically treated separately, Baker suggests the development of an integrated model for both problems, since they share a common context and a dependency in terms of staff requirements. In the same work, Baker discusses the trend of the researchers to simplify real problems, treating demand in a deterministic way, even when the problem has probabilistic features. Application areas of staff scheduling problems tackled in this survey include mainly service activities as baggage handlers, bus drivers, telephone operators or toll collectors. Considering the complexity of the staff scheduling problem and its variants, it is easy to foresee the difficulty in finding a homogeneous problem classification approach among the several surveys published in the literature. Every author proposes its own definitions scheme, which makes it harder for the comparison of problems and the evaluation of achieved results. In a recent work, De Causmaecker and Vanden Berghe (2011) overcome this gap, proposing a framework for the classification of staff scheduling problems in services. It considers three categories: personnel environment, which includes different types of personnel constraints and skills; work characteristics, which refers to coverage constraints and shift types; and optimisation objectives. Such a classification system allows the benchmarking of problems, the evaluation of the instances in terms of hardness and complexity and also the comparison of solution approaches. 23 Chapter 2. Staff scheduling problems to most of the models. Making use of his wide practical experience, Laporte (1999) argues that cyclical scheduling is more of “an art than a science”, suggesting that in order to get workable solutions, some of the problem’s rules must be violated. Chan et al. (2001) propose a constraint programming approach to solve a cyclic scheduling problem considering an annual planning horizon. In addition to common work rules and legal constraints, annual leaves are also included in this case. Work cycles are not just repeated along the planning horizon, but rather relaxed (extended or shortened) to allow for days-off. The constraints developed in this approach were embedded in a more complete software application that has been successfully implemented in real work context, producing annual schedules for 150 employees. Another constraint programming algorithm is proposed by Laporte and Pesant (2004). Beaumont (1997) uses a multi-objective mixed integer formulation to model the days-off scheduling problem in a long-term planning horizon (47 and 48 weeks cycle). Constraints are imposed on consecutive working and off days and on the weekly mean workload. The objective function is a weighted sum of three components: the preference of employees for long work periods and long breaks, the balance of the workload among employees in a 30day period and the management decision of having a number of employees on duty on each day of the week proportional to the demand on that day. The decision variables defined are binary variables that indicate whether a specific day is a workday or a day-off. This is a simpler problem than the ones considered in our work, since the assignment of shifts to working days and to each employee is not considered. The model was solved with a CPLEX solver. Three schedules were generated for each cycle, considering different goal weights, to be analyzed by the client. Alfares (1998) addresses the days-off scheduling problem with five working 30 2.3 Reviewing related works in the literature days and two days-off cycles. The problem is decomposed in two stages. In a first phase, an expression to calculate the minimum workforce size is determined. In a later phase, that value is included as a constraint in the linear programming model of the problem, which is a relaxation of the IP model, ensuring an optimal integer solution. This approach has the advantage of being applicable to problems with different days-off pattern costs. A decomposition two-phase framework is also developed by Balakrishnan and Wong (1990), who propose a network flow formulation to solve a cyclic scheduling problem with fixed shifts. The optimal solution is found using a shortest path based technique. A novel approach is presented by Hao and Lai (2004), who solve a cyclic scheduling problem for airport ground staff with a neural network methodology. Experiments revealed encouraging results when compared with the solutions obtained by simulated annealing, tabu search and genetic algorithms. Heuristics and metaheuristics based methods have also been used to solve the cyclic scheduling problem, as for example in the work of Mora and Musliu (2004) and Musliu (2006). Mora and Musliu (2004) propose a generic algorithm based methodology while Musliu (2006) explores the tabu-search potentialities to develop and compare a set of heuristic procedures to automatically generate cyclic schedules. In the last mentioned work, Musliu uses a benchmark data set to compare results, which is available in http://www.dbai.tuwien.ac.at/staff/musliu/benchmarks. These examples are used to analyze the performance of our formulation, as will be described in detail in Chapter 8. 31 Chapter 2. Staff scheduling problems 2.4 Summary This chapter introduced the staff scheduling problem: main concepts, features and applications. The aim was not only to provide background on the topic, but also to situate the problems addressed by this research work. An overview of modeling aspects was presented, with emphasis on IP techniques. The related literature was reviewed, focusing on those works that shared features with the problems studied in our work. This analysis revealed an existing trend to develop IP models for specific applications and justified the opportunity to build a general model that could be easily adapted to solve different problems. This model should be flexible to accommodate complex but relevant constraints, such as employee preferences and the equity of the staff schedules. The main challenge was to formulate such a general model using IP techniques and apply it to different real-life problems, solving them to optimality. 32 Chapter 3 Hospitality management This chapter is dedicated to the description of hospitality management as a potential application area of staff scheduling problems. The first section introduces the concept of hospitality and gives an overview on how hospitality management is discussed in the research literature. A reference to the contextualization of hospitality activities in the Portuguese setting is included. Afterwards, some insights on the staff scheduling problem applied to hospitality management operations are presented. Firstly, its main features are pointed out and an attempt to approximate it to applications in other areas that have been already extensively studied in the literature is made. This exercise is followed by a literature review of the related works. To close the chapter, a final outlook on the results of the research work described in this chapter is given. 3.1 Hospitality management Hospitality is not a recent activity. In the social sense of the concept it dates from ancient times, where many societies had traditions of travelers protection and welcoming. King (1995) overviews historical and sociological roots of hospitality and proposes a model emphasizing the importance of 33 Chapter 3. Hospitality management relationships between individuals (hosts, guests/ customers, employees) in any hospitality context, whether it takes place in a private or in a commercial setting. Hospitality and hospitality management have been the scope of many research articles, essentially in the social sciences field, where the discussion has been focused on defining a common, generically accepted, definition and on the development of a framework to be the basis of an independent academic discipline. Although still being often merged with tourism and leisure sector activities, hospitality services are a growing activity sector in a society where customer’s satisfaction and well-being run the market. They usually include hotels, restaurants and other sort of lodging, food and drinks services providers. Due to the specifications of the kind of service provided, hospitality management has to deal with complex variables and constraints. An unpredictable customer demand, a multiskilled workforce, different staff labour contracts’ demands, employees satisfaction and costs minimization are just some of the conditioning issues that an organization has to deal with in order to achieve a flexible, profitable and high quality service provision. A survey undertaken by Enz (2009), in cooperation with the Center for Hospitality Research of Cornell University, identified human resources management as the subject of most concern for hotel managers, above other aspects such as economic or environmental problems, and regardless of the geographical location. The study was based on the statement of 243 experienced hotel executives from six countries. This highlights the importance and worldwide relevance of human resource management to a hospitality organization. Staff scheduling are typical problems to solve within this area. There is however a big lack of published articles focusing on these problems 34 3.1 Hospitality management applied to the hospitality sector, as realized by Ernst et al. (2004a), in opposition to other application areas such as hospitals, transportation or call centers. One of the reasons for the lack of research articles focusing on staff scheduling problems in hospitality is perhaps the lack of a consensual and generically accepted definition of the activity itself. Etymologically, the word hospitality, in Latin hospitalities, has its origin in hospes or hospitis (genitive), which means foreigner or guest. Dictionary definitions include “cordial and generous reception of or disposition toward guests” (“hospitality”, The American Heritage Dictionary of the English Language) and “kindness in welcoming strangers or guests” (“hospitality”, Collins Essential English Dictionary). It is synonym of hospitableness and widely used to define welcoming hostguest relationships, being thus traditionally associated with cultural and social values of each community. In the industrial context, the term hospitality has been adopted mainly in the English-speaking countries to refer to the activity of hotels, restaurants and other sort of lodging, food and drinks services’ providers, whether it takes place in a public/ commercial or in a private/ social context. Lashley (2008) argues that this framework can be understood as an effort to “create a more favorable impression” of these activities, promoting a further hospitable commercial activity and letting the profit provision motivation remain in the background. While British researchers have traditionally based the discussion on this definition, American academics tend to use a broader meaning of hospitality, associating these activities with others under the tourism field, such as travel, leisure or entertainment. In a first essay, hospitality management would then be intuitively defined as the management of those hospitality activities. In accordance, Brotherton and Wood (2008) write that hospitality management is a generically used ex35 Chapter 3. Hospitality management pression to easily replace other labels such as “hotel management”, “restaurant management” or “catering management”, but consequently none or few reflection has been given to the genuine meaning or nature of hospitality. They state that hospitality research has been characterized throughout the years by an unsystematic and scattered analysis, rendering a meaningful synthesis very hard to achieve. In the academic community, researchers have been seeking out the development of the specialist discipline of hospitality management that would embody a theoretical framework and link it to the industry sector, but the lack of a consensual definition of hospitality has effectively been a barrier both to research progress (Jones (1996), Taylor and Edgar (1996)) and to the creation of a robust and mature branch of knowledge. The discussion has been driven by some authors into the field of cultural and social sciences (Brotherton (1999), Hemmington (2007), Jones (2004), Lashley (2008)), incorporating in the debate the importance of studying hospitality from a wider perspective rather than the commercial one. The contribution of authors from different fields of research and their vision’s diversity could potentially be a major value but it could also be understood as a reflex of a fragmented and unstructured hospitality research. King (1995) introduces a hospitality model based on the interaction of social “rituals” in the commercial operation, associated with the process of the guest arrival, welcoming and departure. The author defines hospitality as a host-guest relationship between individuals, taking place in a commercial or private setting, whose success is assessed by the clear perception of the guest needs and their genuine satisfaction by the host. This perspective underlies an unconditional moral duty of hospitable behavior that can, at the edge, merge the meanings of hospitality and hospitableness, which Brotherton (1999) contests, arguing that hospitableness has a much broader scope than hospitality activities. In fact, hospitable concerns are a competitive 36 3.1 Hospitality management advantage in any activity where there is a “service” relationship with the customers, whether it is from the hospitality sector or not. Believing that hospitality is a time evolving phenomenon, i.e, that hospitality’ characteristics change over time, Brotherton (2006) presents a conceptual model for hospitality comprising four dimensions: spatial, behavioral, temporal and physical. These dimensions help to analyze the extent of hospitality in terms of place of occurrence, motivational aspects, time and material features involved. In this conceptual model, the nature, incidence and forms of hospitality in a particular society in any given time period, expressed by domestic or commercial hospitality behavior, are a function of the human and natural resources available, which in turn are conditioned by the economic, socio-cultural, politico-legal and technological conjuncture. The author tried to operationalize this model through case studies (Brotherton and Wood (2008)) in two hotels and later in two fast food restaurants, where guests/customers where asked to participate through an interview, associating words that best fitted their notion of hospitality. Although this exercise did not produce statistically significant results in terms of the influence of social factors (like age, gender, occupancy, etc.), it did provide inputs for understanding guests’ perception of the meaning of hospitality that still needs to be further explored. The comprehensive approach of studying the commercial hospitality activity from a wider social sciences perspective has indeed been quite controversial, as it turned out to happen after the publication of the book “In search of hospitality: theoretical perspectives and debates” by Lashley and Morrison (2000). The referred work presents the nature of hospitality from several views, from Anthropology to Marketing, and proposes an integrated “threedomains approach”: the private, the social and the commercial domains. The main idea of this conceptualization is to consider and evaluate the effect of the social and cultural dimensions of hospitality in the commercial 37 Chapter 3. Hospitality management or business activity, despite their blurred boundaries. The book also defends the existence of hospitality management as an independent activity, apart from any other management activity. Slattery (2002) is one of the researchers who is most critical of this approach, arguing that it overestimates the social side in relation to the economic one and “excludes the hospitality industry context”. His classification model of hospitality industry is based on the place where activities effectively take place: Free-Standing Hospitality Business (hotels, restaurants, bars), Hospitality in Leisure Venues (casinos, cinemas, health clubs), Hospitality in Travel Venues (airports, bus stations, trains, ferries) and Subsidiary Hospitality (workplaces, health care, education). He thus considers that confining hospitality to lodging, food and drinks activities falls short since hospitality necessarily undertakes the management of several other sort of associated leisure activities, in order to respond to the increasing complexity of customer demand. In his review, Jones (2004) identifies five main hospitality schools of thought: science model, management, studies, relationship and systems, attesting that the state of hospitality research is not yet consolidated and there is a lack of consensus concerning its definition. Even though this diversity of thoughts persists, the management perspective was recognized to be in a dominant position in relation to other emerging views. But even from a management point of view the author finds three different approaches, with their main divergence in the focus of the research. While the traditional point of view considers hospitality to be a sub-discipline inside the main management disciplines, a different conviction uses hospitality as an application of the main discipline and a third perspective assumes a “multidisciplinary approach” studying hospitality from several different main management subjects. 38 3.1 Hospitality management In a recent article, Ottenbacher et al. (2009) analyze the pedagogical and research implications of defining the hospitality discipline. Based on a services marketing perspective, the authors defend a taxonomical classification, considering hospitality as a field supported by the economic output of a group of six related industries: lodging, food services, leisure, travel, attractions and conventions. Each of these independent industries takes, in turn, “input from hospitality either directly or indirectly for its survival and success.” The article suggests the need of exploring separately each one of these activities, which are often ignored in the literature, recognizing the diversity of their constitutive market segments. In the Portuguese context a translation for the concepts of hospitality or hospitality management is still missing and consequently there is not a consolidated research activity focused in this thematic area, or at least with an acknowledged published work. A few exceptions include for instance the work on hotel management efficiency using Data Envelopment Analysis (Barros and Mascarenhas (2005), Barros et al. (2008)). A hospitality association was created - Hospitality Management Institute (HMI (2008)), as a result of the cooperation between Turismo de Portugal, ISCTE (Instituto Superior de Ciˆencias do Trabalho e da Empresa), Universidade do Algarve and ESHTE (Escola Superior de Hotelaria e Turismo do Estoril), sponsored by the Portuguese Government and the National Strategic Council for Education and Training in Tourism, that aims to promote advanced management training and to support applied research in tourism. Portuguese hotel and restaurant industries have traditionally been considered as a part of the tourism sector, for statistics, economic indicators and sectorial strategies, as well as several other service providers connected to touristic services, such as travel agencies, touristic operators or leisure activities promotors. There are many different associations: Portuguese Ho39 Chapter 3. Hospitality management to understand and satisfy their needs. The staff must be motivated and engaged. Staff scheduling systems shall therefore account for the workforce well-fare, considering employees’ preferences in terms of work and rest days, weekends off and holidays, shifts assignment, shifts change, shifts starting and finishing times flexibility, compatibility or incompatibility with other staff elements, etc. Possible approaches to the staff scheduling and rostering problem in hospitality management, or its sub-problems, may be inspired by the work that has been comprehensively done both in tour scheduling and nurse rostering. As exposed before in this chapter, nurse rostering and hospitality are two activity areas with many similarities concerning rostering issues. Examples of the few divergences between them include the seasonality, the weekly and daily cycles operation inherent to hospitality activities, that contrast with the Winter/Summer seasonal workload distribution of hospitals. Thompson (1999a) gives a very important contribution to staff scheduling and rostering in hospitality management. It should have triggered the interest of researchers in this area, namely in the development of quantitative approaches, but the truth is that it didn’t, according to the latest reviews on this subject that have been analyzed. This work aims to be a recall, as there is still a lot to be done. Future work may be based on the adaptation of tour scheduling, nurse rostering or even shift scheduling models and solution methods to hospitality operations. Schedules should be flexible enough to be easily adaptable to actual workplace environments changes and social aspects should be considered. 46 Chapter 4 General Model This chapter presents the model developed for a general staff scheduling problem. A set of features, which are relevant and common to many variants of the problem are considered. Those are described in Section 4.1. Next, Section 4.2 introduces and explains the proposed IP formulation. Finally, in Section 4.3 we highlight some special features of the model that, to the best of our knowledge, represent a novel and valid contribution to this field of research. 4.1 Problem description The general model was developed for the staff scheduling problem of an organization that works continuously, 24 hours a day. The day is divided in nS working shifts. The model considers a set of nT teams of homogeneous (single skilled and full-time) employees, that must be assigned to either a work or a break shift, in each of the nD planning period days. Daily shift demand levels must be satisfied, meaning that the model must guarantee a required number of teams working in each shift on each day. Work rules include a minimum and a maximum number of consecutive working days for each team, as well as a predefined sequence of working shifts to be respected. 47 Chapter 4. General Model Each shift change must have a break or non-working day in between. The objective is to minimize and to level the number of days each team works in each shift, in order to balance the workload. 4.2 Mathematical model The following notation was defined: Indices d∈ {1, . . . , nD}, day; t∈ {1, . . . , nT}, team; s∈ {1, . . . , nS}, working shift; s0∈ {1,...,2×nS}, extended shift. Shifts s00 ∈ {nS + 1,...,2×nS}are non-working shifts that carry the information on the last working shift of the team; n(s0) is the extended shift that follows the extended shift s0in a given sequence; For example, considering 3 working shifts {1,2,3}and 3 non-working shifts {4,5,6}a possible sequence could be 1-4-2-5-3-6-1-4-..., as defined in Table 4.1. s0123456 n(s0)456231 Table 4.1: Example of a possible sequence of shifts 48 4.2 Mathematical model The indices tand dshould take values in a circular list. The list for index d should for instance be {1, . . . , nD −1, nD, 1, . . . , nD −1, nD, . . .}. For implementation purposes index dshould be replaced by [(d−1) mod (nD)]+1 and index tshould be replaced by [(t−1) mod (nT)] + 1. Parameters nT number of teams; nS number of shifts; nD number of days in the planning period; demandsdaily demand for each working shift s; maxD maximum number of consecutive working days; minD minimum number of consecutive working days. Decision variables xts0d=   1 if team tis assigned to shift s0on day d 0 otherwise Decision variables (auxiliary) btdm =          1 if team tworks at least minD consecutive days, starting on day d+m−1 0 otherwise Objective function min max ts X d xtsd (4.1) 49 Chapter 4. General Model Linearized objective function min Z(4.2) Constraints ∀ts X d xtsd −Z≤0 (4.3) ∀td X s0 xts0d= 1 (4.4) ∀sd X t xtsd ≥demands(4.5) ∀td maxD X q=0 X s xts(d+q)≤maxD (4.6) ∀td minD X m=1 btdm −X s xts(d+minD−1) ≥0 (4.7) ∀td ∀minD m=1 X s m+minD−1 X q=m xts(d+q−1) −minD ×btdm ≥0 (4.8) ∀ts0dxts0d−xts0(d+1) −xtn(s0)(d+1) ≤0 (4.9) ∀ts0dm xts0d, btdm ∈ {0,1}(4.10) The objective function seeks the minimization of the maximum number of days that a team works in each shift. It levels the working days of each team, leading to a solution in which each team works the same number of days in each shift. The linearization of (4.1) results in the linear objective function expressed in (4.2), where Zrepresents the maximum number of days that a team works in each shift, and also in Equations 4.3. Equations (4.4) state that each day every team has exactly one shift assigned, either a working shift or a break shift. 50 4.2 Mathematical model Equations (4.5) are coverage constraints, making sure that each shift daily requirements are fulfilled. Equations (4.6) ensure that no team works more than maxD consecutive days. For each day da window of length maxD + 1 is opened and at least one of the corresponding xtsd must be 0, independently of the working shift 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 t!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! Figure 4.1: Illustration of Eqs. (4.6) Equations (4.7) and (4.8) guarantee that each team works at least minD consecutive working days. The second term on the left-hand-side of Eq. (4.7) sums up the working days xts(d+minD−1) within a window of width minD, starting at d. If all xts(d+minD−1) are zero no constraint is imposed to the variables btdm. However, if at least one xts(d+minD−1) = 1 then at least one of the variables btdm must be equal to 1. When the variable btdm equals zero, the corresponding Eq. (4.8) is fulfilled. However if Eq. (4.7) imposes that a variable btdm equals one, then the first term on the left-handside of Eq. (4.8) has to sum-up at least minD, i.e. the team has to work at least minD consecutive days. The meaning of mis that if a team works one day within a window of width minD, then it has to work at least minD consecutive days, starting at m= 1 or m= 2 or . . . or at m=minD. Figure 4.2 illustrates this process for shift M. Equations (4.9) ensure that the required shift sequence is followed. The basic sequencing requirement is defined over the working shifts that follow the sequence: 1,2,3,1. . ., but, as there are breaks between the working shifts, the breaks must carry the memory of the last working shift. This is 51 Chapter 4. General Model Days! Team t!M" M" M" M" d! m=1!m=2!m=minD! minD! minD! minD! btd1=1! btd2=1!btdminD=1! M" Figure 4.2: Illustration of Eqs. (4.7) and (4.8) obtained through the “extended shift” s0. For instance, if a team has an extended shift s0= 4 assigned, it means that the team is having a breaking shift after a working shift 1. If the same shift is assigned on days dand d+1, then the corresponding Eq. (4.9) is satisfied independently of the value of xtn(s0)(d+1). However if the shift ends, i.e., a different shift is assigned on days dand d+ 1, then the next possible shift is imposed by the vector of indices n(s0) and the Eq. (4.9). Figure 4.3 illustrates the application of Eqs. (4.9) for the sequence of shifts defined in the example of Table 4.1. Days!1!2!3!4!5!6!7!8! Team t!M" M" B" A" B" N" B" B" Days!1!2!3!4!5!6!7!8! Team t!1" 1" 4" 2" 5" 3" 6" 6" Figure 4.3: Illustration of Eqs. (4.9) 52 4.3 Special features 4.3 Special features Emphasis must be given to the wide scope and flexibility introduced with the formulation of the sequence shift restriction (Eqs. 4.9). Any desired sequence pattern of working shifts and days-off can be imposed through the proper definition of the vector of indices n(s0). The limits on the maximum and minimum number of consecutive days for each shift enable the distinction between the length of the working and rest periods, but also between the work shifts’ length itself. Some activities have work rules that impose different maximum allowable numbers of consecutive working shifts, for instance night vs day shifts. But those parameters, together with the shift sequence constraints, also allow to control the periodicity of days-off, as well as the length of the tour or sub-period or sub-cycle of the planning horizon. It is possible to impose a schedule with sub-cycles of equal length (if it is a divisor of the planning period) or give the model flexibility to construct sub-cycles with different lengths. The flexible application of these features is demonstrated in the case studies that are described in the next chapters. 53 Chapter 4. General Model 54 Chapter 5 Application of the general model to a glass production unit The general model presented in Chapter 4 was first adapted to the reallife problem of a glass industry. This chapter describes that experience and is organized as follows. Section 5.1 introduces the facility, the work environment and the features of this particular problem. Then, in Section 5.2 the adjustments that were made to the general model are described, followed by the achieved computational results, which are indicated in Section 5.3. An illustration of the developed solutions is shown in Section 5.4. Section 5.5 sums up the contents of this chapter, emphasizing some important outcomes of the work that was carried out. 5.1 Problem description The facility produces glass bottles using two furnaces, with four lines each. The workforce was distributed in 4 teams but the management wanted to test the scenario of having a higher number of teams. They were convinced this change would increase the scheduling flexibility and provide a more 55 Chapter 5. Application of the general model to a glass production unit part of the constraints, as well as some quality indicators of the solution. 5.5 Conclusions This chapter described the application of the general IP model to the real-life problem of a glass production unit. The main adjustment was the introduction of the offset constraints (Eqs. 5.2), which ensure the workload balance between the teams and allow for a reduction in the overall number of the remaining constraints, improving the model’s performance. A new sequence of shifts and days-off was imposed, by simply defining a corresponding vector of indices n(s0). This demonstrates the flexibility of the approach developed for the sequence constraints. Experiments focused on the evaluation of different optimal solutions achieved for different planning periods and allowed for the selection of those that better suited the company’s goals, namely in terms of holiday distribution along the year. An integrated long-term scheduling solution was proposed, through the replication of two different planning periods, one for the winter months and another for the summer period. Computational times revealed the high efficiency of the model for this particular application, which was embedded in a more complex decision support system to be used for the glass industry management. 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/fev/10 2/fev/10 3/fev/10 4/fev/10 5/fev/10 6/fev/10 7/fev/10 8/fev/10 9/fev/10 10/fev/10 11/fev/10 12/fev/10 13/fev/10 14/fev/10 15/fev/10 16/fev/10 17/fev/10 18/fev/10 19/fev/10 20/fev/10 21/fev/10 22/fev/10 23/fev/10 24/fev/10 25/fev/10 26/fev/10 27/fev/10 28/fev/10 1/mar/10 2/mar/10 3/mar/10 4/mar/10 5/mar/10 6/mar/10 7/mar/10 8/mar/10 9/mar/10 10/mar/10 11/mar/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/mar/10 13/mar/10 14/mar/10 15/mar/10 16/mar/10 17/mar/10 18/mar/10 19/mar/10 20/mar/10 21/mar/10 22/mar/10 23/mar/10 24/mar/10 25/mar/10 26/mar/10 27/mar/10 28/mar/10 29/mar/10 30/mar/10 31/mar/10 1/abr/10 2/abr/10 3/abr/10 4/abr/10 5/abr/10 6/abr/10 7/abr/10 8/abr/10 9/abr/10 10/abr/10 11/abr/10 12/abr/10 13/abr/10 14/abr/10 15/abr/10 16/abr/10 17/abr/10 18/abr/10 19/abr/10 20/abr/10 21/abr/10 22/abr/10 23/abr/10 24/abr/10 25/abr/10 26/abr/10 27/abr/10 28/abr/10 29/abr/10 30/abr/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/set/10 2/set/10 3/set/10 4/set/10 5/set/10 6/set/10 7/set/10 8/set/10 9/set/10 10/set/10 11/set/10 12/set/10 13/set/10 14/set/10 15/set/10 16/set/10 17/set/10 18/set/10 19/set/10 20/set/10 21/set/10 22/set/10 23/set/10 24/set/10 25/set/10 26/set/10 27/set/10 28/set/10 29/set/10 30/set/10 1/out/10 2/out/10 3/out/10 4/out/10 5/out/10 6/out/10 7/out/10 T1 # # ! ! ! ! " " " " # # # # ! ! ! ! " " " " # # # # ! ! ! ! " " " " !###!!!!! ! ! """ !####!! ! 18 15 17 T2 " " " " # # # # ! ! ! ! " " " " # # # # ! ! ! ! " " " " !###!!!!! ! ! """!!!! 12 15 11 T3 " # # # # ! ! ! ! # ! ! ! ! " " " " # # # # !!!! ! ! """" !###!!!!! ! ! 15 9 12 T4 ! ! ! " " " " # # # # ! ! ! ! " " " " # # # !!!!####!!!! ! ! """" !### 10 12 14 T5 " " " " # # # # ! ! ! ! " " " " # # # # ! ! ! ! " " " " # # # # ! ! ! ! ! ! """ !!!!####!!!! ! ! """" 15 19 16 8/out/10 9/out/10 10/out/10 11/out/10 12/out/10 13/out/10 14/out/10 15/out/10 16/out/10 17/out/10 18/out/10 19/out/10 20/out/10 21/out/10 22/out/10 23/out/10 24/out/10 25/out/10 26/out/10 27/out/10 28/out/10 29/out/10 30/out/10 31/out/10 1/nov/10 2/nov/10 3/nov/10 4/nov/10 5/nov/10 6/nov/10 7/nov/10 8/nov/10 9/nov/10 10/nov/10 11/nov/10 12/nov/10 13/nov/10 14/nov/10 15/nov/10 16/nov/10 17/nov/10 18/nov/10 19/nov/10 20/nov/10 21/nov/10 22/nov/10 23/nov/10 24/nov/10 25/nov/10 26/nov/10 27/nov/10 28/nov/10 29/nov/10 30/nov/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 Figure 5.4: Annual schedule for the glass production unit 63 Chapter 5. Application of the general model to a glass production unit 64 Chapter 6 Application of the general model to a continuous care unit The general model described in Chapter 4 was in a second phase adapted to the real-world problem of a continuous care unit. This chapter presents that work and is organized as follows. Section 6.1 introduces the service type, the work environment and the features of this particular problem. Then, in Section 6.2 the adjustments that were made to the general model are explained, followed by the achieved computational results, which are presented in Section 6.3. A proposed solution is shown in Section 6.4. Section 6.5 resumes this chapter, highlighting some important outcomes of the developed research work. 6.1 Problem description The organization provides private lodging and nursing home services, directed mainly to the elderly. This work addresses the scheduling of only part of the workforce that is composed by care takers, which are employees with no specific qualifications that are responsible for the daily basic needs 65 Chapter 6. Application of the general model to a continuous care unit of the guests/patients, such as personal hygiene. The unit works continuously, around the clock, 24h a day, in a multi-shift working scheme: M - morning (from 8:00 a.m. to 2:00 p.m.), A - afternoon (from 2:00 p.m. to 8:00 p.m.), N - night (from 8:00 p.m. to 0:00 a.m.) and D - after-night (from 0:00 a.m. to 8:00 a.m.). In opposition to the previous case study, the demand is now different for each shift and the maximum and minimum number of consecutive working (or rest) days is now indexed to each shift. Again, no daily meal breaks are considered, as well as weekends-off restrictions. Employees’ preferred sequence of shifts and breaks (B) must be assured (M-A-N-D-B) and preference is given to a balanced schedule between employees. The workforce is considered single skilled but is now heterogeneous in terms of contract types. It combines a fixed workforce of 49 full-time, permanent, employees with a variable pool of part-time workers. The objective of the model is to minimize the parttime requirements, assuming that full-time contracted hours must be as fully assigned as possible. Part-time workers are not subject to any constraints. 6.2 Mathematical model In order to adapt the general model to this new problem, the following adjustments were made. Indices n(s0) is the extended shift that follows the extended shift s0in a given sequence; Considering 4 working shifts {1,2,3,4}and 1 non-working shift {5} the new sequence M-A-N-D-B is now defined as shown in Table 6.1. 66 6.2 Mathematical model s012345 n(s0)23451 Table 6.1: Sequence of shifts for the continuous care unit maxDs0maximum number of consecutive working (shifts 1 to 4) and rest (shift 5) days for each shift; minDs0minimum number of consecutive working (shifts 1 to 4) and rest (shift 5) days for each shift; ptCostshourly cost of a part-time employee working in shift s; hsnumber of working hours of shift s. Parameters δD offset between the working cycles of the teams (in number of days). Objective function Minimization of the cost with part-time work. min PdPsptCosts×hs×(demands−Ptxtsd) (6.1) Constraints ∀sd X t xtsd ≤demands(6.2) Equations (6.2) state that each day, the number of full-time employees assigned to every working shift is less than or equal to the demand. The difference between the assigned and the demanded work will be assured by part-time workers. The cyclic approach introduced in Chapter 5 was also adopted in this formulation. Therefore, the model constraints include Eqs. (5.2), (5.3), (5.4), 67 Chapter 6. Application of the general model to a continuous care unit (5.5) and (5.6). See Section 5.2 for a detailed description of each one of the equations. Equations (5.3), (5.4), (5.5) were adjusted to consider extended shifts, which implied the replacement of the parameters maxD and minD by the indexed parameters maxDs0and minDs0. These represent minor adjustments, but in order to allow for an easier reading the new Eqs. (6.3), (6.4) and (6.5) are presented next. ∀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 Computational experiments The model was coded in OPL Studio version 6.3 and solved using the CPLEX 12.1.0 solver on a server machine powered by 2 Intel R Xeon R processors of 2,4 GHz and 1,39 GHz, and with 2 GB RAM. The number of employees (nT) is 49 and the working shifts (nS) are now 4. The daily shift demand (demands) is 20 M, 17 A, 11 N and 11 D. Tests were conducted for planning periods of 25, 28 and 30 days, considering different combinations of the parameters minDs0,maxDs0and ptCosts. The choice of the values of these parameters took into account the desired length of the sub-periods, the assurance of the minimum of one day-off every 7 days, and also that the working hours assigned to each employee should fall below 160h in a 30day period in order to respect labor contracts. The reasoning made in the previous case study, concerning the value of the offset parameter, does not make sense in this problem, since the planning period is now shorter than the number of employees. Therefore, the offset was set to 1, as it achieved satisfactory results. 68 6.3 Computational experiments In terms of dimension, the number of decision variables of this problem varies between 6125 for nD=25 and 7350 for nD=30 and the number of constraints reaches the maximum of 8250 for nD=30 and maxD1=maxD2 = 3, maxD3=maxD4=maxD5= 1. Table 6.2 reports the computational results for a set of different values of input parameters. The column ”solution pattern” contains the schedule for one employee for the whole planning period considered, as illustrated in the next examples. Figures 6.1 and 6.2 show the schedule for E1 in a nD = 25 days scenario. !" # $ % & ' ( ) * + #, ## #$ #% #& #' #( #) #* #+ $, $# $$ $% $& $' -# . . / / 0 " 1. . / / 0 " 1. . / 0 " 1. / 0 " 1 Figure 6.1: Schedule of E1 for nD=25 days; maxD1=maxD2= 2 and maxD3=maxD4=maxD5= 1; minD1=minD2=minD3=minD4= minD5= 1; ptCost1=ptCost2=ptCost3=ptCost4= 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 Figure 6.2: Schedule of E1 for nD=25 days; maxD1=maxD2=maxD3 =maxD4=maxD5= 1; minD1=minD2=minD3=minD4=minD5 = 1; ptCost1=ptCost2=ptCost3=ptCost4= 1. The ability to control the solution pattern with the variation of input parameters is noticeable. For this scenario, for example, it is possible to get a balanced solution, with sub-periods of equal length, with a reduction of maxDs0, forcing the model to assign exactly 1 day to each shift. In this solution the number of sub-periods increases from 4 in Fig. 6.1 to 5 in Fig. 6.2, meaning that the number of breaks or days-off of full-time employees will also increase, as well as the requirements for part-time service (higher/poorer solution value). The results of the tuning of maxDs0and minDs0can also be checked for a 30 days planning horizon. In this case, fixing to 2 the minimum number 69 Chapter 6. Application of the general model to a continuous care unit nD maxDsminDsptCostsSolution Pattern PT Req. s = M A N D B s = M A N D B s = M A N D (sub-periods) (hours) 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 computational parameters and results for the continuous care unit 70 6.3 Computational experiments of consecutive days of shift M, results in a balanced solution but with the same number of sub-periods and, therefore, with the same solution value. Figures 6.3 and 6.4 illustrate this 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 Figure 6.3: Schedule of E1 for nD=30 days; maxD2=maxD2= 2 and maxD3=maxD4=maxD5= 1; minD1=minD2=minD3=minD4= minD5= 1; ptCost1=ptCost2=ptCost3=ptCost4= 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 Figure 6.4: Schedule of E1 for nD=30 days; maxD1= 2 and maxD2= maxD3=maxD4=maxD5= 1; minD1= 2 and minD2=minD3= minD4=minD5= 1; ptCost1=ptCost2=ptCost3=ptCost4= 1. The influence of the ptCostsparameter can be verified in the 28 days planning horizon case. The increase from 1 (Fig. 6.5) to 3 (Fig. 6.6) units, results in a higher number of sub-periods and therefore, in a higher number of days-off of full time employees and higher part-time needs, leading to a worse solution. !" # $ % & ' ( ) * + #, ## #$ #% #& #' #( #) #* #+ $, $# $$ $% $& $' $( $) $* -# . . / / 0 " 1. . / / 0 " 1. . / / 0 " 1. . / / 0 " 1 Figure 6.5: Schedule of E1 for nD=28 days; maxD1=maxD2= 2 and maxD3=maxD4=maxD5= 1; minD1=minD2=minD3=minD4= minD5= 1; ptCost1=ptCost2=ptCost3=ptCost4= 1. The same happens in the nD=30 case, where an increase from 1 (Fig. 6.7) to 1000 (Fig. 6.8), in the hourly cost of the part-time night and after-night shifts, achieves a solution with 2 additional sub-periods, which means more part-time requirements and consequently a worse solution value. In terms of execution times, each run took less than 4 seconds. 71 Chapter 7. Application of the general model to a hospital min Pt|[(ht−at)−PsPd(ps×xtsd)]|(7.1) Constraints ∀sd Ptxtsd ≥dMinsd (7.2) ∀sd Ptxtsd ≤dMaxsd (7.3) Equations (7.2) and (7.3) state that each day, the required number of working nurses for each shift is ensured. ∀td Pw−1 i=0 P5 s0=4 xts0(d+i)≥2 (7.4) Equation (7.4) imposes a minimum of two non-working days (D or B) in each window w. The cyclic approach introduced in Chapter 5 was once more adopted. The model constraints include Eqs. (5.2), (5.3), (5.4), (5.5) and (5.6). See Section 5.2 for a detailed description. Equations (5.3), (5.4), (5.5) were adjusted to consider the indexed parameters maxDks0and minDks0. These parameters can be set to different values in order to evaluate different patterns for the sequence of shifts of the different types of contracts. These represent minor adjustments, but in order to allow for an easier reading the new Eqs. (7.5), (7.6) and (7.7) are presented next. ∀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 Computational experiments and solutions The scheduling constraints that ensure a maximum of 6 consecutive work days for each nurse are imposed by the tuning of the parameters maxDks0 and minDks0. 7.3 Computational experiments and solutions The model was coded in OPL Studio version 6.3 and solved using the CPLEX 12.1.0 solver on a server machine powered by 2 Intel R Xeon R processors of 2,4 GHz and 1,39 GHz, and with 2 GB RAM. In this problem the workforce is composed by 42 nurses with different contract types. For implementation purposes, the 42 nurses were divided in 5 groups, as shown in Fig. 7.4. tType of contract 1. . . 5 1 6. . . 36 2 37. . . 38 3 39. . . 40 4 41. . . 42 5 Table 7.4: Association of index tto the type of contract Since each type of contract is linked to a number of contracted hours, each nurse is thus initially connected to a number of contracted hours per planning period. This approach led to a lower number of decision variables than the alternative of indexing each decision variable to a nurse. In opposition to the previous case studies, as there are nurses with different contracted hours, it was not reasonable to impose the same offset to all the schedules. Therefore, each group of nurses of the same type had its own offset. In terms of size, this model dealt with 5880 decision variables and 952 constraints. Just to give an idea of the influence of the offset constraints in the simplification of the model, if these constraints were not considered the overall number of 79 Chapter 7. Application of the general model to a hospital constraints would be 37 times higher, increasing from 952 to 35392. Figure 7.1 shows a solution obtained for this case study in 1170.9 seconds (20 minutes). In this case, maxDks0= 5 for k=1,. . . ,5 and s0=1,. . . ,4; maxD15 =maxD25 = 5 and maxD35 =maxD45 =maxD55 = 7; minDks0= 1, for k=1,. . . ,5 and s0=1,. . . ,5. The formulation of the parameters maxDks0and minDks0allows us to control the relation between the number of work and rest days for each type of nurse. In this case, it makes sense to allow for more breaks for those nurse types that have less contracted work hours (maxD35 =maxD45 = maxD55 = 7). This solution does not consider planned absences or holidays. Although this constraint has not been treated in the previous applications of the IP model, we decided to introduce it in the hospital case study since it was addressed in the solution proposed in the original work of Antunes and Moz (2011) and, therefore, it makes the comparison between approaches easier and more realistic. In order to consider this scenario, the decision variables corresponding to each planned day-off were initially set to 0 and the offset constraints could not be applied to the teams that had planned days-off. Sequence and maximum/minimum consecutive days constraints were also adjusted individually for each of those teams in order to exclude the days-off. Figure 7.2 shows the solution obtained when considering the planned daysoff for this particular month. As expected, the execution time increased, as the model gets more constrained, and it takes now 2256.3 seconds (about 38 minutes) to obtain this solution. 80 7.3 Computational experiments and solutions !"#$%&'( )) *) +) ,) -) )* ** +* ,* -* .* /* 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' Figure 7.1: Schedule for the hospital case study without planned absences 81 Chapter 7. Application of the general model to a hospital In both solutions, the deviation between assigned and contracted hours transferred from the previous month was set from real data. Column “Deviation” data refers only to the present month’s deviation and column “Current balance” shows the actual deviation balance after the present month’s assignment. We consider this last column in order to compare our IP solution with the one achieved by Antunes and Moz (2011) and also with the real schedule that was made by hand by the head nurse of the hospital. We will name them IP, Antunes and Real solutions respectively. Table 7.5 shows some statistical data for the deviation balance in the three solutions. Deviation balance Solutions (hours) IP Antunes Real Maximum 13.8 8 19.4 Median 4.7 4.8 5.5 Average 4.8 4.7 5.8 Table 7.5: Statistic analysis of the solutions The mathematical model proposed by Antunes and Moz (2011) limits the maximum deviation balance of each nurse to 8 hours. In the Antunes solution, this value is reached in the schedules of two of the nurses. In the Real solution this 8 hours-value is exceeded in 12 situations, which corresponds to approximately 29% of the workforce, and the maximum deviation is 19.4 hours. In our IP solution, there are 8 nurses (19%) with a deviation balance above 8 hours, but the maximum value is 13.8. Nevertheless, the IP solution obtains a deviation below 4 hours for 45% of the nurses, against 31% of the Antunes solution and 43% of the Real solution. Although the average and the median values are not very distant, the fact is that high deviations are harder to manage and should be avoided. In our approach, we had to make a trade-off between the resolution time and the minimization of the sum of 82 7.3 Computational experiments and solutions !"#$%&'( )) *) +) ,) -) )* ** +* ,* -* .* /* 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' Figure 7.2: Schedule for the hospital case study considering planned absences 83 Chapter 7. Application of the general model to a hospital these deviations (translated by the objective function). In order to get an optimal solution in a reasonable time, a lower bound to the objective function was imposed. After testing several values, the best compromise was found for the solution of Fig. 7.2, with an objective function of 200. The limits on the daily shift requirements dMaxDsd and dMinDsd have also a significant influence on the model’s performance. The closer to real data these parameters are set, the tighter the model gets and the longer it takes to reach a solution. In our approach, only the dMinDsd real data was imposed. The limits on dMaxDsd had to be relaxed in order to get a solution in a reasonable amount of time. Looking again into the solution of Fig. 7.2, the information on the daily assigned hours can be checked in the rows below the schedule, for each one of the working shifts. A comparison of these figures with the initial demand requirements proves that the minimum daily requirements are satisfied, whereas the maximum limits are violated in 6 different days: one extra morning shift on day 6, one extra afternoon shift on days 10, 13, 14 and 17, and two afternoon shifts in excess on day 27. This drawback does not seem very representative when we look at the real solution, where the number of similar violations is much higher, reaching 23 situations, mostly affecting the afternoon and night shifts. Nevertheless, we do not have enough information to evaluate the impact of these violations in the real setting. 7.4 Conclusions This chapter described the application of the general IP model to the problem of nurse scheduling in a Portuguese hospital (Antunes and Moz (2011)). This problem differs from the others already described in the previous two chapters (Chapters 5 and 6) in two main features: the workforce composition and the objective. The workforce is now composed of 5 groups of 84 7.4 Conclusions nurses, which are grouped according to their contract types. The objective is to minimize the gap between assigned and contracted hours. The cyclic approach introduced in Chapter 5 was adopted in order to ensure a balanced solution within each group of nurses. Demand constraints (Eqs. 4.5, 7.2 and 7.3) were adapted in order to consider minimum and maximum daily requirements for each shift. Equations (5.3), (5.4) and (5.5) to each contract type (index k) made it possible to impose different limits on the number of consecutive working/rest days to each group of nurses. In this problem, it was more reasonable to allow the groups with less contracted hours to have more days-off assignments than the others. A new sequence of shifts and days-off that met the preferences of the nurses was imposed, by simply defining a new vector of indices n(s0). Although it was not considered in this problem, we could define different sequence patterns to each group of nurses by simply indexing the sequence constraints (Eqs. 5.6) to each type of contract. This example illustrates the flexibility and potential of the proposed formulation. Experiments focused on finding a trade-off between the value of the optimal solution and the computational time. In order to compare our solution with the one proposed by Antunes and Moz (2011) and the real solution manually developed by the head nurse of the hospital, we adjusted the model to consider the absences planned for the present month. An optimal solution was built in 38 minutes, considerably more than the 0.38 seconds taken by the optimal solution proposed by Antunes and Moz (2011), which was specifically tailored to this problem, but much less than the 8 hours the head nurse needed to develop it by hand. Results are encouraging, demonstrating that our formulation can also accommodate restrictions on planned absences, such as holiday or training. 85 Chapter 7. Application of the general model to a hospital 86 Chapter 8 Benchmark instances In order to evaluate the flexibility and wide scope of the developed formulation and to compare results with other approaches, experiments were carried out on a collection of 20 rotating workforce scheduling problems available in http://www.dbai.tuwien.ac.at/staff/musliu/benchmarks and presented in Musliu (2006). This chapter describes the application of the general model introduced in Chapter 4 to those benchmark problems. Section 8.1 presents the features of the problems. Next, the adjustments that were made to the general formulation are explained in Section 8.2, giving special attention to the sequence constraints adaptation. Section 8.3 shows the computational results and a comparison with other methods. Solutions are discussed in Section 8.4, followed by some concluding remarks that end the chapter. 8.1 Problem description In these instances, the number of employees vary from 7 to 163. The number of standard shifts is either 2 (day and afternoon) or 3 (day, afternoon and night). The length of working and days-off blocks is now limited by a minimum and a maximum number of consecutive days, as well as the length of each sequence of days assigned to the same shift. In the previous case 87 Chapter 8. Benchmark instances 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: Computational times for the benchmarking instances using the IP model, MC-T and FCS 94 Chapter 9 Heuristic approach An optimization approach is typically limited in terms of performance for real-life large dimension problems. The challenge of developing a heuristic procedure naturally arose as a means of systematically overcoming that handicap and to compare results. In this chapter we propose a constructive heuristic to solve the problem of the glass unit addressed in Chapter 5. Section 9.1 describes the heuristic procedure, explaining the initial assumptions and the developed algorithms. Computational results for the glass unit problem are shown in Section 9.2 and a comparison of the performance of both approaches, heuristic and optimization, is carried out. In order to analyze the consistency of the heuristic, a set of computer generated instances was also used, varying in size with the number of teams and the number of shifts. The solutions generated for the glass unit problem are presented in Section 9.2. Section 9.3 draws some conclusions and reflexions for future extensions of this work. 95 Chapter 9. Heuristic approach 9.1 Heuristic 9.1.1 Initial assumptions From our previous experience with the optimization model, described in Chapter 5, we realized that a key issue that guarantees the existence of feasible solutions is the availability of a sufficient number of breaks, to allow for an adequate sequence of working days and days-off for each team. This break availability condition is on the basis of the proposed heuristic. When the condition is valid, for a set of input parameters, the heuristic defines a feasible schedule for the first team, which will be afterwards replicated for the remaining teams, with a time lag or offset days in between. In the development of the first team’s schedule, working-day blocks are assigned following the sequence of the shifts in which the teams must work. The length of the working blocks is limited by the minimum and maximum numbers of allowable consecutive working days. It may occur, therefore, that all working blocks have the same length, i.e. the same number of consecutive days, or that blocks have different lengths. Between each two consecutive working blocks, i.e., between each change of working shifts, there must be at least one break day. The heuristic assures that blocks of working days plus breaks have always the same length. Therefore, in the case of a schedule with working-day blocks with different lengths, more than one break is assigned after the working blocks with shorter lengths, in order to have a block of working days plus breaks with the same length as the block with the maximum length plus one break. The heuristic tests different combinations of working blocks until a feasible solution is reached. These procedures are next explained in detail. 96 9.1 Heuristic 9.1.2 Algorithm 1 - checkAvailableBreaks The first step of the heuristic is the verification of the available breaks condition, described in Algorithm 1 - checkAvailableBreaks, where: nD is the number of days in the planning period; nT is the number of teams; nS is the number of working shifts; minD is the minimum required number of consecutive working days; maxD is the maximum allowed number of consecutive working days; wdis the number of working days of the planning period to be assigned to each team, for each shift; nblocks is the number of blocks of working days, for each team and for each shift; maxBlock is the block of working days with the maximum length to be considered; Ftot is the total number of available breaks in the planning period, for each team; Fmin is the minimum number of required breaks in the planning period, for each team, considering the required number of working-day blocks. The algorithm first calculates the values for Ftot and wd. If, in each day, there are 3 shifts to be assigned to exactly 3 teams, the remaining 2 teams are necessarily assigned to breaks. So, 2 breaks are available in each day. These 2 breaks multiplied by the number of days in the planning period (nD) and divided by the number of teams (nT) result in the total number of available 97 Chapter 9. Heuristic approach Algorithm 1 checkAvailableBreaks Ftot ←nD ∗(nT −nS)/nT wd←(nD −Ftot)/nS for i= 0 →(minD +i)do if wdis a multiple of (minD +i)then nblocks ←wd/(minD +i) Fmin ←nblocks ∗nS if Fmin ≤Ftot then solutionExists maxBlock ←(minD +i) equalBlocks Exit end if end if end for testBlocksCombination() if solutionExists then Exit else noFeasibleSolutionAssured Exit end if breaks per team, Ftot. This figure represents the maximum number of breaks the procedure has available to assign to each team, and must be enough to ensure the mandatory minimum number of breaks to assign between shift changes. Taking Ftot out of nD and dividing it by the number of shifts (nS) we get the number of working days, in each shift, to assign to each team, wd. Figures 9.1, 9.2 and 9.3 illustrate the reasoning of these calculations for nD = 20 days, breaks are represented by the blank cells. Algorithm 1 proceeds by checking the possibility of assigning only working blocks with equal length: (minD +i). Looking into the same example of nD = 20 days, with minD = 2 days and maxD = 4 days, the number of days in each of the working blocks is achieved for i= 0, thus wd/2 = 2. When that is not feasible, the function testBlocksCombination() is called and 98 9.1 Heuristic combinations of working blocks with different lengths are evaluated. This is the case illustrated in Fig. 9.4, for a planning period of 25 days. In this scenario, wd= 5 days, which is not divisible for any minD +i, for any i. Therefore, a combination of blocks of minD and minD + 1 days, 2 days and 3 days respectively, is used. If no combination of blocks satisfies the condition Fmin ≤Ftot, then the problem may not have a feasible solution. Consequently, the following statement can be made: If the input parameters selected verify the condition: Fmin ≤ Ftot, then it has a feasible solution. Otherwise, it may have or not a feasible solution. This condition is thus sufficient but not necessary. 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 !! #" #" !! $" $" !! !! !" !" !! #" #" !! $" $" !! !! !" !" Figure 9.1: Example: calculation of the number of available breaks/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 !! #" #" !! $" $" !! !! !" !" !! #" #" !! $" $" !! !! !" !" Figure 9.2: Example: calculation of the number of available breaks/team. 99 Chapter 9. Heuristic approach 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 !! #" #" !! $" $" !! !! !" !" !! #" #" !! $" $" !! !! !" !" Figure 9.3: Example: calculation of the number of working days/shift/team. 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 " " # # # ! ! " " # # ! ! ! " Figure 9.4: Example: solution for nD=25 days. 9.1.3 Algorithm 2 - generateSchedule If the condition is met we propose a constructive heuristic to build a feasible solution, as described in Algorithm 2 - generateSchedule. It starts by checking the relation between the input parameters nD and nT. The procedure only proceeds when nD is a multiple of nT. Then the function checkAvailableBreaks is called in order to verify if there are enough available breaks to guarantee the existence of a feasible solution, as explained before. After this condition is fullfiled, the schedule is generated, either with only working blocks with the same length, through the function generateEqualBlocksSchedule or combining working blocks with different length, calling the function generateCombinationBlocksSchedule. 9.1.4 Algorithm 3 - generateEqualBlocksSchedule The pseudo code of generateEqualBlocksSchedule is described in Algorithm 3. The idea is to build a feasible solution for the first team and then replicate it for the remaining (nT −1) teams. In this scenario, all working 100 9.1 Heuristic Algorithm 2 generateSchedule if nD is not a multiple of nT then Msg: ”Change input parameters” end if checkAvailableBreaks if solutionExists then initializeSchedule if equalBlocks then generateEqualBlocksSchedule else generateCombinationBlocksSchedule end if else if noFeasibleSolutionAssured then Msg: ”Fmin > Ftot, the problem may not have a feasible solution!” end if blocks have the same length of maxBlock days and are separated by one break. The procedure begins by assigning the first block of the first working shift to all teams, with a time lag, δD, equal to minD days between them, if maxBlock ≤minD or, otherwise, equal to nD/nT days. It proceeds by assigning the first blocks of the remaining shifts to the first team, separated by a break. In order to satisfy the shift daily demand, which forces each working shift to be assigned to only one team in each day of the planning period, the second sub-period can only begin when the first shift is available again, and for maxBlock consecutive days. This means that the second working block of the first shift can only be assigned to team 1 in a slot with, at least, maxBlock consecutive days where there isn’t any team assigned to that shift. The first sub-period is then replicated for the first team until the whole planning period is fulfilled, resulting in the schedule for the first team. This schedule is replicated for all the remaining (nT −1) teams, with a time lag of δD days between them. 101 Chapter 9. Heuristic approach Algorithm 3 generateEqualBlocksSchedule Use working blocks of maxBlock days Assign the first working block of the first shift to team 1 Use a time lag: δD =minD or nD/nT days to assign the first block of the first shift to all remaining (nT −1) teams Assign the first blocks of the remaining working shifts to team 1, separating each block with one break Insert breaks at the end of the last shift block to wait until the first shift is available again, in order to close the first sub-period Replicate the first sub-period to the first team as many times as necessary to fulfill the planning period Replicate the schedule of the first team to the remaining (nT −1) teams, with a time lag of δD =nD/nT days 9.1.5 Algorithm 4 - generateCombinationBlocksSchedule Algorithm 4 presents the procedure generateCombinationBlocksSchedule. The process is similar to the one followed in the previously described function generateEqualBlocksSchedule procedure, but in this case, the working blocks can have different lengths: maxBlock (maxBlock −1) and/or (maxBlock−2) days. The time lag δD to be used between teams’ schedules is nD/nT days. The procedure first assigns the working blocks of maxBlock days, then of (maxBlock−1) days and ends up with the assignment of blocks with (maxBlock −2) days, if applicable. An important aspect to take into account is the number of breaks to insert between working blocks, that must be 1 between maxBlock blocks, 2 between (maxBlock −1) blocks and 3 between (maxBlock −2) blocks. This makes all blocks of (working days plus breaks) to have the same length, equal to (maxBlock + 1) days. Again, we must ensure that no working shift is assigned to more than one team in each day, as already stated in Algorithm 3. This is achieved by inserting 102 9.2 Computational experiments and solutions Algorithm 4 generateCombinationBlocksSchedule Use a combination of working blocks of maxBlock, (maxBlock−1) and/or (maxBlock −2) days, if applicable for i= 0 →2do Assign the first (maxBlock−i) working block of the first shift to team 1 Use a time lag: δD =nD/nT to assign the first (maxBlock −i) block of the first shift to all remaining (nT −1) teams Assign the first (maxBlock −i) block of the remaining working shifts to team 1, separating each block with (i+ 1) breaks Insert breaks at the end of the last shift block to wait until the first shift is available again, in order to close the first sub-period end for Replicate the first sub-period to the first team as many times as necessary to fulfill the planning period Replicate the schedule of the first team to the remaining (nT −1) teams, with a time lag of δD =nD/nT days breaks at the end of the last working block of the first sub-period until the first shift is available again for the second sub-period assignment. The first sub-period is then replicated to the first team as many times as necessary in order to complete the whole planning period, resulting in the schedule for the first team. This schedule is replicated to all the remaining (nT −1) teams, with a time lag of δD days between them. 9.2 Computational experiments and solutions The heuristic was coded using VBA for Excel 2011 and ran on a server machine powered by 2 Intel R Xeon R processors of 2,4 GHz and 1,39 GHz, 103 Chapter 9. Heuristic approach No. Planning No. Execution time (sec.) shifts period (days) teams Heuristic 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: Computational results for a set of combinations of the ratio nS/nT. 9.3 Conclusions In this chapter a new constructive heuristic was proposed for solving the staff scheduling problem of the glass manufacture unit introduced in Chapter 5. The developed procedures were described and a comparison of the results achieved by both heuristic and optimization approaches was presented, highlighting a consistent outperformance of the heuristic over the optimization approach, with all results falling below 5 seconds. An important and novel contribution of this work is the approach introduced with Algorithm 1 - checkAvailableBreaks. With some simple calculations 110 9.3 Conclusions over the problem’s input data, it is possible to foresee the existence of a feasible solution. Although the proposed heuristic was developed for this specific instance, it is flexible enough to account for variations in some of the problem’s parameters and constraints. That is the case of the sequence of working shifts, which can be any that the user defines, as well as the minimum and maximum number of consecutive working days. With slight adjustments, the number of breaks to interpose between working blocks can also be redefined. Nevertheless, the proposed procedure has limitations when considering its direct applicability to other instances. It imposes the existence of at least one break day between each change of working shifts, so it does not allow for the possibility of having different shifts on consecutive days. The shift daily demand, for example, is a very strong constraint of this particular problem since it is on the basis of the calculation of the number of available breaks, as it was previously explained, which is a conditioning factor for the existence of a feasible solution. In problems with more than one team working simultaneously on the same shift, or with different daily requirements for each shift, this constraint would have to be reformulated and would imply deeper adjustments in the procedures proposed, but the base reasoning would be the same. As stated before, the “working-shifts sequence” approach is a strength of this work, for problems where a unique predefined sequence must be followed. But it can also be a limitation because, in problems where a set of sequences should be avoided, the heuristic may not respond accordingly, unless a preferred sequence can be chosen. As a conclusion, we believe that the achieved results are promising and encouraging of further extensions of the heuristic in order to consider, for example, different shift daily demands or forbidden sequences of shifts. 111 Chapter 9. Heuristic approach 112 Chapter 10 Conclusions 10.1 Contributions of this work In this thesis, we proposed an optimization method for simultaneously assigning work shifts and days-off to each employee. A general IP model was developed and applied, with slight adjustments, to three real-world problems: a glass production unit, a continuous care unit and a hospital. A set of benchmark instances was also used in order to evaluate the model’s performance when solving larger problems and to compare results with other methods. Two main goals of the model were to ensure a balanced and equitable schedule between all employees, in terms of workload, and also to respect a predefined sequence of work shifts and days-off, either following work rules or employees’ preferences. The first goal was achieved, initially, through the levelling of the number of days that each team works in each shift, as imposed by the objective function defined for the general model and in a next phase, through the imposition of equal schedules to all employees, with a time lag, of a predefined number of days, between them. This feature gives a cyclic dimension to the schedule. The second condition was achieved through the formulation of an array of indices that, together with the definition of a maximum and a minimum number of consecutive days, 113 Chapter 10. Conclusions enable the imposition of any desired pattern of work shifts and days-off. This pattern can be the same for all employees or can be defined according to contract types, skills, employees preferences, etc. This original formulation also makes it possible to control the periodicity of days-off, as well as the length of the tour or sub-period of the planning horizon. The definition of the planning period is not a very explored issue in the literature, since it is closely related to demand forecast periods and it is often an input parameter. But the initially set planning period may not be the one that better fits the problem’s features and so it is pertinent to study which is the “ideal” planning period for a specific instance. This experiment was carried out. Even though constraints on the periodicity of long-weekends and on planned absences were not an initial issue, the model was able to handle them as well, as shown in two of the case-studies. The model developed in this work demonstrated to be general and flexible, with several degrees of freedom and with the capacity of being easily applied to different real-life staff scheduling problems, but at the same time with a cyclic feature that ensures the equitableness and predictability of the schedule. The cyclic approach, often considered to be inflexible and not easily adjustable, proved to be flexible enough to successfully solve problems that are typically addressed with acyclic scheduling, namely with heterogeneous staff and fluctuating demand levels. This is a new insight and represents a novel contribution to the academic literature. From a company’s point of view, the use of the automatic scheduling model proposed in this research work can represent a powerful tool for increasing both the efficiency and the effectivity of the staff scheduling process, leading to higher profitability and productivity. However, the implementation of such a solution into practice is not always easy, it deeply depends on the involvement of the company in the whole development process. 114 10.2 Future research directions The developed heuristic approach represents an alternative method for solving one of the real-world problems studied in this thesis, allowing also for a comparative evaluation of the optimization model’s performance. An original contribution of the heuristic is that with some simple calculations over the problem’s input data, it is possible to foresee the existence of a feasible solution. This reduces the solution search space. Additionally, the comprehensive study on the staff scheduling problem and the insight into hospitality management operations constitute two assets for researchers looking for background on these topics. As a conclusion, we proposed a generic, novel and valuable approach to staff scheduling. We developed generic methodologies, showed their flexibility and solved a set of different problems. We challenged the potential of cyclic scheduling and proved it can be flexible. We developed an innovative formulation of sequence and consecutiveness of shifts. And we believe this research work can add value to a company by leading to cost reduction and an increase in the productivity. 10.2 Future research directions In order to consolidate our findings, future research could address the application of the proposed IP model to more real-world problems, from different activity sectors. Hospitality management is a promising area that should be more explored, namely hotels (housekeeping staff) and restaurants. Concerning the problems’ features, all the problems studied in this work had fixed shifts. It would be interesting to extend the IP model to consider the case of variable shifts, in terms of starting-times, length or even the placement of breaks. One of the drawbacks that are usually pointed out in the literature to cyclic 115 Chapter 10. Conclusions scheduling approaches is their difficulty in handling non predicted absences. In Chapter 5 absentees were replaced within their team. We have also shown how the IP model can ocasionally accommodate planned absences (Chapter 7). A systematic way of addressing this constraint could be worthy of further research. Although the proposed heuristic was developed for a specific problem, it proved to be flexible enough to account for variations in some of the problem’s parameters and constraints. The achieved results encourage further extensions of the procedure in order to consider, for example, different shift daily demands or forbidden sequences of shifts. 116 References Abdennadher, S. and Schlenker, H. (1999). Nurse scheduling using constraint logic programming. In Proceedings of the 11th Conference on Innovative Applications of Artificial Intelligence, pages 838–843. Addou, I. and Soumis, F. (2007). Bechtold-Jacobs generalized model for shift scheduling with extraordinary overlap. Annals of Operations Research, 155:177–205. Aickelin, U. and White, P. (2004). Building Better Nurse Scheduling Algorithms. Annals of Operations Research, 128(1-4):159–177. Alfares, H. (2004). Survey, categorization, and comparison of recent tour scheduling literature. Annals of Operations Research, 127(1):145–175. Alfares, H. K. (1998). An efficient two-phase algorithm for cyclic days-off scheduling. Computers & Operations Research, 25(11):913 – 923. Antunes, A. F. and Moz, M. (2011). Optimiza¸c˜ao do escalonamento de enfermeiros numa unidade hospitalar. In INESC-COIMBRA, editor, Livro de Actas do 15 Congresso da Associa¸c˜ao Portuguesa de Investiga¸c˜ao Operacional (IO2011), pages 25–36. Arabeyre, J., Fearnley, J., Steiger, F., and Teather, W. (1969). The airline crew scheduling problem: A survey. Transportation Science, 3(2):140–163. Aykin, T. (2000). A comparative evaluation of modeling approaches to the 117 REFERENCES labor shift scheduling problem. European Journal of Operational Research, 125(2):381–397. Azaiez, M. (2005). A 0-1 goal programming model for nurse scheduling. Computers & Operations Research, 32(3):491–507. Baker, K. R. (1976). Workforce Allocation in Cyclical Scheduling Problems: A Survey. Operational Research Quarterly (1970-1977), 27(1):155. Balakrishnan, N. and Wong, R. T. (1990). A network model for the rotating workforce scheduling problem. Networks, 20:25–42. Bard, J. F., Binici, C., and DeSilva, A. H. (2003). Staff scheduling at the United States Postal Service. Computers & Operations Research, 30(5):745–771. Barros, C. P. and Mascarenhas, M. J. (2005). Technical and allocative efficiency in a chain of small hotels. International Journal of Hospitality Management, 24(3):415 – 436. Barros, C. P., Peypoch, N., and Solonandrasana, B. (2008). Efficiency and productivity growth in hotel industry. International Journal of Tourism Research. Beaulieu, H., Ferland, J. A., Gendron, B., and Michelon, P. (2000). A mathematical programming approach for scheduling physicians in the emergency room. Health care management science, 3(3):193–200. Beaumont, N. (1997). Using mixed integer programming to design employee rosters. Journal of the Operational Research Society, 48(6):585–590. Bechtold, S. and Jacobs, L. (1990). Implicit modeling of flexible break assignments in optimal shift scheduling. Management Science, 36(11):1339– 1351. 118 REFERENCES Brotherton, B. (1999). Towards s definitive view of the nature of hospitality and hospitality management. International Journal of Contemporary Hospitality Management, 11(4):165–173. Brotherton, B. (2006). Some thoughts on a general theory of hospitality. Tourism Today, (6):7–19. Brotherton, B. and Wood, R. C. (2008). The nature and meanings of ‘hospitality’. In The SAGE Handbook of Hospitality Management, chapter 1, pages 35–61. SAGE. Brucker, P., Burke, E. K., Curtois, T., Qu, R., and Vanden Berghe, G. (2008). A shift sequence based approach for nurse scheduling and a new benchmark dataset. Journal of Heuristics, 16(4):559–573. Brusco, M. and Johns, T. (1996). A sequential integer programming method for discontinuous labor tour scheduling. European Journal of Operational Research, 95(3):537–548. Burke, E. (2003). A Tabu-Search hyperheuristic for timetabling and rostering. Journal of Heuristics, 9(6):451–470. Burke, E., Cowling, P., De Causmaecker, P., and Vanden Berghe, G. (2001). A memetic approach to the nurse rostering problem. Applied intelligence, 15(3):199–214. Burke, E., De Causmaecker, P., and Vanden Berghe, G. (1999). A Hybrid Tabu Search Algorithm for the Nurse Rostering Problem. In et Al., B. M., editor, Lecture Notes in Artificial Intelligence, volume 1585, pages 187– 194. Springer. Burke, E., Hyde, M., Kendall, G., Ochoa, G., Ozcan, E., and Woodward, J. R. (2010a). A classification of hyper-heuristic approaches. In Gendreau, M. and Potvin, J.-Y., editors, Handbook of Metaheuristics, volume 146 119 REFERENCES Schedules in Real Time. Cornell Hotel and Restaurant Administration Quarterly, 40(3):85. Thompson, G. M. (2003). Labor Scheduling: A Commentary. Cornell Hospitality Quarterly, 44(5-6):149–155. Thompson, G. M. and Goodale, J. C. (2006). Variable employee productivity in workforce scheduling. European Journal of Operational Research, 170(2):376 – 390. Topaloglu, S. and Ozkarahan, I. (2004). An Implicit Goal Programming Model for the Tour Scheduling Problem Considering the Employee Work Preferences. Annals of Operations Research, 128(1-4):135–158. Totterdell, P. (2005). Work schedules. Handbook of work stress, page 53. Ulusam Se¸ckiner, S., G¨ok¸cen, H., and Kurt, M. (2007). An integer programming model for hierarchical workforce scheduling problem. European Journal of Operational Research, 183(2):694–699. Valouxis, C. and Housos, E. (2000). Hybrid optimization techniques for the workshift and rest assignment of nursing personnel. Artificial intelligence in medicine, 20(2):155–75. Van den Bergh, J., Beli¨en, J., De Bruecker, P., Demeulemeester, E., and De Boeck, L. (2012). Personnel scheduling: A literature review. European Journal of Operational Research, http://dx.doi.org/10.1016/j.ejor.2012.11.029. Warner, D. M. (1976). Scheduling nursing personnel according to nursing preference: a mathematical programming approach. Operations Research, 24(5). Wren, A. (1996). Scheduling, timetabling and rostering - a special relationship? In Selected papers from the First International Conference on 126 REFERENCES Practice and Theory of Automated Timetabling, pages 46–75, London, UK. Springer-Verlag. Wren, A. (1998). Heuristics ancient and modern: Transport scheduling through the ages. Journal of Heuristics, 4:87–100. Wren, A. and Rousseau, J. (1995). Bus driver scheduling - an overview. Technical Report July, University of Leeds, School of Computer Studies. 127