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.     

Engineering an efficient two‐phase local search algorithm for the co‐rotating twin‐screw extruder configuration problem

The twin‐screw configuration problem arises during polymer extrusion and compounding. It consists in defining the location of a set of pre‐defined screw elements along the screw axis in order to optimize different, typically conflicting objectives. In this paper, we present a simple yet effective stochastic local search (SLS) algorithm for this problem. Our algorithm is based on efficient single‐objective iterative improvement algorithms, which have been developed by studying different neighborhood structures, neighborhood search strategies, and neighborhood restrictions. These algorithms are embedded into a variation of the two‐phase local search framework to tackle various bi‐objective versions of this problem. An experimental comparison with a previously proposed multi‐objective evolutionary algorithm shows that a main advantage of our SLS algorithm is that it converges faster to a high‐quality approximation to the Pareto front.     

Solving bus terminal location problems using evolutionary algorithms

Bus terminal assignment with the objective of maximizing public transportation service is known as bus terminal location problem (BTLP). We formulate the BTLP, a problem of concern in transportation industry, as a p-uncapacitated facility location problem (p-UFLP) with distance constraint. The p-UFLP being NP-hard (Krarup and Pruzan, 1990), we propose evolutionary algorithms for its solution. According to the No Free Lunch theorem and the good efficiency of the distinctive preserve recombination (DPX) operator, we design a new recombination operator for solving a BTLP by new evolutionary and memetic algorithms namely, genetic local search algorithms (GLS). We also define the potential objective function (POF) for the nodes and design a new mutation operator based on POF. To make the memetic algorithm faster, we estimate the variation of the objective function based on POF in the local search as part of an operator in memetic algorithms. Finally, we explore numerically the performance of nine proposed algorithms on over a thousand randomly generated problems and select the best two algorithms for further testing. The comparative studies show that our new hybrid algorithm composing the evolutionary algorithm with the GLS outperforms the multistart simulated annealing algorithm.     

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.     

A hybrid memetic algorithm for maximizing the weighted number of just-in-time jobs on unrelated parallel machines

This paper presents a hybrid memetic algorithm for the problem of scheduling n jobs on m unrelated parallel machines with the objective of maximizing the weighted number of jobs that are completed exactly at their due dates. For each job, due date, weight, and the processing times on different machines are given. It has been shown that when the numbers of machines are a part of input, this problem is NP-hard in the strong sense. At first, the problem is formulated as an integer linear programming model. This model is practical to solve small-size problems. Afterward, a hybrid memetic algorithm is implemented which uses two heuristic algorithms as constructive algorithms, making initial population set. A data oriented mutation operator is implemented so as to facilitate memetic algorithm search process. Performance of all algorithms including heuristics (H1 and H2), hybrid genetic algorithm and hybrid memetic algorithm are evaluated through computational experiments which showed the capabilities of the proposed hybrid algorithm.     

Adaptive memetic algorithm for minimizing distance in the vehicle routing problem with time windows

This paper presents an adaptive memetic algorithm to solve the vehicle routing problem with time windows (VRPTW). It is a well-known NP-hard discrete optimization problem with two objectives—to minimize the number of vehicles serving a set of geographically dispersed customers, and to minimize the total distance traveled in the routing plan. Although memetic algorithms have been proven to be extremely efficient in solving the VRPTW, their main drawback is an unclear tuning of their numerous parameters. Here, we introduce the adaptive memetic algorithm (AMA-VRPTW) for minimizing the total travel distance. In AMA-VRPTW, a population of solutions evolves with time. The parameters of the algorithm, including the selection scheme, population size and the number of child solutions generated for each pair of parents, are adjusted dynamically during the search. We propose a new adaptive selection scheme to balance the exploration and exploitation of the solution space. Extensive experimental study performed on the well-known Solomon’s and Gehring and Homberger’s benchmark sets confirms the efficacy and convergence capabilities of the proposed AMA-VRPTW. We show that it is very competitive compared with other state-of-the-art techniques. Finally, the influence of the proposed adaptive schemes on the AMA-VRPTW behavior and performance is investigated in a thorough sensitivity analysis. This analysis is complemented with the two-tailed Wilcoxon test for verifying the statistical significance of the results.     

A memetic algorithm-based heuristic for a scheduling problem in printed circuit board assembly

This research develops a memetic algorithm to solve Printed Circuit Board (PCB) scheduling with sequence-dependent setup times on a single machine with constrained feeder capacity. The objective of the scheduling problem is to minimize the total weighted tardiness. A memetic algorithm-based heuristics is developed by integrating a genetic algorithm, Minimum Slack Time (MST) scheduling rule, “Keep Tool Needed Soonest” (KTNS) policy, and a local search procedure. Application of the MA results in two outcome plans: a scheduling plan and a feeder setup plan.Numerical experiments show that compared to a number of commonly used dispatching rules, the memetic algorithm provides better solutions in term of minimum total weighted tardiness. Even the computation is the highest, it still practical. Calibration of MA parameter values is also explored in this study.     

A hybrid metaheuristic case-based reasoning system for nurse rostering

In this paper we present a novel Case-Based Reasoning (CBR) system called CABAROST (CAsed-BAsed ROSTering) which was developed for personnel scheduling problems. CBR is used to capture and store examples of personnel manager behaviour which are then used to solve future problems. Previous examples of constraint violations in schedules and the repairs that were used to solve the violations are stored as cases. The sequence in which violations are repaired can have a great impact on schedule quality. A novel memetic algorithm is proposed which evolves good quality sequences of repairs generated by CABAROST. The algorithm was tested on instances of the real-world nurse rostering problem at the Queens Medical Centre NHS Trust in Nottingham.     

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.     

带时间窗车辆路径问题的多目标文化基因算法

针对物流配送中带时间窗的车辆路径问题,以最小化车辆使用数和行驶距离为目标,建立了多目标数学模型,提出了一种求解该问题的多目标文化基因算法。种群搜索采用遗传算法的进化模式和Pareto排序的选择方式,局部搜索采用禁忌搜索机制和存储池的结构,协调两者得到的Pareto非占优解的关系。与不带局部搜索的多目标遗传算法和单目标文化基因算法的对比实验表明,本文算法的求解质量较高。     

Optimizing a bi‐objective vehicle routing problem that appears in industrial enterprises

In this paper, a new solution method is implemented to solve a bi‐objective variant of the vehicle routing problem that appears in industry and environmental enterprises. The solution involves designing a set of routes for each day in a period, in which the service frequency is a decision variable. The proposed algorithm, a muti‐start multi‐objective local search algorithm (MSMLS), minimizes total emissions produced by all vehicles and maximizes the service quality measured as the number of times that a customer is visited by a vehicle in order to be served. The MSMLS is a neighbourhood‐based metaheuristic that obtains high‐quality solutions and that is capable of achieving better performance than other competitive algorithms. Furthermore, the proposed algorithm is able to perform rapid movements thanks to the easy representation of the solutions.     

A multistage approach for an employee timetabling problem with a high diversity of shifts as a solution for a strongly varying workforce demand

This work deals with the employee rostering problem at the airport. Such problems, related to the time varying demand of the transport services, use many (e.g., about a hundred) diverse shifts to cover the workforce demand during the day. Together with the strict constraints, given by the collective agreement, the problem becomes difficult to solve. Algorithms commonly used for solving the usual employee rostering problems produce poor quality rosters, which are unusable in practice. This paper suggests a three stage approach allowing one to solve the employee rostering problems where a huge set of different shifts is used to satisfy the coverage requirements. The solution is based on the problem transformation to a simpler problem, thereupon, an evolutionary algorithm is used to determine a rough position of the shifts in the roster. Afterwards, the maximal weighted matching in the bipartite graph is applied as the inverse transformation of the problem and the final roster is obtained by the optimization based on a Tabu Search algorithm. This multistage approach is compared to other approaches. Furthermore, an evaluation methodology was proposed in order to make a complex and fair comparison. Its objective is to verify the contribution of the particular stages used in the different approaches applied on the different personnel scheduling problems.     

Solving the bi‐objective capacitated p‐median problem with multilevel capacities using compromise programming and VNS

A bi‐objective optimisation using a compromise programming (CP) approach is proposed for the capacitated p‐median problem (CPMP) in the presence of the fixed cost of opening facility and several possible capacities that can be used by potential facilities. As the sum of distances between customers and their facilities and the total fixed cost for opening facilities are important aspects, the model is proposed to deal with those conflicting objectives. We develop a mathematical model using integer linear programming (ILP) to determine the optimal location of open facilities with their optimal capacity. Two approaches are designed to deal with the bi‐objective CPMP, namely CP with an exact method and with a variable neighbourhood search (VNS) based matheuristic. New sets of generated instances are used to evaluate the performance of the proposed approaches. The computational experiments show that the proposed approaches produce interesting results.     

Assignment of cells to switches in cellular mobile network: a learning automata-based memetic algorithm

Handoff and cabling costs management plays an important role in the design of cellular mobile networks. Efficient assigning of cells to switches can have a significant impact on handoff and cabling cost. Assignment of cells to switches problem (ACTSP) in cellular mobile network is NP-hard problem and consequently cannot be solved by exact methods. In this paper a new memetic algorithm which is obtained from the combination of learning automata (LA) and local search is proposed for solving the ACTSP in which the learning automata keeps the history of the local search process and manages the problem’s constraints. The proposed algorithm represents chromosome as object migration automata (OMAs), whose states represent the history of the local search process. Each state in an OMA has two attributes: the value of the gene (allele), and the degree of association with those values. The local search changes the degree of association between genes and their values. To show the superiority of the proposed algorithm several computer experiments have been conducted. The obtained results confirm the efficiency of proposed algorithm in comparison with the existing algorithms such as genetic algorithm, memetic algorithm, and a hybrid Hopfield network-genetic algorithm.     

基于自适应Memetic算法的多目标复杂网络社区检测

针对提高复杂网络社区检测准确度问题, 提出了一种自适应Memetic算法的多目标社区检测算法。在全局搜索中利用Logistic函数来设置与全局优化相应的交叉概率和变异概率,并将多目标优化问题转化成同时最小优化Kernel K-Means和Ratio Cut这两个目标函数;在局部搜索中利用权重将两个目标函数合并成一个局部优化目标,并采用爬山搜索来寻找个体最优。在虚拟和真实网络实验平台下,与五个基于遗传算法的方法以及Fast Modularity算法相比,结果表明算法能有效提高社区检测准确度,具有更好的寻优效果。     

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.     

电子就业中介中的匹配研究

研究了电子就业中介中公司学生的双边匹配问题,并基于HR算法(医学院实习生与医院相互选择算法[1])建立了电子就业中介的工作流程模型。以交易双方总满意度分别最大为目标,建立了多目标指派模型,从而解决了传统HR算法的匹配公平性问题。以等权重的线性加权方法将问题化为单目标求解。仿真实验表明,该多目标算法虽不能保证匹配稳定性[2],但在匹配数量上优于HR算法。     

A bi‐objective mathematical model for product allocation in block stacking warehouses

Put‐away and picking operations in warehouses play a critical role in determining operating costs and customer response time. While the place where products are put away has an important effect on picking efficiency due to accessibility, it also affects space usage, which is critical for space availability and space costs. Hence, this study focuses on put‐away operations in pallet‐in pallet‐out block stacking warehouses. We develop a unique bi‐objective mathematical model and a constructive heuristic algorithm to allocate products to storage lanes while considering two objectives simultaneously: minimizing total travel distance and maximizing average storage usage. We test our model and heuristic through a real company case study and randomly generated large‐sized problem instances. We show that the model and heuristic offer better storage usage with reduced travel distance than the company's approach when the two objectives have equal weight. We also present a set of nondominated solutions for each problem instance. We present that the heuristic seems beneficial for the warehouse industry due to its short run time and effective solutions.     

A bi‐objective approach to reschedule new jobs in a one machine model

We consider a one machine scheduling model, minimizing a classical objective function—either the total completion time or the maximum tardiness—and with two sets of jobs: one with initial jobs already scheduled and one with new jobs that must be inserted in the schedule. As such rescheduling can create a modification of the schedule of the initial jobs, a disruption objective is considered in addition to the original objective. This additional objective can be formulated in four different ways. Such model has been introduced by Hall and Potts, minimizing either a linear aggregation of the two objectives or the initial objective under a constraint giving an upper limit of the disruption objective. In this paper, the aim is to obtain the set of efficient schedules in regard to the two objectives. Algorithms are provided for the eight possible bi‐objective problems and illustrated by some didactic examples.     

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.