Hybrid Genetic Algorithms for a Rostering Problem

Hybrid Genetic Algorithms are described for a large-size real-life rostering problem (railway workers' job scheduling and roster optimization). The new algorithm uses an order-based representation which encodes as a chromosome the list of job units to schedule. First, a greedy algorithm is considered, which uses a randomly generated job units list, and satisfies only the constraints pertaining to the workers' job contract. Then, a genetic algorithm optimizes the global roster, minimizing its length and achieving some desired homogenizations. Finally, a second genetic algorithm (GA) is used to find the best parameter values for the first genetic algorithm. Thus, this work investigates the use of a GA together with a greedy algorithm and of a second GA to optimize the parameter values of the first GA. The results of significant tests on real data are reported. They compare favourably with the known results on Rostering Problems, both in terms of execution time and solution accuracy. This work considers a practical Rostering Problem concerning the Railway workers' rosters optimization. The size of the input data is very challenging: about 1000 duties (i.e. job-units called ‘links’) based on a large-size city location; 125 days to consider for roster optimization (summer rostering); the goal is to optimize the structure of the working-turn for any worker, and to minimize the global cost of the rosters. It should be emphasised that this is a very large problem: we will use GAs to solve the problem within an execution time in the order of a few minutes on a common workstation.     

A branch-and-price algorithm for the multi-activity multi-task shift scheduling problem

The multi-activity multi-task shift scheduling problem requires the assignment of interruptible activities and uninterruptible tasks to a set of employees in order to satisfy a demand function. In this paper, we consider the personalized variant of the problem where the employees have different qualifications, preferences, and availabilities. We present a branch-and-price algorithm to solve this problem. The pricing subproblems in column generation are formulated with context-free grammars that are able to model complex rules in the construction of feasible shifts for an employee. We present results for a large set of instances inspired by real cases and show that this approach is sufficiently flexible to handle different classes of problems.     

Branching strategies in a branch-and-price approach for a multiple objective nurse scheduling problem

The efficient management of nursing personnel is of critical importance in a hospital’s environment comprising a vast share of the hospital’s operational costs. The nurse scheduling process affects highly the nurses’ working conditions, which are strongly related to the provided quality of care. In this paper, we consider the rostering over a mid-term period that involves the construction of duty timetables for a set of heterogeneous nurses. In scheduling nursing personnel, the head nurse is typically confronted with various (conflicting) goals complying with different priority levels which represent the hospital’s policies and the nurses’ preferences. In constructing a nurse roster, nurses need to be assigned to shifts in order to maximize the quality of the constructed timetable satisfying the case-specific time related constraints imposed on the individual nurse schedules. Personnel rostering in healthcare institutions is a highly constrained and difficult problem to solve and is known to be NP-hard. In this paper, we present an exact branch-and-price algorithm for solving the nurse scheduling problem incorporating multiple objectives and discuss different branching and pruning strategies. Detailed computational results are presented comparing the proposed branching strategies and indicating the beneficial effect of various principles encouraging computational efficiency.     

Crew rostering with multiple goals: An empirical study

An empirical crew rostering problem drawn from the customer service section of a department store in southern Taiwan is addressed in this paper. The service section established relevant service facilities and functions to provide services for customers as well as distinguished guests and visitors. The crew rostering task is concerned with assigning multi-functional workers to different types of job and scheduling working shifts for each worker within a given time horizon, where the available and demand workforce vary from one shift to another. The current crew rostering method is a seniority orientation method. In developing the roster under current method, lines of job are generated and then bids are taken in order of decreasing seniority. The most senior worker has the widest range of job lines from which to select so as to best satisfy his/her preference. Successive crew members bid for the remaining lines of job. The current method has some drawbacks. To overcome the drawbacks, this paper develops a problem-specific approach with three stages to deal with the crew rostering problem, making it more equitable and personalized for workers by considering the management goals concerning worker–job suitability, worker–worker compatibility and worker–shift fondness. Due to the vagueness of job characteristics and the personal attributes, fuzzy method is used to improve the evaluation results of suitability, compatibility and fondness. The utility similarities of fuzzy assessments with the linguistic grade of very good are used to measure the fitness grade for the management goals. A linear goal programming model is proposed to fulfill the “efficient assignment/match from the right” policy. The proposed approach ensures the right workers are assigned to the right jobs, the right workers are placed together in a job and the pleasing working shifts are given to the workers. An illustrative application demonstrates the implementation of the proposed approach.     

A Memetic Approach to the Nurse Rostering Problem

Constructing timetables of work for personnel in healthcare institutions is known to be a highly constrained and difficult problem to solve. In this paper, we discuss a commercial system, together with the model it uses, for this rostering problem. We show that tabu search heuristics can be made effective, particularly for obtaining reasonably good solutions quickly for smaller rostering problems. We discuss the robustness issues, which arise in practice, for tabu search heuristics. This paper introduces a range of new memetic approaches for the problem, which use a steepest descent improvement heuristic within a genetic algorithm framework. We provide empirical evidence to demonstrate the best features of a memetic algorithm for the rostering problem, particularly the nature of an effective recombination operator, and show that these memetic approaches can handle initialisation parameters and a range of instances more robustly than tabu search algorithms, at the expense of longer solution times. Having presented tabu search and memetic approaches (both with benefits and drawbacks) we finally present an algorithm that is a hybrid of both approaches. This technique produces better solutions than either of the earlier approaches and it is relatively unaffected by initialisation and parameter changes, combining some of the best features of each approach to create a hybrid which is greater than the sum of its component algorithms.     

On an exact method for the constrained shortest path problem

The constrained shortest path (CSP) is a well known NP-Hard problem. Besides from its straightforward application as a network problem, the CSP is also used as a building block under column-generation solution methods for crew scheduling and crew rostering problems. We propose an exact solution method for the CSP capable of handling large-scale networks in a reasonable amount of time. We compared our approach with three different state-of-the-art algorithms for the CSP and found optimal solutions on networks with up to 40,000 nodes and 800,000 arcs. We extended the algorithm to effectively solve the auxiliary problems of a multi-activity shift scheduling problem and a bus rapid transit route design problem tackled with column generation. We obtained significant speedups against alternative column generation schemes that solve the auxiliary problem with state-of-the-art commercial (linear) optimizers. We also present a first parallel version of our algorithm that shows promising results.     

Α two-phase adaptive variable neighborhood approach for nurse rostering

This contribution presents a two-phase variable neighborhood search algorithm for solving nurse rostering problems. In order to demonstrate the efficiency of the proposed algorithm, it is firstly applied to all nurse rostering problem instances as proposed in the First International Nurse Rostering Competition (INRC-2010). Computational results assessed on all three sets of sixty competition instances demonstrate that the proposed algorithm improves the best known results for two instances, inside the time limits of the competition, while achieving the best known bounds for forty eight other instances. The proposed algorithm was also applied to seven other nurse rostering instances reported in the respective literature and managed to achieve the best known result in six of them while improving the best known result in one instance. The proposed algorithm, as well as its differences from existing approaches are presented, described and discussed in detail.     

A genetic algorithm approach to a nurse rerostering problem

The nurse rerostering problem occurs when one or more nurses cannot work in shifts that were previously assigned to her or them. If no pool of reserve nurses exists to replace those absent, then the current roster must be rebuilt. This new roster must comply with the labour rules and institutional constraints. Moreover, it must be as similar as possible to the current one. The present paper describes constructive heuristics, besides several versions of genetic algorithms based on specific encoding and operators for sequencing problems applied to the nurse rerostering problem, defined with hard constraints. In the genetic algorithms described, each individual in the population is associated with a pair of chromosomes, representing permutations of tasks and nurses. Those permutations are used as input to a procedure that generates rosters. The fitness of individuals is given by the similarity between the roster generated from the permutations and the current one. The authors developed several versions of the genetic algorithm, whose difference lay in the encoding of permutations and in the genetic operators used for each encoding. These heuristics were tested with real data from a Lisbon hospital and yielded good quality solutions.     

A hybridization of mathematical programming and dominance-driven enumeration for solving shift-selection and task-sequencing problems

A common problem in production planning is to sequence a series of tasks so as to meet demand while satisfying operational constraints. This problem can be challenging to solve in its own right. It becomes even more challenging when higher-level decisions are also taken into account. For example, determining which shifts to operate clearly impacts how tasks are then scheduled; additionally, reducing the number of shifts that must be operated can have great cost benefits. Integrating the shift-selection and task-sequencing decisions can greatly impact tractability, however, traditional mathematical programming approaches often failing to converge in reasonable run times. Instead, we develop an approach that embeds mathematical programming, as a mechanism for solving simpler feasibility problems, within a larger search-based algorithm that leverages dominance to achieve substantial pruning. In this paper, we introduce the Shift-Selection and Task Sequencing problem (SS-TS), develop the Test-and-Prune algorithm (T&P), and present computational experiments based on a real-world problem in automotive stamping to demonstrate its effectiveness. In particular, we are able to solve to provable optimality, in very short run times, a number of problem instances that could not be solved through traditional integer programming methods.     

A hybrid setup for a hybrid scenario: combining heuristics for the home health care problem

Home health care, i.e. visiting and nursing patients in their homes, is a growing sector in the medical service business. From a staff rostering point of view, the problem is to find a feasible working plan for all nurses that has to respect a variety of hard and soft constraints, and preferences. Additionally, home health care problems contain a routing component: a nurse must be able to visit her patients in a given roster using a car or public transport. It is desired to design rosters that consider both, the staff rostering and vehicle routing components while minimizing transportation costs and maximizing satisfaction of patients and nurses.     

集成手术排程和护士排班的中期决策优化研究

在手术需求增大与医护人员短缺的矛盾下如何合理安排手术和配置医护资源,解决手术室实际运作中资源负荷不均衡现象,是当前手术室运作管理中亟待解决的难题。然而手术排程和手术室护士排班作为手术室科学管理的核心决策问题,却有着不同的时间域,并且会相互影响。在考虑科室手术和手术室护士偏好等硬约束和软约束前提下,构建一个集成手术排程和护士排班的手术室中期集成决策模型,设计了具有双层嵌套路径化结构的蚁群算法。通过某三甲医院10天的实际手术室运作数据,进行算法对比和分析评价,验证了算法在解决集成决策问题上的可行性和有效性。     

A particle swarm optimization approach with refinement procedure for nurse rostering problem

This study attempts to develop a model satisfying the rules of a typical hospital environment based both on published research data and on requirements of a local hospital under study. A mathematical formulation for the studied nurse rostering problem (NRP) is presented first. Due to the combinatorial nature of the NRP model, a particle swarm optimization (PSO) approach is proposed to solve this highly complicated NRP. The structure of the problem constraints is analyzed and used as base for generating workstretch patterns. These patterns serve as the base for generating fast initial solutions, and will later be improved upon by the proposed PSO algorithm. This study also proposes a simple yet effective procedure for attempting possible refinements on the solutions obtained by the PSO before reporting the final solutions. When fair shift assignment is considered as the decision objective, computational results show that the proposed PSO algorithm with refinement procedure is able to produce optimal solutions in all real test problems in a very efficient manner.     

A parallel membrane inspired harmony search for optimization problems: A case study based on a flexible job shop scheduling problem

Harmony search is an emerging meta-heuristic optimization algorithm that is inspired by musical improvisation processes, and it can solve various optimization problems. Membrane computing is a distributed and parallel model for solving hard optimization problems. First, we employed some previously proposed approaches to improve standard harmony search by allowing its parameters to be adaptive during the processing steps. Information from the best solutions was used to improve the speed of convergence while preventing premature convergence to a local minimum. Second, we introduced a parallel framework based on membrane computing to improve the harmony search. Our approach utilized the parallel membrane computing model to execute parallelized harmony search efficiently on different cores, where the membrane computing communication characteristics were used to exchange information between the solutions on different cores, thereby increasing the diversity of harmony search and improving the performance of harmony search. Our simulation results showed that the application of the proposed approach to different variants of harmony search yielded better performance than previous approaches. Furthermore, we applied the parallel membrane inspired harmony search to the flexible job shop scheduling problem. Experiments using well-known benchmark instances showed the effectiveness of the algorithm.     

The State of the Art of Nurse Rostering

Nurse rostering is a complex scheduling problem that affects hospital personnel on a daily basis all over the world. The need for quality software solutions is acute for a number of reasons. In particular, it is very important to efficiently utilise time and effort, to evenly balance the workload among people and to attempt to satisfy personnel preferences. A high quality roster can lead to a more contented and thus more effective workforce.In this review, we discuss nurse rostering within the global personnel scheduling problem in healthcare. We begin by briefly discussing the review and overview papers that have appeared in the literature and by noting the role that nurse rostering plays within the wider context of longer term hospital personnel planning. The main body of the paper describes and critically evaluates solution approaches which span the interdisciplinary spectrum from operations research techniques to artificial intelligence methods. We conclude by drawing on the strengths and weaknesses of the literature to outline the key issues that need addressing in future nurse rostering research.     

A bi-objective approach for shortest-path network interdiction

In the literature, solution approaches to the shortest-path network interdiction problem have been developed for optimizing a single figure-of-merit of the network configuration when considering limited amount of resources available to interdict network links. This paper presents a newly developed evolutionary algorithm that allows approximating the optimal Pareto set of network interdiction strategies when considering bi-objective shortest path problems. Thus, the paper considers the concurrent optimization of two objectives: (1) maximization of shortest-path length and (2) minimization of interdiction strategy cost. Also, the paper considers the transformation of the first objective into the minimization of the most reliable path reliability. To solve these multi-objective optimization problems, an evolutionary algorithm has been developed. This algorithm is based on Monte Carlo simulation, to generate potential network interdiction strategies, graph theory to analyze strategies’ shortest path or most reliable path and, an evolutionary search driven by the probability that a link will appear in the optimal Pareto set. Examples for different sizes of networks and network behavior are used throughout the paper to illustrate and validate the approach.     

A hybrid artificial bee colony for a nurse rostering problem

The nurse rostering problem (NRP) is a combinatorial optimization problem tackled by assigning a set of shifts to a set of nurses, each has specific skills and work contract, to a predefined rostering period according to a set constraints. The metaheuristics are the most successful methods for tackling this problem. This paper proposes a metaheuristic technique called a hybrid artificial bee colony (HABC) for NRP. In HABC, the process of the employed bee operator is replaced with the hill climbing optimizer (HCO) to empower its exploitation capability and the usage of HCO is controlled by hill climbing rate (HCR) parameter. The performance of the proposed HABC is evaluated using the standard dataset published in the first international nurse rostering competition 2010 (INRC2010). This dataset consists of 69 instances which reflect this problem in many real-world cases that are varied in size and complexity. The experimental results of studying the effect of HCO using different value of HCR show that the HCO has a great impact on the performance of HABC. In addition, a comparative evaluation of HABC is carried out against other eleven methods that worked on INRC2010 dataset. The comparative results show that the proposed algorithm achieved two new best results for two problem instances, 35 best published results out of 69 instances as achieved by other comparative methods, and comparable results in the remaining instances of INRC2010 dataset.     

A simulated annealing algorithm for dynamic layout problem

Increased level of volatility in today's manufacturing world demanded new approaches for modelling and solving many of its well-known problems like the facility layout problem. Over a decade ago Rosenblatt published a key paper on modelling and solving dynamic version of the facility layout problems. Since then, various other researchers proposed new and improved models and algorithms to solve the problem. Balakrishnan and Cheng have recently published a comprehensive review of the literature about this subject. The problem was defined as a complex combinatorial optimisation problem. The efficiency of SA in solving combinatorial optimisation problems is very well known. However, it has recently not been applied to DLP based on the review of the available literature. In this research paper a SA-based procedure for DLP is developed and results for test problems are reported.

Scope and purpose

One of the characteristic of today's manufacturing environments is volatility. Under a volatile environment (or dynamic manufacturing environment) demand is not stable. To operate efficiently under such environments facilities must be adaptive to changing demand conditions. This requires solution of the dynamic layout problem (DLP). DLP is a complex combinatorial optimisation problem for which optimal solutions can be found for small size problems. This research paper makes use of a SA algorithm to solve the DLP. Simulated annealing (SA) is a well-established stochastic neighbourhood search technique. It has a potential to solve complex combinatorial optimisation problems. The paper presents in detail how to apply SA to solve DLP and an extensive computational study. The computational study shows that SA is quite effective in solving dynamic layout problems.     

On the design of hybrid bio-inspired meta-heuristics for complex multiattribute vehicle routing problems

This paper addresses a multiattribute vehicle routing problem, the rich vehicle routing problem, with time constraints, heterogeneous fleet, multiple depots, multiple routes, and incompatibilities of goods. Four different approaches are presented and applied to 15 real datasets. They are based on two meta-heuristics, ant colony optimization (ACO) and genetic algorithm (GA), that are applied in their standard formulation and combined as hybrid meta-heuristics to solve the problem. As such ACO-GA is a hybrid meta-heuristic using ACO as main approach and GA as local search. GA-ACO is a memetic algorithm using GA as main approach and ACO as local search. The results regarding quality and computation time are compared with two commercial tools currently used to solve the problem. Considering the number of customers served, one of the tools and the ACO-GA approach outperforms the others. Considering the cost, ACO, GA, and GA-ACO provide better results. Regarding computation time, GA and GA-ACO have been found the most competitive among the benchmark.     

A comparative study of fuzzy PSO and fuzzy SVD-based RBF neural network for multi-label classification

In multi-label classification problems, every instance is associated with multiple labels at the same time. Binary classification, multi-class classification and ordinal regression problems can be seen as unique cases of multi-label classification where each instance is assigned only one label. Text classification is the main application area of multi-label classification techniques. However, relevant works are found in areas like bioinformatics, medical diagnosis, scene classification and music categorization. There are two approaches to do multi-label classification: The first is an algorithm-independent approach or problem transformation in which multi-label problem is dealt by transforming the original problem into a set of single-label problems, and the second approach is algorithm adaptation, where specific algorithms have been proposed to solve multi-label classification problem. Through our work, we not only investigate various research works that have been conducted under algorithm adaptation for multi-label classification but also perform comparative study of two proposed algorithms. The first proposed algorithm is named as fuzzy PSO-based ML-RBF, which is the hybridization of fuzzy PSO and ML-RBF. The second proposed algorithm is named as FSVD-MLRBF that hybridizes fuzzy c-means clustering along with singular value decomposition. Both the proposed algorithms are applied to real-world datasets, i.e., yeast and scene dataset. The experimental results show that both the proposed algorithms meet or beat ML-RBF and ML-KNN when applied on the test datasets.

     

A new model for the integrated vehicle-crew-rostering problem and a computational study on rosters

Operational planning within public transit companies has been extensively tackled but still remains a challenging area for operations research models and techniques. This phase of the planning process comprises vehicle-scheduling, crew-scheduling and rostering problems. In this paper, a new integer mathematical formulation to describe the integrated vehicle-crew-rostering problem is presented. The method proposed to obtain feasible solutions for this binary non-linear multi-objective optimization problem is a sequential algorithm considered within a preemptive goal programming framework that gives a higher priority to the integrated vehicle-crew-scheduling goal and a lower priority to the driver rostering goals. A heuristic approach is developed where the decision maker can choose from different vehicle-crew schedules and rosters, while respecting as much as possible management’s interests and drivers’ preferences. An application to real data of a Portuguese bus company shows the influence of vehicle-crew-scheduling optimization on rostering solutions.