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

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

考虑公平和护士偏好的护士排班研究

针对护士排班问题涉及护士满意度的特点，在护士排班过程中加入护士偏好和公平的约束，寻求最优的排班表以增加护士的满意度。根据多目标问题的特点，采用粒子群多目标优化算法。在硬约束条件上，加入N班之后不能上A班和P班的约束，使护士在上N班之后能够得到足够的休息。在算法设计上，加入变异算子，扩大了粒子群的搜索空间。由于各优化目标之间存在一定的矛盾，用多目标决策理论可以更加科学客观地优化护士排班表。在最后的案例分析中，发现护士不同的偏好会产生不同的非劣解，因此在实际排班中，要充分考虑护士的偏好，以求出更加科学合理的排班表。     

生产作业排程单道工序的模拟仿真算法研究

依据现实世界生产系统的实际运作情况,设计了一种单道工序作业排程的模拟仿真算法,相对于其他一些排程算法,该算法能比较准确真实的描绘生产系统机台作业的运行情况,准确得出作业的开始运行时间,结束时间及机台能力负荷状况。该算法运用于某实际ERP系统的生产实践表明:该算法能全面提高生产效率和机器设备使用率,为实际现场排程提供客观依据。     

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

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

呼叫中心排班优化模型的研究

呼叫中心排班系统的优化研究是在话务员和坐席资源约束下,根据服务需求时间序列,合理安排资源,以提高呼叫接入服务质量、提高话务员的个性化满意度和降低运营成本的多目标复杂约束的优化问题。根据客服质量与话务员满意度相关的指标和约束,引入了服务水平、排班成本、话务员疲劳度、排班公平性和话务员意愿等因素。基于对满足服务水平的班组数量的预测,依据对外的规划经营和对内的管理调度的区别,将排班决策分为班次设计和班组指派两大具有递进关系的子模型。利用改进型PSO算法和旋转排班法进行求解,并且根据排班结果和评价参数对规划调度参数进行反馈调整。最后通过仿真分析说明了本文方法在兼顾客服满意度和话务员满意度的呼叫中心排班决策系统中有很好的适应性。     

带约束的清洁排班问题模型及其求解

保洁服务公司的清洁任务往往具有不同级别、不同时长和不同周期等特点,缺乏通用清洁排班问题模型,现阶段主要依赖人工排班方案,存在耗时费力且排班质量不稳定等问题。因此提出了属于NP难问题的带约束的清洁排班问题的数学模型,并使用模拟退火算法（SA）、蜂群算法（BCO）、蚁群算法（ACO）和粒子群优化算法（PSO）对该模型进行求解,最后以某清洁服务公司实际排班情况进行了实证分析。实验结果表明,与人工排班方案进行对比,启发式智能优化算法求解带约束的清洁排班问题具有明显优势,获得的清洁排班表的人力需求明显减少。具体来说,在一年排班周期内这些算法比人工排班方案可节省清洁人力218.62~513.30 h。可见基于启发式智能优化算法的数学模型对带约束的清洁排班问题的求解可行且有效,能为保洁服务公司提供科学管理的决策支持。     

多约束条件下生产排程智能优化技术

针对当前企业智能化生产中,多条工艺路线共享工序以及工单在生产过程中具有多个约束条件(如工期、优先级、产量等)的问题,提出了一种以“等待时间最短”为主的生产排程智能优化算法。综合考虑工单优先级、工期长短和紧急任务插单等因素,通过一种递归算法来计算工单等待时间,以最小化工单完成时间、最大化资源利用率为优化目标,建立了多约束条件下紧急工单处理的快速响应机制。在服装加工企业中的实际应用表明,相比手工排程及其他传统算法,文中提出的优化排程算法不仅缩短了生产周期,力求各工序的负荷率最大化,使企业的生产效率提高了20%及以上,同时还改善了排程系统的稳定性。     

手术通知单申请与排班系统应用及分析

用电子手术通知单取代传统纸质单,利用信息化手段提高手术通知单申请效率,以提高手术相关科室的医疗质量,是现代医院手术室管理的必然趋势。文章介绍了手术通知单申请与排班系统的整个开发过程,详细描述了手术通知和排班中对各种条件的逻辑判断。系统的应用提高了临床工作质量及效率,基本实现手术管理自动化和手术资源信息的共享,也方便了手术科室合理安排手术间和参与人员。     

APS系统中基于改进的遗传算法的分布式排产研究

探讨了在分布式生产模式下,解决生产排程问题的新技术——APS（Advanced Planning and Scheduling）系统。系统利用PowerBuilder作为开发工具。实践证明,在APS的计划模型下,改进的遗传算法在解决分布式生产排程问题上具有良好的算法性能,并在某大型制药厂的实施中取得成功。     

基于进化算法的铝加工行业生产计划高级排程系统设计

现有排程系统存在加工时间长、加工效率低等问题，为此设计基于进化算法的铝加工行业生产计划高级排程系统。首先，根据铝加工行业生产线分钟级别的生产排程及系统运行需要，设计高级排程系统框架结构；其次，利用进化算法，完成铝加工行业生产车间调度；最后，在动态环境下，实现生产计划高级排程。实验结果表明，新的排程系统在实际应用中可以在更短的时间内完成加工任务。     

Maximizing the efficiency of use of nurses under uncertain surgery durations: A case study

This paper studies a nurse scheduling problem of assigning a set of nurses to surgeries scheduled on each workday in an operating room (OR) suite. This problem plays a decisive role in utilizing nurses efficiently, which is of paramount importance for OR suites to provide high-quality service at ever reduced cost. Due to significant uncertainty in surgery durations, designing schedules that achieve high nurse efficiency is complicated by the competing objective of ensuring on-time starts of surgeries. For trading off between the two performance criteria, we formulate the problem as a mixed integer programming (MIP) model with explicit probability modeling of uncertainty. We are concerned about improving nurse efficiency in terms of overtime and idle time of nurses while mastering the risk of delay of surgeries. The MIP model is applied in a large size Chinese hospital, and the results are compared with the actual performance of the OR suite. The comparisons reveal that through examining the trade-off between the performance criteria, important nurse efficiency improvements can be achieved with good on-time start performance. Moreover, the applicability of the MIP model in various problem settings is also investigated.     

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.     

基于单亲遗传禁忌搜索算法的手术排程问题研究

针对规模较大的手术排程问题,分别以所有病人完成手术过程的最长时间和平均时间最小化为目标,构建了手术排程问题的数学模型。在分析解的最优化条件基础上,设计了一种将单亲遗传算法与禁忌搜索算法相结合的混合优化算法。按照个体的优劣及算法迭代情况设计了一种自适应选择机制,使个体自适应地选择执行变异操作或禁忌搜索算法。最后,仿真实验结果表明了所提算法的有效性和自适应选择机制的可行性。     

考虑患者分类的应急手术调度研究

针对公众突发事件背景下应急手术调度效率及救治率低下等问题,将应急手术调度问题看作三级混合流水车间调度问题,在考虑患者三级分类的同时,综合考虑患者的恶化效应与手术团队的学习效应因素,构建以平均完成手术时间、患者恶化成本和手术室总能耗为优化目标的多目标应急手术调度模型。针对布谷鸟算法易陷入局部寻优的缺点,设计了一种被发现概率自适应的布谷鸟算法对应急手术的调度模型进行求解。最后通过仿真实验验证了模型和算法的有效性。     

Local and global constraint consistency in personnel rostering

Personnel rostering is a challenging combinatorial optimization problem in which shifts are assigned to employees over a scheduling period while subject to organizational, legislative, and personal constraints. Academic models for personnel rostering typically abstractly conceptualize complex real‐world problem characteristics. Often only one isolated scheduling period is considered, contradicting common practice where personnel rostering inherently spans multiple dependent periods. The state of the art offers no systematic approach to address this modeling challenge, and consequently, few models capture the requirements imposed by practice. The present paper introduces the concepts of local and global consistency in constraint evaluation processes and proposes a general methodology to address these challenges in integer programming approaches. The impact of inconsistent constraint evaluation is analyzed in a case study concerning rostering nurses in a hospital ward, of which the data have been made publicly available. The results demonstrate that the proposed methodology approximates the optimal solution.     

A hybrid genetic approach for solving an integrated multi-objective operating room planning and scheduling problem

In this paper, we propose a multi-objective integer linear programming model aiming at efficiently planning and managing hospital operating room suites. By effectively exploiting a novel hybrid genetic solution approach, the devised optimization model is able to determine, in an integrated way, (i) the operating room time assigned to each surgical specialty, (ii) the operating room time assigned to each surgical team, (iii) the surgery admission planning and (iv) the surgery scheduling. The resulting Pareto frontiers provide a set of “optimal” solutions able to support hospital managers in efficiently orchestrating the involved resources and planning surgeons and surgeries. On this basis, the proposed solution framework could represent a suitable engine for the development of advanced and effective health care management decision support systems.     

基于分布式神经动态优化的综合能源系统多目标优化调度EI北大核心CSCD

研究了基于神经动态优化的综合能源系统(Integrated energy systems,IES)分布式多目标优化调度问题.首先,将IES元件单元(包含负荷)作为独立的决策主体,联合考量其运行成本和排放成本,并计及多能源设备间的传输损耗,提出了IES多目标优化调度模型,该模型可描述为一类非凸多目标优化问题.其次,针对此类问题的求解,提出了一种基于神经动力学系统的分布式多目标优化算法,该算法基于动态权重的神经网络模型,可以解决不可分离的不等式约束问题.该算法计算负担小,收敛速度快,并且易于硬件实现.仿真结果表明,所提算法能同时协调综合能源系统的经济性和环境性这两个冲突的目标,且获得了整个帕累托前沿,有效降低了综合能源系统的污染物排放量和综合运行成本.     

Operating room scheduling with Generalized Disjunctive Programming

This paper addresses the short-term scheduling problem involved in the selection of a subset of elective surgeries from a large waiting list. In order to overcome the combinatorial complexity, a decomposition algorithm is proposed that relies on two continuous-time Generalized Disjunctive Programming (GDP) models. More specifically, there is an upper-level planning model to select surgical assignments to operating rooms and a lower-level constrained scheduling model to synchronize surgeons operating in different rooms on a given day. The GDP models are reformulated using standard convex hull and big-M techniques so as to generate the most efficient set of integer or mixed-integer linear programming constraints. Through the solution of a set of real-life instances from the literature, we show that the new algorithm outperforms a full-space discrete-time formulation and a genetic algorithm, improving the total surgical time as well as the number of performed surgeries by 5%.     

Operating room management under uncertainty

The operating room management problems are legion. This paper tackles the scheduling of surgical procedures in an operating theatre containing up to two operating rooms and two surgeons. We first solve a deterministic version that uses the constraint programming paradigm and then a stochastic version which embeds the former in a sample average approximation scheme. The latter produces more robust schedules that cope better with the surgeries’ time variability