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.     

带约束的护士排班模型和基于变换规则的优化算法

护士排班是医院不可或缺并且需要反复进行的工作,排班方案的优劣对医院的护理质量、运作成本、护士心身健康、工作积极性等产生重大影响。针对我国护士排班问题缺乏通用模型和排班手段落后的问题,本文首先建立了一个带有一系列劳动法规约束和护士级别差异约束的整数规划模型,该问题被公认为是NP问题;然后增加护士请假约束和护士对工作时段偏好以及护士间配合默契程度的软约束,建立了一个更加人性化的扩展模型;随后设计了一系列变换规则,研制出一个护士优化排班算法。实例验证该模型与算法是可行且有效的,并且扩展模型更受欢迎,有利于提高护士积极性和工作效益。     

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.     

Enhanced genetic algorithms for a bi‐objective bus driver rostering problem: a computational study

In this work, the bus driver rostering problem is considered in the context of a noncyclic rostering, with two objectives representing either the company or the drivers’ interests. A network model and a proof of the NP‐hardness of the problem are presented, along with a bi‐objective memetic algorithm that combines a specific decoder with a utopian/lexicographic elitism, a strength Pareto fitness evaluation, and a local search procedure. By taking real and benchmark instances the computational behavior of the memetic algorithm is compared with simpler versions to assess the effects of the embedded components. The developed algorithm is a valuable tool for bus companies’ planning departments insofar as it yields at low computing times a pool of good quality rosters that reconcile contradictory objectives. This study shows that simple enhancements in standard bi‐objective genetic algorithms may improve the results for this difficult combinatorial problem.     

A Heuristic Approach to the Inverse Differential Kinematics Problem

Inversion of the kinematics of manipulators is one of the central problems in the field of robot arm control. The iterative use of inverse differential kinematics is a popular method of solving this task. Normally the solution of the problem requires a complex mathematical apparatus. It involves methods for solving equation systems as well as algorithms for optimization. In this paper we introduce a naïve heuristic method which works without the need for complex mathematical algorithms. This method forms a simple basis for the more sophisticated control procedures of our robot manipulator (JANUS).     

Automated Manpower Rostering: Techniques and Experience

We present ROMAN, a comprehensive, generic manpower rostering toolkit that successfully handles a wide spectrum of work policies found in service organizations. We review the use of various techniques and methodologies in the toolkit that contribute to its robustness and efficiency, and relate experience gained in addressing manpower rostering problems in industry.     

资源受限工程调度问题的优化方法综述

由于资源受限的工程调度问题在理论上和实际中具有重要意义,近年来,国内外关于这一问题的优化方法有了较大的发展,因此根据收集到的资料,对求解这一问题的分支定界算法、基于优先规则的启发式算法、样本算法以及智能优化算法的最新发展进行简要概述,并指出了该问题未来的研究方向.     

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

An AND/OR-graph Approach to the Container Loading Problem

The container loading problem consists of packing boxes of various sizes into available containers in such a way as to optimize an objective function. In this paper we deal with the special case where there is just one available container and the objective is to maximize the total volume (or the total utility value, supposing that each box has a utility value) of the loaded boxes. We firstly present three heuristic solution methods for the unconstrained problem. Two of them solve the original three-dimensional problem by layers and by stacks reducing it into several problems with lower dimensions. The third one consists of representing possible loading patterns as complete paths in an AND/OR-graph. Bounds and heuristics are proposed in order to reduce the solution space. A proper heuristic is also given to treat the constrained problem by using the AND/OR-graph approach. Moreover, computational results are presented by solving a number of examples.     

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

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

Constructing nurse schedules at large hospitals

Several heuristics, based on evolutive algorithms and local search, are used to solve the nurse scheduling problem at a large hospital. Due to several intricate and specific restrictions imposed on the schedules, the problem is a difficult one to solve by hand. Moreover, some of the restrictions have a subjective value attached to them, and this constrains the use of exact methods that search for global optima. In order to facilitate the use of the solver modules by the hospital staff, a user interface was also implemented.     

一种基于模拟退火的多目标Memetic算法

为了改善多目标进化算法的搜索效率，提出了基于模拟退火的多目标Memetic算法．此算法根据Pareto占优关系评价个体适应值，采用模拟退火进行局部搜索，并结合交叉算子和基于网格密度的选择机制改善算法的收敛速度和解的均衡分布．flowshop调度问题算例的仿真结果表明，基于模拟退火的多目标Memetic算法能够产生更接近Pareto前沿的近似集．     

基于关键链的资源受限项目调度新方法

针对资源受限项目调度问题（RCPSPs）的实际需求建立了多目标优化调度模型,综合运用现有研究成果,设计了基于关键链的项目调度方法。该方法首先采用基于优先规则的启发式算法生成工期最小的近优项目计划,再在该计划中嵌入输入缓冲和项目缓冲,保证项目计划在非确定环境下的稳定执行。论文引用RCPSPs的标准问题库PSPLIB中大量案例对算法进行了的仿真试验,结果表明本文方法较传统项目调度方法有很大改进,论文最后对仿真结果进行了深入讨论,并指出了未来的研究方向。     

A Bayesian Approach to Batch Process Scheduling

The problem of decision timing in the context of batch scheduling is addressed in this paper. The representation of time in any scheduling model affects the number of integer variables and the convexity of the model. The usual procedure in batch process scheduling is to divide the scheduling horizon into equal size intervals to achieve the required accuracy. This construction generates a formulation with a potentially large number of binary variables. In this paper, the time events arising in the schedule are modeled directly, and thus the use of binary variables over periods during which no changes in system state occur is avoided. The problem is formulated as a mixed integer nonlinear program (MINLP). The Bayesian heuristic (BH) approach is used to implement a global optimization algorithm which effectively solves the resulting model. Computational comparisons using two text examples are made against a UDM (uniform discretization model) formulation. The results suggest that the BH approach combined with the nonuniform time discretization formulation shows promise for the solution of batch scheduling problems.     

文化基因算法求解TSP问题的研究

TSP是组合优化问题中著名的NP-hard问题。针对粒子群算法求解离散的TSP问题收敛速度慢,求解精度低,易于陷入局部最优和模拟退火算法的性能与参数初始值有关及参数敏感等不足,提出了将改进的粒子群算法作为全局搜索策略,改进的模拟退火算法作为局部搜索策略的文化基因算法。介绍了两种算法的协同方法,定义了局部搜索邻域的确定以及在新种群产生中引入自组织随机移民策略。仿真结果表明,改进算法在求解TSP问题中具有很快的收敛速度,且能搜索到最优解。     

多目标柔性车间调度的文化基因非支配排序粒子群算法

本文以离散型柔性制造车间为对象, 以缩短生产周期、减少机器空转时间和提高产品合格率为优化目标, 提出一种文化基因非支配排序粒子群算法. 该算法采用二维编码方式. 首先, 分别对工序和机器分配进行不同的变异操作, 建立了多目标离散型资源优化调度模型. 然后, 采用非支配排序策略和随机游走法获得Pareto最优解, 接着利用层次分析法给出资源优化配置方案. 最后, 利用实际生产数据进行仿真, 结果表明所提出的优化算法具有平衡全局搜索能力和局部搜索能力的特性.     

同构计算环境中一种快速有效的静态任务调度算法

快速有效的调度任务是多处理器计算环境中的一个关键问题. 目前任务调度算法中刻画任务依赖关系最流行的模型是DAG. 在以前的文献中, 提出了一种新的更实际、更普遍的TTIG模型及其相应的MATE算法(基于同构计算环境). 延伸了TTIG模型, 并提出基于同构系统的新的算法及两种启发式方法(GBHA1和GBHA2). GBHA以组的形式尽量消除图中回路,因而能获得任务图的全局信息,具有更好的调度性能. 在模拟实验中,将此算法与MATE和其他同构环境中基于DAG的有效调度算法,在不同测试条件下进行了比较,结果显示GBHA在性能上明显优于MATE,与基于DAG模型的调度算法比较而言,在性能方面各有千秋,但在算法时间复杂度方面具有显著的优势.     

A Matrix-Based Approach to the Image Moment Problem

An image can be seen as an element of a vector space and hence it can be expressed in as a linear combination of the elements of any non necessarily orthogonal basis of this space. After giving a matrix formulation of this well-known fact, this paper presents a reconstruction method of an image from its moments that sheds new light on this inverse problem. Two main contributions are presented: (a) the results using the standard approach based on the least squares approximation of the result using orthogonal polynomials can also be obtained using matrix pseudoinverses, which implies higher control on the numerical stability of the problem; and (b) it is possible to use basis functions in the reconstruction different from orthogonal polynomials, such as Fourier or Haar basis, allowing to introduce constraints relative to the bandwidth or the spatial resolution on the image to be reconstructed. Judit Martònez received the B.Sc. degree in 1993 and the PhD degree (with honors) in 1998, both in telecommunications engineering from the Technical University of Catalonia. She developed her research at the Institut de Robútica i Informütica Industrial of the Spanish High Council for Scientific Research. In 1999 she joined the Computer Vision Center, a R&D center founded by the Autonomous University of Barcelona and the Autonomous Government of Catalonia. She has been principal researcher of several industrial and research projects related to computer vision technologies. Her research interests include industrial applications of machine vision, efficient algorithms for low-level image processing, multiresolution mathematical models, statistical clustering, pattern classification and inverse problems. Josep M. Porta received the Engineer Degree in Computer Science in 1994 and the Ph.D. in Artificial Intelligence in 2001, both from the Technical University of Catalonia (UPC). After that, he joined the IAS group of the University of Amsterdam and currently, he holds a post-doc position at the Institut de Robútica i Informütica Industrial (CSIC-UPC) in Barcelona. He carried research in legged robots, machine learning, vision-based methods for autonomous robot localization, and computational kinematics. Federico Thomas is Research Professor at the Spanish Scientific Research Council (CSIC) and director of the Institut de Robútica i Informütica Industrial (CSIC-UPC), Barcelona, Spain. He received the telecommunications engineering degree in 1984, and the Ph.D. degree (with honors) in computer science in 1988, both from the Technical University of Catalonia (UPC). In 1991, he won a NATO postdoctoral scholarship at the University of Massachusetts with the late Prof. Robin Popplestone. In 1999, he was visiting professor, sponsored by the Autonomous Government of Catalonia, at the Oxford University Computing Laboratory with Prof. Stephen Cameron. He has been project leader of several national projects financed by the Spanish Committee for Science and Technology (CICYT), and by local companies such as ENHER, a power generation company now part of ENDESA. His current research interests are in Geometry and Kinematics with applications to Robotics, Computer Graphics and Computer Vision. Prof. Thomas is an Associate Editor of the IEEE Transactions on Robotics.     

A Stochastic Limit Approach to the SAT Problem

There exists an important problem whether there exists an algorithm to solve an NP-complete problem in polynomial time. In this paper, a new concept of quantum adaptive stochastic systems is proposed, and it is shown that it can be used to solve the problem above.