SNCF is a large-sized railway transportation company that needs to be operated 365 days a year and 24 hours a day. In order to schedule a certain category of workers in train stations and selling points, rosters are designed to cover a cyclical demand. However, the highly combinatorial nature of the rostering problem makes it very difficult to solve manually, and experts spend a huge amount of time to derive implementable solutions that improve a number of preference criteria. This thesis presents two formulations based on mixed-integer programming to adress the cyclical rostering problem. The first one uses variables to express the nature of each day of the roster, whereas the second one uses patterns corresponding to feasible blocks of seven days and assigns them to each week of the roster. Different strategies relative to the management of some preference criteria are compared, some of them leading to significant reductions in computational times. Cuts are finally introduced to improve the bounds obtained by the linear relaxation of the mixed-integer programs. The impact of these cuts on computational times depends much on the problem. / Master of Science

Title: Workforce Optimisation Author: Štefan Pacinda Department / Institute: Department of Theoretical Computer Science and Mathematical Logic (KTIML) Supervisor of the master thesis: doc. RNDr. Roman Barták Ph.D., KTIML Abstract: Workforce management deals with the problem of maintaining productive workforce for example in call centers, hospitals, transportation companies etc. It includes the problem of deciding which skills are necessarily at each given time and how many personnel with given skills is required. These decisions are followed by solving the problem of allocating particular employees to shifts while satisfying the skill demands but also other constraints derived for example from law regulations, trade unions agreements, and individual preferences. This thesis deals with workforce optimization, that is with the optimal assignment of personnel to shifts in order to cover the demand for resources that vary over time. In this paper the solved problem is described in all detail and modeled as mixed integer program. Implementation details are presented and exhaustive analysis and experiments on a real life problem instance are performed to assure that the aims of the work have been met. Keywords: Rostering, Workforce Management, Shift Scheduling

<p>The harsh competition in the airline industry continuously forces airline carriers to streamline their production and cut back on costs. Manpower constitutes the largest expense in Scandinavian Airline System, closely followed by fuel costs. Thus effective crew planning is vital to face the competition from international actors and low cost carriers.</p><p>Creating efficient schedules for airline crew is a very complex combinatorial task and the process is heavily dependent on optimization. A large set of constraints comprised of union- and governmental rules as well as company policies and quality factors must be taken into consideration when the schedules are created.</p><p>This master thesis examines how the distribution of rank in the SAS international pilot corps affects the total cost associated with flight deck crew.</p><p>Long haul flights at SAS intercontinental are manned with a captain, a first officer and a relief pilot. Pilots may man lower ranking positions on any given flight in order to make efficient use of the pilot corps and to minimize the need of full time equivalents.</p><p>This work discusses the development and evaluation of a simulation environment developed in order to create and analyze fictitious crew populations with different distributions of rank. Furthermore the solution methods to the scheduling problem implemented at SAS and the optimization theory associated with them are discussed.</p><p>The project has resulted in an evaluation of the developed simulation environment and a discussion about the difficulties of analyzing crew populations with the systems currently in use at SAS.</p>

The harsh competition in the airline industry continuously forces airline carriers to streamline their production and cut back on costs. Manpower constitutes the largest expense in Scandinavian Airline System, closely followed by fuel costs. Thus effective crew planning is vital to face the competition from international actors and low cost carriers. Creating efficient schedules for airline crew is a very complex combinatorial task and the process is heavily dependent on optimization. A large set of constraints comprised of union- and governmental rules as well as company policies and quality factors must be taken into consideration when the schedules are created. This master thesis examines how the distribution of rank in the SAS international pilot corps affects the total cost associated with flight deck crew. Long haul flights at SAS intercontinental are manned with a captain, a first officer and a relief pilot. Pilots may man lower ranking positions on any given flight in order to make efficient use of the pilot corps and to minimize the need of full time equivalents. This work discusses the development and evaluation of a simulation environment developed in order to create and analyze fictitious crew populations with different distributions of rank. Furthermore the solution methods to the scheduling problem implemented at SAS and the optimization theory associated with them are discussed. The project has resulted in an evaluation of the developed simulation environment and a discussion about the difficulties of analyzing crew populations with the systems currently in use at SAS.

Constraint Programming can be used to solve many problems and this thesis is about getting an overview on the usage of Constraint Programming for Constraint Satisfaction Problems, both interactive and explorative. Many problems can be mathematically modeled as a Constraint Satisfaction Problem but this thesis will focus on the Nurse Rostering Problem since it is a well-studied area. The problem when creating a schedule for nurses is that it can easily be over-constrained and a solution could be hard to find. This thesis will investigate whether if Constraint Programming is a good technique for solving the Nurse Rostering Problem but also if user interaction is considered when solving the problem. The method for this is a literature study where a number of research articles has been reviewed and categorized, and resulted in 27 different kinds of sources that were used. The conclusion is that there exists better ways to solve these problems than the use of pure Constraint Programming. To answer the second part of the thesis, it seems like the solution for the problem is the main focus and therefore is user interaction something that is given less attention.

Made available in DSpace on 2015-03-05T13:57:00Z (GMT). No. of bitstreams: 0 Previous issue date: 27 / Nenhuma / Problemas de pessoal, produtividade e contenção de custos afetam todas as áreas de negócio, inclusive os provedores de cuidados de saúde. Porém, nesta área o controle dos custos não pode comprometer a qualidade do atendimento. É neste contexto que uma ferramenta computacional para a elaboração das escalas de trabalho de pessoal de enfermagem torna-se importante. Esta é uma tarefa realizada manualmente na maioria dos hospitais e clínicas, consumindo muito tempo e nem sempre atendendo completamente a legislação e normas vigentes. No Brasil há falta de ferramentas computacionais para a elaboração destas escalas, ou mesmo para a avaliação das escalas desenvolvidas. O objetivo desta pesquisa é encontrar uma solução, computacionalmente viável, para a geração de escalas de trabalho mensais para os técnicos de enfermagem, de acordo com as regras operacionais dos hospitais e as restrições da legislação. Deseja-se ainda obter maior nível de satisfação dos funcionários atendendo preferências de dias de folga e distribui / Problems of personnel, productivity and cost restriction affect all areas of a business, including the health care providers. However, in this area, cost control cannot endanger the quality of service. In this context, a software for creating the schedule of nursing personnel becomes important. This is a hand-made task in the majority of hospitals and clinics. It is time consuming and does not always comply to the legislation and the valid rules. In Brazil, there is a lack of computer tools for the creation of these schedules or even for the evaluation of the ones already developed. This research aims at finding a technologically feasible solution for the generation of monthly schedules for the nursing technicians, according to the operational rules of hospitals and legislation restrictions. It also aims at giving the employees a higher level of satisfaction, concerning their day off preferences and equitable distribution of duties on Saturdays, Sundays and holidays. The proposal is to apply a Tabu Search me

Šioje disertacijoje nagrinėjamas sveikatos priežiūros įstaigos darbuotojų darbų grafikų optimizavimo uždavinys, kuris formuluojamas ir sprendžiamas, remiantis vienos didžiausių Lietuvos sveikatos priežiūros įstaigų, realiais duomenimis. Disertacijoje apžvelgiami darbų grafikų optimizavimo uždaviniai bei jų sprendimo metodai, atlikta naujausių šaltinių, tiriančių panašius uždavinius, analizė. Antrame skyriuje nagrinėjamasis darbų grafikų optimizavimo uždavinys suformuluotas matematiškai. Pateikiamos dvi formuluotės: vienakriterio ir daugiakriterio optimizavimo uždavinio. Aprašomos sąlygos, kurias turi tenkinti sudaromasis darbų grafikas. Trečiajame skyriuje nagrinėjami metodai, tiek vienakriteriams, tiek daugiakriteriams uždaviniams spręsti. Pasiūlytas naujas metodas, kuris efektyviau nei kiti nagrinėti metodai sprendžia šioje disertacijoje suformuluotą uždavinį. Ketvirtame skyriuje pateikiami pasiūlyto metodo eksperimentinio tyrimo rezultatai. Pirmoje skyriaus dalyje analizuojami rezultatai gauti, sprendžiant vienakriterį optimizavimo uždavinį, o antroje dalyje – daugiakriterį optimizavimo uždavinį. Disertacijos tyrimų rezultatai buvo pristatyti respublikinėje konferencijoje ir trijose tarptautinėse konferencijose bei publikuoti trijuose mokslo žurnaluose. / In this dissertation nurse rostering problem is investigated. The formulation of the problem is based on real-world data of one of the largest healthcare centers in Lithuania. Most recent publications that tackle the nurse rostering problem and the methods for solving the nurse rostering problem are reviewed in this dissertation. The mathematical formulation of the single objective and the multi-objective nurse rostering problem is presented and the requirements for the roster are described in the second chapter. In the third chapter, the methods for solving the single objective and the multi-objective nurse rostering problem are described. A new method for solving the single objective and the multi-objective nurse rostering problem is proposed in the third chapter. In the fourth chapter, the experimental results of our proposed method are introduced. In the first section of this chapter, the results gathered solving single-objective optimization problem are analyzed, and in the second section of this chapter, the results gathered solving multi-objective optimization problem are analyzed. Dissertation research results were presented at one national conference and three international conferences and published in three scientific journals.

In the dissertation the nurse rostering problem is investigated. The formulation of the problem is based on real-world data of one of the largest healthcare centers in Lithuania. Most recent publications that tackle the nurse rostering problem and the methods for solving the nurse rostering problem are reviewed, the mathematical formulation of the single objective and the multi-objective nurse rostering problem is presented, the requirements for the roster are described and a new method for solving the single objective and the multi-objective nurse rostering problem is proposed in this dissertation. / Disertacijoje nagrinėjamas sveikatos priežiūros įstaigos darbuotojų darbų grafikų optimizavimo uždavinys, kuris formuluojamas ir sprendžiamas, remiantis vienos didžiausių Lietuvos sveikatos priežiūros įstaigų, realiais duomenimis. Disertacijoje apžvelgiami darbų grafikų optimizavimo uždaviniai bei jų sprendimo metodai. Pateikiama nagrinėjamo darbų grafikų vienakriterio ir daugiakriterio optimizavimo uždavinių matematinės formuluotės. Aprašomos sąlygos, kurias turi tenkinti sudaromasis darbų grafikas. Nagrinėjami metodai, tiek vienakriteriams, tiek daugiakriteriams darbų grafikų optimizavimo uždaviniams spręsti. Pasiūlytas naujas metodas, kuris yra efektyvesnis nei kiti nagrinėti metodai sprendžiant disertacijoje suformuluotą uždavinį.

Numerous studies have been done in the area of nurse scheduling, since this is a complex area with a lot of aspects that has to be taken into account. An interesting but little studied subject is how the requirements for the scheduling affect the possibility to construct a feasible schedule, or how the requirements affect the quality of the schedule. Of special interest is the effect of the composition of the workforce and of the change in scheduling rules. What is missing is results showing which composition and changes that are possible, and if so what is needed to be able to follow through with them. The changes tested in our simulation study are changes that is up for discussion at many wards in Sweden today, with topics such as split shifts and high part-time work percentages within the staff. In order to simulate various scheduling requirements and changes, an integer linear model for creating nurse schedules is developed. The results provide some insight into the dependence between scheduling requirements and the resulting schedules. In particular our simulation results indicate that there is an inherent conflict between high part-time work percentages and split or long work shifts. Our results can be used as a basis for future research on these topics in the area of nurse scheduling.

For workplaces with a preference or need for staffing around the clock, employees commonly work in shifts, which are work sessions that span different parts of the day. The scheduling of these shifts is a multi-objective optimization problem with both hard and soft constraints. The reduction in the available workforce when employees go on vacation makes the problem especially constrained. We describe a method that uses a genetic algorithm to generate shift schedules, for teams of employees and time periods with vacations. The method supports a staffing demand that can be met with one of multiple combinations of shifts. The genetic algorithm features specialized crossovers, together with a repair step aimed at maintaining staffing that fulfils the staffing requirements. A software implementation of the method is evaluated on three real-life problem instances. For two of them, it can produce schedules that are feasible, but subpar to those constructed manually by an experienced personnel scheduling professional. Several ideas to improve the program are presented.