Using stochastic programming to solve an outpatient appointment scheduling problem with random service and arrival times

We study a stochastic outpatient appointment scheduling problem (SOASP) in which we need to design a schedule and an adaptive rescheduling (i.e., resequencing or declining) policy for a set of patients. Each patient has a known type and associated probability distributions of random service duration and random arrival time. Finding a provably optimal solution to this problem requires solving a multistage stochastic mixed‐integer program (MSMIP) with a schedule optimization problem solved at each stage, determining the optimal rescheduling policy over the various random service durations and arrival times. In recognition that this MSMIP is intractable, we first consider a two‐stage model (TSM) that relaxes the nonanticipativity constraints of MSMIP and so yields a lower bound. Second, we derive a set of valid inequalities to strengthen and improve the solvability of the TSM formulation. Third, we obtain an upper bound for the MSMIP by solving the TSM under the feasible (and easily implementable) appointment order (AO) policy, which requires that patients are served in the order of their scheduled appointments, independent of their actual arrival times. Fourth, we propose a Monte Carlo approach to evaluate the relative gap between the MSMIP upper and lower bounds. Finally, in a series of numerical experiments, we show that these two bounds are very close in a wide range of SOASP instances, demonstrating the near‐optimality of the AO policy. We also identify parameter settings that result in a large gap in between these two bounds. Accordingly, we propose an alternative policy based on neighbor‐swapping. We demonstrate that this alternative policy leads to a much tighter upper bound and significantly shrinks the gap.     

Relaxed sequencing games have a nonempty core

We study sequencing situations with a fixed initial order and linear cost functions. Cost savings can be obtained by rearranging jobs. Next to finding an optimal order, an additional issue is formed by the division of these savings. Cooperative game theory studies this issue. A common assumption states that cooperation between players is restricted to groups that are connected according to the initial order. The value of disconnected groups is defined additively over their connected components. In this paper we allow players in disconnected coalitions to switch places as long as they do not hurt the players not in the coalition under consideration. The resulting games are called relaxed sequencing games. Although they have been studied before, no general results on stable profit divisions have been derived so far. In this paper we prove that relaxed sequencing games have a nonempty core, i.e., they all have stable profit divisions. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Approximation algorithms for minimizing total weighted completion time of orders on identical machines in parallel

We consider the problem of scheduling orders on identical machines in parallel. Each order consists of one or more individual jobs. A job that belongs to an order can be processed by any one of the machines. Multiple machines can process the jobs of an order concurrently. No setup is required if a machine switches over from one job to another. Each order is released at time zero and has a positive weight. Preemptions are not allowed. The completion time of an order is the time at which all jobs of that order have been completed. The objective is to minimize the total weighted completion time of the orders. The problem is NP‐hard for any fixed number (≥2) of machines. Because of this, we focus our attention on two classes of heuristics, which we refer to as sequential two‐phase heuristics and dynamic two‐phase heuristics. We perform a worst case analysis as well as an empirical analysis of nine heuristics. Our analyses enable us to rank these heuristics according to their effectiveness, taking solution quality as well as running time into account. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Maximizing project cash availability

Consider a project during the life cycle of which there are cash payouts and in‐flows. To better meet his financial commitments, the project owner would like to meet all deadlines without running out of cash. We show that the cash availability objective is similar to the total weighted flowtime used to measure work‐in‐progress performance in the scheduling and inventory control literatures. In this article we provide several specialized solution methods for the problem of minimizing total weighted flowtime in an arbitrary acyclic project network, subject to activity release times and due dates, where the activity weights may be positive or negative and represent cash in‐ and out‐flows. We describe the structure of an optimal solution and provide several efficient algorithms and their complexity based on mincost and maxflow formulations. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

基于蚁群算法的试验流程优化研究

水中兵器的海上试验涉及许多人员、兵力、被试产品、测量设备等,试验周期长、消耗大,因此如何缩短试验周期是亟待研究解决的问题.文中首先将试验流程优化问题转化为车间调度问题,建立了相应的数学模型,再应用蚁群算法转移规则得到中间结果并进行排队以对各种资源约束进行处理.最后将结果利用局部搜索算法优化后作为蚁群算法信息素更新的基础.实例计算结果表明,该方法优化效果良好.     

土中爆炸对埋地管线冲击作用的数值模拟分析

为了研究土中爆炸作用下埋地管线的安全问题,利用AUTODYN-2D、AU?TODYN-3D程序,采用程序提供的流固耦合功能和网格映射功能,对爆炸地冲击作用下埋地管线的变形和破坏问题进行了数值模拟分析,得到不同爆心间距管线的应力峰值.将模拟计算结果和理论计算结果进行了对比分析,结果表明:模拟计算值与TM5-855-1手册理论计算值比较吻合,表明采用数值模拟方法分析爆炸地冲击对埋地管线的作用是可行的,计算结果对地下爆破的安全施工和埋地管线的安全运行具有参考价值.     

基于逆向强化学习的舰载机甲板调度优化方案生成方法

针对计算机辅助指挥调度舰载机甲板作业的决策过程无法脱离人参与这一特点,引入基于逆向学习的强化学习方法,将指挥员或专家的演示作为学习对象,通过分析舰载机的甲板活动,建立舰载机甲板调度的马尔可夫决策模型(MDP)框架;经线性近似,采用逆向学习方法计算得到回报函数,从而能够通过强化学习方法得到智能优化策略,生成舰载机甲板调度方案。经仿真实验验证,本文所提方法能够较好地学习专家演示,结果符合调度方案优化需求,为形成辅助决策提供了基础。     

基于PCA-RBF网络的储运过程管道堵塞故障诊断方法

针对现代储运过程管道堵塞故障诊断时,提取的过程参数多导致诊断速度慢、性能差等问题,提出了基于主成分分析（PCA）和径向基函数（RBF）神经网络故障的诊断方法。首先利用PCA方法对储运过程高维历史数据矩阵进行特征提取,提取的故障特征信息作为训练集,并给出故障特征信息的分类号;然后将其作为RBF神经网络分类器的输入输出进行故障模式识别。仿真实验表明：该方法应用于储运过程管道堵塞故障诊断,不仅大幅度地降低了诊断模型的训练时间,而且提高了诊断正确率。     

管道机器人在三通处的通过性分析

三通是管道机器人经常遇到的典型障碍之一,克服该障碍的能力用管道机器人在三通处通过性来描述。文中提出一种描述差压驱动式管道机器人三通通过性的数学模型,该模型由一组组合约束构成。通过对约束方程的分析讨论、与管道机器人弯道通过性的对比分析,得出了规律性的结论。管道机器人在三通处的姿态、单元体的几何尺寸、行走轮结构形式对其通过性都有不同程度的影响。所提出数学模型是管道机器人三通自主行走控制策略设计和相应结构设计的理论基础。     

C2组织结构设计:平台-任务关系设计

以联合作战战役为例建立作战平台和任务模型,对C2(Command and Control)组织结构设计中平台-任务关系设计问题分析了传统多维动态列表规划算法(Multidimensional Dynamic List Scheduling,MDLS)在解决作战平台资源调度(平台-任务分配)问题的不足,提出了在平台-任务分配过程中采用任务选择平台组、平台选择任务以及两者选择冲突消除改进的MDLS算法,以解决MDLS算法的不足,并对不同方法的结果进行了比较.