The Experts below are selected from a list of 5286 Experts worldwide ranked by ideXlab platform
Edmund K. Burke - One of the best experts on this subject based on the ideXlab platform.
-
Personnel Scheduling: Models and complexity
European Journal of Operational Research, 2011Co-Authors: Peter Brucker, Edmund K. BurkeAbstract:Due to its complexity, its challenging features, and its practical relevance, Personnel Scheduling has been heavily investigated in the last few decades. However, there is a relatively low level of study on models and complexity in these important problems. In this paper, we present mathematical models which cover specific aspects in the Personnel Scheduling literature. Furthermore, we address complexity issues by identifying polynomial solvable and NP-hard special cases.
-
An Evolutionary Squeaky Wheel Optimization Approach to Personnel Scheduling
IEEE Transactions on Evolutionary Computation, 2009Co-Authors: Uwe Aickelin, Edmund K. BurkeAbstract:The quest for robust heuristics that are able to solve more than one problem is ongoing. In this paper, we present, discuss and analyze a technique called Evolutionary Squeaky Wheel Optimization and apply it to two different Personnel Scheduling problems. Evolutionary Squeaky Wheel Optimization improves the original squeaky wheel optimization's effectiveness and execution speed by incorporating two additional steps (selection and mutation) for added evolution. In the evolutionary squeaky wheel optimization, a cycle of analysis-selection-mutation-prioritization-construction continues until stopping conditions are reached. The aim of the analysis step is to identify below average solution components by calculating a fitness value for all components. The selection step then chooses amongst these underperformers and discards some probabilistically based on fitness. The mutation step further discards a few components at random. Solutions can become incomplete and thus repairs may be required. The repair is carried out by using the prioritization step to first produce priorities that determine an order by which the following construction step then schedules the remaining components. Therefore, improvements in the evolutionary squeaky wheel optimization is achieved by selective solution disruption mixed with iterative improvement and constructive repair. Strong experimental results are reported on two different domains of Personnel Scheduling: bus and rail driver Scheduling and hospital nurse Scheduling.
-
An Evolutionary Squeaky Wheel Optimisation Approach to Personnel Scheduling
SSRN Electronic Journal, 2009Co-Authors: Uwe Aickelin, Edmund K. BurkeAbstract:The quest for robust heuristics that are able to solve more than one problem is ongoing. In this paper, we present, discuss and analyse a technique called Evolutionary Squeaky Wheel Optimisation and apply it to two different Personnel Scheduling problems. Evolutionary Squeaky Wheel Optimisation improves the original Squeaky Wheel Optimisation's effectiveness and execution speed by incorporating two extra steps (Selection and Mutation) for added evolution. In the Evolutionary Squeaky Wheel Optimisation, a cycle of Analysis-Selection-Mutation-Prioritization-Construction continues until stopping conditions are reached. The aim of the Analysis step is to identify below average solution components by calculating a fitness value for all components. The Selection step then chooses amongst these underperformers and discards some probabilistically based on fitness. The Mutation step further discards a few components at random. Solutions can become incomplete and thus repairs may be required. The repairs are carried out by using the Prioritization to first produce priorities that determine an order by which the following Construction step then schedules the remaining components. Therefore, improvement in the Evolutionary Squeaky Wheel Optimisation is achieved by selective solution disruption mixed with interative improvement and constructive repair. Strong experimental results are reported on two different domains of Personnel Scheduling: bus and rail driver Scheduling and hospital nurse Scheduling.
-
A Component-Based Heuristic Search Method with Evolutionary Eliminations for Hospital Personnel Scheduling
INFORMS Journal on Computing, 2009Co-Authors: Uwe Aickelin, Edmund K. BurkeAbstract:Nurse rostering is a complex Scheduling problem that affects hospital Personnel on a daily basis all over the world. This paper presents a new component-based approach with evolutionary eliminations for a nurse Scheduling problem arising at a major UK hospital. The main idea behind this technique is to decompose a schedule into its components (i.e., the allocated shift pattern of each nurse), and then to implement two evolutionary elimination strategies mimicking natural selection and the natural mutation process on these components, respectively, to iteratively deliver better schedules. The worthiness of all components in the schedule has to be continuously demonstrated for them to remain there. This demonstration employs an evaluation function that evaluates how well each component contributes toward the final objective. Two elimination steps are then applied: the first elimination removes a number of components that are deemed not worthy to stay in the current schedule; the second elimination may also throw out, with a low level of probability, some worthy components. The eliminated components are replenished with new ones using a set of constructive heuristics using local optimality criteria. Computational results using 52 data instances demonstrate the applicability of the proposed approach in solving real-world problems.
-
A Component Based Heuristic Search Method with Adaptive Perturbations for Hospital Personnel Scheduling
SSRN Electronic Journal, 2006Co-Authors: Uwe Aickelin, Edmund K. BurkeAbstract:Nurse rostering is a complex Scheduling problem that affects hospital Personnel on a daily basis all over the world. This paper presents a new component-based approach with adaptive perturbations, for a nurse Scheduling problem arising at a major UK hospital. The main idea behind this technique is to decompose a schedule into its components (i.e. the allocated shift pattern of each nurse), and then mimic a natural evolutionary process on these components to iteratively deliver better schedules. The worthiness of all components in the schedule has to be continuously demonstrated in order for them to remain there. This demonstration employs a dynamic evaluation function which evaluates how well each component contributes towards the final objective.Two perturbation steps are then applied: the first perturbation eliminates a number of components that are deemed not worthy to stay in the current schedule; the second perturbation may also throw out, with a low level of probability, some worthy components. The eliminated components are replenished with new ones using a set of constructive heuristics using local optimality criteria. Computational results using 52 data instances demonstrate the applicability of the proposed approach in solving real-world problems.
Liesje De Boeck - One of the best experts on this subject based on the ideXlab platform.
-
a three stage approach for aircraft line maintenance Personnel rostering using mip discrete event simulation and dea
Expert Systems With Applications, 2013Co-Authors: Jorne Van Den Bergh, Jeroen Belien, Philippe De Bruecker, Liesje De Boeck, Erik DemeulemeesterAbstract:Personnel Scheduling problems need to cope with Personnel preferences, coverage constraints, legal restrictions, and many other constraints. We present a three-stage methodology that can be used to select Personnel rosters. In the first stage we generate multiple Personnel rosters with a mathematical programming model. In the second stage, the performance of the rosters regarding a number of service criteria is evaluated through discrete event simulation. In the third stage, a ranking is made using data envelopment analysis. The methodology is tested on a Personnel Scheduling problem for aircraft line maintenance.
-
Personnel Scheduling: A literature review
European Journal of Operational Research, 2013Co-Authors: Jorne Van Den Bergh, Jeroen Belien, Philippe De Bruecker, Erik Demeulemeester, Liesje De BoeckAbstract:This paper presents a review of the literature on Personnel Scheduling problems. Firstly, we discuss the classification methods in former review papers. Secondly, we evaluate the literature in the many fields that are related to either the problem setting or the technical features. Each perspective is presented as a table in which the classification is displayed. This method facilitates the identification of manuscripts related to the reader’s specific interests. Throughout the literature review, we identify trends in research on Personnel staffing and Scheduling, and we indicate which areas should be subject to future research.
-
Personnel Scheduling: A literature review
European Journal of Operational Research, 2013Co-Authors: Jorne Van Den Bergh, Jeroen Belien, Philippe De Bruecker, Erik Demeulemeester, Liesje De BoeckAbstract:This paper presents a review of the literature on Personnel Scheduling problems. Firstly, we discuss the classification methods in former review papers. Secondly, we evaluate the literature in the many fields that are related to either the problem setting or the technical features. Each perspective is presented as a table in which the classification is displayed. This method facilitates the identification of manuscripts related to the reader’s specific interests. Throughout the literature review, we identify trends in research on Personnel staffing and Scheduling, and we indicate which areas should be subject to future research.
Michael J. Brusco - One of the best experts on this subject based on the ideXlab platform.
-
LP-based working subsets for Personnel Scheduling: Evaluation and augmentation
European J. of Industrial Engineering, 2018Co-Authors: Michael J. Brusco, Tony R. Johns, Ray R. VenkataramanAbstract:This paper evaluates the efficacy of LP-based working subsets for generalised set-covering formulations of Personnel Scheduling problems and presents a nearest-neighbour augmentation procedure for improving performance. Three experimental studies were completed in the evaluation process. In the first study, the LP-based working subset was sufficient to yield an optimal shift Scheduling solution for 85% of the 24,300 test problems and the nearest-neighbour augmentation improved the percentage of optimal solutions to over 98%. The second study focused on more complex cyclic shift Scheduling environments that permitted shift length, meal break and relief break flexibility. The adequacy of LP-based working subsets was supported by the provision of optimal shift Scheduling solutions for 185 of 189 (98%) of the test problems. The third study examined a challenging tour Scheduling environment for which globally-optimal benchmarks are not available. The superiority of the augmented LP-based working subset procedure was nevertheless evident, as it yielded better results than the (non-augmented) LP-based working subset for 92% of the test problems despite being constrained to only 40% of the allowed computation time for the non-augmented subsets. [Received 24 April 2017; Revised 25 August 2017; Revised 17 September 2017; Accepted 6 December 2017]
-
Personnel tour Scheduling when starting time restrictions are present
Management Science, 1998Co-Authors: Michael J. Brusco, Larry W. JacobsAbstract:This paper presents an effective solution strategy for an important category of Personnel Scheduling problems. Specifically, we address the restricted starting-time tour-Scheduling problem (RSTP), which involves the determination of the hours of the day (shifts) and days of the week (days on) that employees are assigned to work. RSTP is characterized by restrictions on the number of daily time periods in which employees may begin their shifts. Moreover, the RSTP we consider contains constraints that require separation of starting times. Such restrictions are widely encountered in practice and are based on a number of factors including managerial concerns for control of employee movements, union contractual obligations, and employee preferences for common shift starting times. A two-stage heuristic solution strategy is proposed for RSTP. We developed eight heuristic procedures based on this strategy and applied them to four sets of labor requirements, for each of 27 United Airlines (UA) airport ground stations. One of the best of these procedures yielded solution costs that averaged only 1.36 full-time-equivalent employees above very conservative LP-based lower bounds. Moreover, the solution costs obtained using this procedure were, on average, 28 percent closer to the lower bounds than solution costs obtained using UA's current Scheduling system. We conclude that the two-stage heuristic solution strategy is a valuable platform from which to develop procedures for generating near-optimal solutions to this difficult class of Personnel Scheduling problems.
-
Microcomputer‐based working set generation methods for Personnel Scheduling
International Journal of Operations & Production Management, 1995Co-Authors: Stephen E. Bechtold, Michael J. BruscoAbstract:Presents a new approach to working set generation for Personnel Scheduling problems. In full‐time (FT) and mixed‐workforce (MW) experiments, generates the schedules in the working sets from the use of two‐phase heuristic labour Scheduling solution procedures. The solution procedures were implemented on a 386 microcomputer and did not require the specification of the size of the working sets in advance. In the FT experiment, the general set‐covering formulations (GSCFs) associated with the produced working sets were solved with integer programming. The new working set procedure yielded optimal integer solutions for all 36 test problems in the FT experiment. Owing to the size and complexity of the problem data in the MW experiment, the GSCFs associated with the working sets were solved with linear programming, and heuristic rounding procedures were applied to obtain feasible integer solutions. The mean labour costs of these solutions averaged 0.69 per cent less than the mean cost of solutions obtained via t...
-
Cost analysis of alternative formulations for Personnel Scheduling in continuously operating organizations
European Journal of Operational Research, 1995Co-Authors: Michael J. Brusco, Larry W. JacobsAbstract:Personnel-Scheduling problems for continuously operating organizations have proven to be difficult to solve optimally. As a consequence, a number of alternative approaches have been devised for solving these problems. We provide computational results of a study of the staffing costs obtained using a prominent alternative formulation approach. The results demonstrate that excess staffing costs may result from the use of this approach. We subsequently develop a new local-search heuristic based on the simulated annealing algorithm to generate feasible integer Personnel schedules in continuously operating organizations. The solution costs and computational effort associated with the new heuristic are shown to be generally superior to those of branch-and-bound integer programming.
-
Improving Personnel Scheduling at Airline Stations
Operations Research, 1995Co-Authors: Michael J. Brusco, Larry W. Jacobs, Robert J. Bongiorno, Duane V. Lyons, Baoxing TangAbstract:Many service organizations encounter Personnel tour-Scheduling problems which focus on the efficient assignment of daily shift schedules and work days to employees across a weekly planning horizon. The airline Industry, in particular, faces a highly complex and difficult tour-Scheduling environment for their ground station Personnel, During the past twenty years, the airlines have worked to improve continuously their abilities to effectively schedule Personnel working at planesides, counters, and gates in airline stations. Substantial reductions in labor costs have resulted from the use of efficient tour-Scheduling methods for such workers. We report on the development and implementation of two modules designed to enhance the tour-Scheduling process associated with United Airlines' Pegasys Manpower Planning System. The first module uses column generation to improve the selection of employee shifts. The second module, a local search heuristic based on simulated annealing, enables initial feasible tour-Scheduling solutions to rapidly improve. Using data collected from all 119 United Airlines stations across the U.S., we find that the incorporation of the modules results in a potential annual cost savings of more than $8 million. We conclude with a discussion of notable implementation issues and extensions.
Erik Demeulemeester - One of the best experts on this subject based on the ideXlab platform.
-
a three stage approach for aircraft line maintenance Personnel rostering using mip discrete event simulation and dea
Expert Systems With Applications, 2013Co-Authors: Jorne Van Den Bergh, Jeroen Belien, Philippe De Bruecker, Liesje De Boeck, Erik DemeulemeesterAbstract:Personnel Scheduling problems need to cope with Personnel preferences, coverage constraints, legal restrictions, and many other constraints. We present a three-stage methodology that can be used to select Personnel rosters. In the first stage we generate multiple Personnel rosters with a mathematical programming model. In the second stage, the performance of the rosters regarding a number of service criteria is evaluated through discrete event simulation. In the third stage, a ranking is made using data envelopment analysis. The methodology is tested on a Personnel Scheduling problem for aircraft line maintenance.
-
Personnel Scheduling: A literature review
European Journal of Operational Research, 2013Co-Authors: Jorne Van Den Bergh, Jeroen Belien, Philippe De Bruecker, Erik Demeulemeester, Liesje De BoeckAbstract:This paper presents a review of the literature on Personnel Scheduling problems. Firstly, we discuss the classification methods in former review papers. Secondly, we evaluate the literature in the many fields that are related to either the problem setting or the technical features. Each perspective is presented as a table in which the classification is displayed. This method facilitates the identification of manuscripts related to the reader’s specific interests. Throughout the literature review, we identify trends in research on Personnel staffing and Scheduling, and we indicate which areas should be subject to future research.
-
Personnel Scheduling: A literature review
European Journal of Operational Research, 2013Co-Authors: Jorne Van Den Bergh, Jeroen Belien, Philippe De Bruecker, Erik Demeulemeester, Liesje De BoeckAbstract:This paper presents a review of the literature on Personnel Scheduling problems. Firstly, we discuss the classification methods in former review papers. Secondly, we evaluate the literature in the many fields that are related to either the problem setting or the technical features. Each perspective is presented as a table in which the classification is displayed. This method facilitates the identification of manuscripts related to the reader’s specific interests. Throughout the literature review, we identify trends in research on Personnel staffing and Scheduling, and we indicate which areas should be subject to future research.
Larry W. Jacobs - One of the best experts on this subject based on the ideXlab platform.
-
Personnel tour Scheduling when starting time restrictions are present
Management Science, 1998Co-Authors: Michael J. Brusco, Larry W. JacobsAbstract:This paper presents an effective solution strategy for an important category of Personnel Scheduling problems. Specifically, we address the restricted starting-time tour-Scheduling problem (RSTP), which involves the determination of the hours of the day (shifts) and days of the week (days on) that employees are assigned to work. RSTP is characterized by restrictions on the number of daily time periods in which employees may begin their shifts. Moreover, the RSTP we consider contains constraints that require separation of starting times. Such restrictions are widely encountered in practice and are based on a number of factors including managerial concerns for control of employee movements, union contractual obligations, and employee preferences for common shift starting times. A two-stage heuristic solution strategy is proposed for RSTP. We developed eight heuristic procedures based on this strategy and applied them to four sets of labor requirements, for each of 27 United Airlines (UA) airport ground stations. One of the best of these procedures yielded solution costs that averaged only 1.36 full-time-equivalent employees above very conservative LP-based lower bounds. Moreover, the solution costs obtained using this procedure were, on average, 28 percent closer to the lower bounds than solution costs obtained using UA's current Scheduling system. We conclude that the two-stage heuristic solution strategy is a valuable platform from which to develop procedures for generating near-optimal solutions to this difficult class of Personnel Scheduling problems.
-
Cost analysis of alternative formulations for Personnel Scheduling in continuously operating organizations
European Journal of Operational Research, 1995Co-Authors: Michael J. Brusco, Larry W. JacobsAbstract:Personnel-Scheduling problems for continuously operating organizations have proven to be difficult to solve optimally. As a consequence, a number of alternative approaches have been devised for solving these problems. We provide computational results of a study of the staffing costs obtained using a prominent alternative formulation approach. The results demonstrate that excess staffing costs may result from the use of this approach. We subsequently develop a new local-search heuristic based on the simulated annealing algorithm to generate feasible integer Personnel schedules in continuously operating organizations. The solution costs and computational effort associated with the new heuristic are shown to be generally superior to those of branch-and-bound integer programming.
-
Improving Personnel Scheduling at Airline Stations
Operations Research, 1995Co-Authors: Michael J. Brusco, Larry W. Jacobs, Robert J. Bongiorno, Duane V. Lyons, Baoxing TangAbstract:Many service organizations encounter Personnel tour-Scheduling problems which focus on the efficient assignment of daily shift schedules and work days to employees across a weekly planning horizon. The airline Industry, in particular, faces a highly complex and difficult tour-Scheduling environment for their ground station Personnel, During the past twenty years, the airlines have worked to improve continuously their abilities to effectively schedule Personnel working at planesides, counters, and gates in airline stations. Substantial reductions in labor costs have resulted from the use of efficient tour-Scheduling methods for such workers. We report on the development and implementation of two modules designed to enhance the tour-Scheduling process associated with United Airlines' Pegasys Manpower Planning System. The first module uses column generation to improve the selection of employee shifts. The second module, a local search heuristic based on simulated annealing, enables initial feasible tour-Scheduling solutions to rapidly improve. Using data collected from all 119 United Airlines stations across the U.S., we find that the incorporation of the modules results in a potential annual cost savings of more than $8 million. We conclude with a discussion of notable implementation issues and extensions.