Α 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.     

Cooperative search for fair nurse rosters

The development of decision support systems acceptable for nurse rostering practitioners still presents a daunting challenge. Building on an existing nurse rostering problem, a set of fairness-based objective functions recently introduced in the literature has been extended. To this end, a generic agent-based cooperative search framework utilising new mechanisms is described, aiming to combine the strengths of multiple metaheuristics. These different metaheuristics represent individual planners’ implicit procedures for improving rosters. The framework enables to explore different ways of assessing nurse rosters in terms of fairness objectives. Computational experiments have been conducted across a set of benchmark instances. The overall results indicate that the proposed cooperative search for fair nurse rosters outperforms each metaheuristic run individually.     

Fast forward planning by guided enforced hill climbing

In recent years, a number of new heuristic search methods have been developed in the field of automated planning. Enforced hill climbing (EHC) is one such method which has been frequently used in a number of AI planning systems. Despite certain weaknesses, such as getting trapped in dead-ends in some domains, this method is more competitive than several other methods in many planning domains. In order to enhance the efficiency of ordinary enforced hill climbing, a new form of enforced hill climbing, called guided enforced hill climbing, is introduced in this paper. An adaptive branch ordering function is the main feature that guided enforced hill climbing has added to EHC. Guided enforced hill climbing expands successor states in the order recommended by the ordering function. Our experimental results in several planning domains show a significant improvement in the efficiency of the enforced hill climbing method, especially when applied to larger problems.     

An evolutionary algorithm based on constraint set partitioning for nurse rostering problems

The nurse rostering problem (NRP) is a representative of NP-hard combinatorial optimization problems. The hardness of NRP is mainly due to its multiple complex constraints. Several approaches, which are based on an evolutionary algorithm (EA) framework and integrated with a penalty-function technique, were proposed in the literature to handle the constraints found in NRP. However, these approaches are not very efficient in dealing with large-scale NPR instances and thus need to be improved upon. In this paper, we investigate a large-scale NRP in a real-world setting, i.e., Chinese NRP (CNRP), which requires us to arrange many nurses (up to 30) across a 1-month scheduling period. The CNRP poses various constraints that lead to a large solution space with multiple isolated areas of infeasible solutions. We propose a single-individual EA for the CNRP. The novelty of the proposed approach is threefold: (1) using a constraint separation to partition the constraints into hard and soft constraints; (2) using a revised integer programming to generate a high-quality initial individual (solution), which then leads the subsequent EA search to a promising feasible solution space; and (3) using an efficient mutation operator to quickly search for a better solution in the restricted feasible solution space. The experimental results based on extensive simulations indicate that our proposed approach significantly outperforms several existing representative algorithms, in terms of solution quality within the same calculation times of the objective function.     

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.     

ABC-based manufacturing scheduling for unrelated parallel machines with machine-dependent and job sequence-dependent setup times

To date, the topic of unrelated parallel machine scheduling problems with machine-dependent and job sequence-dependent setup times has received relatively little research attention. In this study, a hybrid artificial bee colony (HABC) algorithm is presented to solve this problem with the objective of minimizing the makespan. The performance of the proposed HABC algorithm was evaluated by comparing its solutions to state-of-the-art metaheuristic algorithms and a high performing artificial bee colony (ABC)-based algorithm. Extensive computational results indicate that the proposed HABC algorithm significantly outperforms these best-so-far algorithms. Since the problem addressed in this study is a core topic for numerous industrial applications, this article may help to reduce the gap between theoretical progress and industrial practice.     

Solving the team orienteering problem using effective multi-start simulated annealing

The team orienteering problem (TOP) is known as an NP-complete problem. A set of locations is provided and a score is collected from the visit to each location. The objective is to maximize the total score given a fixed time limit for each available tour. Given the computational complexity of this problem, a multi-start simulated annealing (MSA) algorithm which combines a simulated annealing (SA) based meta-heuristic with a multi-start hill climbing strategy is proposed to solve TOP. To verify the developed MSA algorithm, computational experiments are performed on well-known benchmark problems involving numbers of locations ranging between 42 and 102. The experimental results demonstrate that the multi-start hill climbing strategy can significantly improve the performance of the traditional single-start SA. Meanwhile, the proposed MSA algorithm is highly effective compared to the state-of-the-art meta-heuristics on the same benchmark instances. The proposed MSA algorithm obtained 135 best solutions to the 157 benchmark problems, including five new best solutions. In terms of both solution quality and computational expense, this study successfully constructs a high-performance method for solving this challenging problem.     

Multiprocessor task scheduling in multistage hybrid flowshops: A hybrid artificial bee colony algorithm with bi-directional planning

In this paper, the problem of scheduling multistage hybrid flowshops with multiprocessor tasks is contemplated. This is a strongly NP-hard problem for which a hybrid artificial bee colony (HABC) algorithm with bi-directional planning is developed to minimize makespan. To validate the effectiveness of the proposed algorithm, computational experiments were tested on two well-known benchmark problem sets. The computational evaluations manifestly support the high performance of the proposed HABC against the best-so-far algorithms applied in the literature for the same benchmark problem sets.     

An ensemble uncertainty aware measure for directed hill climbing ensemble pruning

This paper proposes a new measure for ensemble pruning via directed hill climbing, dubbed Uncertainty Weighted Accuracy (UWA), which takes into account the uncertainty of the decision of the current ensemble. Empirical results on 30 data sets show that using the proposed measure to prune a heterogeneous ensemble leads to significantly better accuracy results compared to state-of-the-art measures and other baseline methods, while keeping only a small fraction of the original models. Besides the evaluation measure, the paper also studies two other parameters of directed hill climbing ensemble pruning methods, the search direction and the evaluation dataset, with interesting conclusions on appropriate values.     

$$\beta$$ -Hill climbing: an exploratory local search

Hill climbing method is an optimization technique that is able to build a search trajectory in the search space until reaching the local optima. It only accepts the uphill movement which leads it to easily get stuck in local optima. Several extensions to hill climbing have been proposed to overcome such problem such as Simulated Annealing, Tabu Search. In this paper, an extension version of hill climbing method has been proposed and called \(\beta\)-hill climbing. A stochastic operator called \(\beta\)-operator is utilized in hill climbing to control the balance between the exploration and exploitation during the search. The proposed method has been evaluated using IEEE-CEC2005 global optimization functions. The results show that the proposed method is a very efficient enhancement to the hill climbing providing powerful results when it compares with other advanced methods using the same global optimization functions.

     

Modelling and Solving Employee Timetabling Problems

Employee timetabling is the operation of assigning employees to tasks in a set of shifts during a fixed period of time, typically a week. We present a general definition of employee timetabling problems (ETPs) that captures many real-world problem formulations and includes complex constraints. The proposed model of ETPs can be represented in a tabular form that is both intuitive and efficient for constraint representation and processing. The constraint networks of ETPs include non-binary constraints and are difficult to formulate in terms of simple constraint solvers. We investigate the use of local search techniques for solving ETPs. In particular, we propose several versions of hill-climbing that make use of a novel search space that includes also partial assignments. We show that, on large and difficult instances of real world ETPs, where systematic search fails, local search methods perform well and solve the hardest instances. According to our experimental results on various techniques, a simple version of hill climbing based on random moves is the best method for solving large ETP instances.     

Ordinal Hill Climbing Algorithms for Discrete Manufacturing Process Design Optimization Problems

Thispaper introduces ordinal hill climbing algorithms for addressingdiscrete manufacturing process design optimization problems usingcomputer simulation models. Ordinal hill climbing algorithmscombine the search space reduction feature of ordinal optimizationwith the global search feature of generalized hill climbing algorithms.By iteratively applying the ordinal optimization strategy withinthe generalized hill climbing algorithm framework, the resultinghybrid algorithm can be applied to intractable discrete optimizationproblems. Computational results on an integrated blade rotormanufacturing process design problem are presented to illustratethe application of the ordinal hill climbing algorithm. The relationshipbetween ordinal hill climbing algorithms and genetic algorithmsis also discussed. This discussion provides a framework for howthe ordinal hill climbing algorithm fits into currently appliedalgorithms, as well as to introduce a bridge between the twoalgorithms.     

求解护士排班问题的变邻域搜索算法

变邻域搜索算法是求解护士排班问题的一个有效算法,其扰动方法对算法性能有显著影响。为提高护士排班问题中护士的满意度,提出一个改进的变邻域搜索(IVNS)算法。该算法使用了三种邻域结构,而且当使用任意的邻域都不能进一步改进当前解时,设计了一个对当前最优解进行扰动的方法,即在排班期间内随机地选择两天,在不违反硬性约束的条件下选出一组值班护士并交换他们在这两天中的班次。在2010年举行的第一次全球护士排班大赛提供的一组公共测试集上与一个混合变邻域搜索(HVNS)算法进行了比较,在Sprint-early、Medium-early和Long-early组算例上的结果表明,IVNS算法的最优值至少不劣于HVNS,而平均值均优于HVNS;IVNS算法的最大方差为0.72,波动范围小,求解性能稳定。IVNS的扰动方案对现有方案的扰动较小,能有效跳出当前局部最优,增强变邻域搜索算法的优化能力,与HVNS算法相比,其求解性能更优。     

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.     

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.     

A constraint programming based column generation approach to nurse rostering problems

This paper presents our investigations on a hybrid constraint programming based column generation (CP–CG) approach to nurse rostering problems. We present a complete model to formulate all the complex real-world constraints in several benchmark nurse rostering problems. The hybrid CP–CG approach is featured with not only the effective relaxation and optimality reasoning of linear programming but also the powerful expressiveness of constraint programming in modeling the complex logical constraints in nurse rostering problems. In solving the CP pricing subproblem, we propose two strategies to generate promising columns which contribute to the efficiency of the CG procedure. A Depth Bounded Discrepancy Search is employed to obtain diverse columns. A cost threshold is adaptively tightened based on the information collected during the search to generate columns of good quality. Computational experiments on a set of benchmark nurse rostering problems demonstrate a faster convergence by the two strategies and justify the effectiveness and efficiency of the hybrid CP–CG approach.     

A hybrid optimization approach to conformance testing of finite automata

Unique Input–Output sequences (UIOs) are quite commonly used in conformance testing. Unfortunately finding UIOs of minimal length is an NP hard problem. This study presents a hybrid approach to generate UIOs automatically on a basis of the finite state machine (FSM) specification. The proposed hybrid approach harnesses the benefits of hill climbing (Greedy search) and heuristic algorithm. Hill climbing, which exploits domain knowledge, is capable of quickly generating good result however it may get stuck in local minimum. To overcome the problem we used a set of parameters called the seed, which allows the algorithm to generate different results for a different seed. The hill climbing generates solutions implied by the seed while the Genetic Algorithm is used as the seed generator. We compared the hybrid approach with Genetic Algorithm, Simulated Annealing, Greedy Algorithm, and Random Search. The experimental evaluation shows that the proposed hybrid approach outperforms other methods. More specifically, we showed that Genetic Algorithm and Simulated Annealing exhibit similar performance while both of them outperform Greedy Algorithm. Finally, we generalize the proposed hybrid approach to seed-driven hybrid architectures and elaborate on how it can be adopted to a broad range of optimization problems.     

A case study of memetic algorithms for constraint optimization

There is a variety of knapsack problems in the literature. Multidimensional 0–1 knapsack problem (MKP) is an NP-hard combinatorial optimization problem having many application areas. Many approaches have been proposed for solving this problem. In this paper, an empirical investigation of memetic algorithms (MAs) that hybridize genetic algorithms (GAs) with hill climbing for solving MKPs is provided. Two distinct sets of experiments are performed. During the initial experiments, MA parameters are tuned. GA and four MAs each using a different hill climbing method based on the same configuration are evaluated. In the second set of experiments, a self-adaptive (co-evolving) multimeme memetic algorithm (MMA) is compared to the best MA from the parameter tuning experiments. MMA utilizes the evolutionary process as a learning mechanism for choosing the appropriate hill climbing method to improve a candidate solution at a given time. Two well-known MKP benchmarks are used during the experiments.     

A memetic algorithm with adaptive hill climbing strategy for dynamic optimization problems

Dynamic optimization problems challenge traditional evolutionary algorithms seriously since they, once converged, cannot adapt quickly to environmental changes. This paper investigates the application of memetic algorithms, a class of hybrid evolutionary algorithms, for dynamic optimization problems. An adaptive hill climbing method is proposed as the local search technique in the framework of memetic algorithms, which combines the features of greedy crossover-based hill climbing and steepest mutation-based hill climbing. In order to address the convergence problem, two diversity maintaining methods, called adaptive dual mapping and triggered random immigrants, respectively, are also introduced into the proposed memetic algorithm for dynamic optimization problems. Based on a series of dynamic problems generated from several stationary benchmark problems, experiments are carried out to investigate the performance of the proposed memetic algorithm in comparison with some peer evolutionary algorithms. The experimental results show the efficiency of the proposed memetic algorithm in dynamic environments.