Appointment scheduling at a multidisciplinary outpatient clinic using stochastic programming

The purpose of this paper is to investigate the problem of constructing an appointment template for scheduling patients at a specific type of multidisciplinary outpatient clinic called an integrated practice unit (IPU). The focus is on developing and solving a stochastic optimization model for a back pain IPU in the face of random arrivals, an uncertain patient mix, and variable service times. The deterministic version of the problem is modeled as a mixed integer program with the objective of minimizing a weighted combination of clinic closing time (duration) and total patient waiting time (length of stay). A two‐stage stochastic program is then derived to account for the randomness and the sequential nature of the decisions. Although it was not possible to solve the two‐stage problem for even a limited number of scenarios, the wait‐and‐see (WS) problem was sufficiently tractable to provide a lower bound on the stochastic solution. The introduction of valid inequalities, limiting indices, and the use of special ordered sets helped to speed up the computations. A greedy heuristic was also developed to obtain solutions much more quickly. Out of practical considerations, it was necessary to develop appointment templates with time slots at fixed intervals, which are not available from the WS solution. The first to be derived was the expected value (EV) template that is used to find the expected value of the EV solution (EEV). This solution provides an upper bound on the objective function value of the two‐stage stochastic program. The average gap between the EEV and WS solutions was 18%. Results from extensive computational testing are presented for the EV template and for our adaptation of three other templates found in the literature. Depending on the relative importance of the two objective function metrics, the results demonstrate the trade‐off that exists between them. For the templates investigated, the “closing time” ranged from an average of 235 to 275 minutes for a 300‐minute session, while the corresponding “total patient time in clinic” ranged from 80 to 71 minutes.     

Multiple common due dates

Common due date problems have been extensively discussed in the scheduling literature. Initially, these problems discussed finding a common due date for a set of jobs on a single machine. These single machine problems were later extended to finding the common due date on a set of parallel machines. This paper further extends the single machine problem to finding multiple common due dates on a single machine. For a basic and important class of penalty functions, we show that this problem is comparable to the parallel machine problem. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 293–298, 2001     

A heuristic for the two‐machine no‐wait openshop scheduling problem

In this paper the problem of minimizing makespan in a two‐machine openshop is examined. A heuristic algorithm is proposed, and its worst case performance ratio and complexity are analyzed. The average case performance is evaluated using an empirical study. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 129–145, 1999     

Open shop scheduling to minimize the number of late jobs

We develop polynomial algorithms for several cases of the NP-hard open shop scheduling problem of minimizing the number of late jobs by utilizing some recent results for the open shop makespan problem. For the two machine common due date problem, we assume that either the machines or the jobs are ordered. For the m machine common due date problem, we assume that one machine is maximal and impose a restriction on its load. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 525–532, 1998     

Openshop scheduling under linear resources constraints

Consider n jobs (J₁, …, J_n), m working stations (M₁, …, M_m) and λ linear resources (R₁, …, R_λ). Job J_i consists of m operations (O_i1, …, O_im). Operation O_ij requires P_k(i, j) units of resource R_k to be realized in an M_j. The availability of resource R_k and the ability of the working station M_h to consume resource R_k, vary over time. An operation involving more than one resource consumes them in constant proportions equal to those in which they are required. The order in which operations are realized is immaterial. We seek an allocation of the resources such that the schedule length is minimized. In this paper, polynomial algorithms are developed for several problems, while NP-hardness is demonstrated for several others. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 51–66, 1998     

网络中心战中舰艇编队的作战效能分析

在网络中心战条件下,舰艇编队通过互通、互联和互操作,可在编队范围内共享资源,进行跨平台的通道组织和实现武器共用,这种跨平台的资源共享充分发挥了作战资源的利用率,增强了编队作战系统的生命力。建立了在网络中心战条件下的舰艇编队作战效能计算数模,并进行了分析和计算,解释了在网络支持下编队作战效能提升的原理,分析和计算方法可用于网络兵力的兵力指数计算和作战效能评估。     

仿真网格原型系统的设计与实现

进行仿真网格原型系统的研究是解决仿真网格关键技术的基础。SGE网格引擎是一个构建本地和集群级网格的工具,通过SGE构建基本的网格平台,根据HLA仿真任务的特点,对分布式仿真网格的原型系统进行了研究和设计。提出了仿真网格的双通道通信机制:一个通道负责仿真网格组件的通信,另一个通道负责HLA仿真任务之间的通信。提出了仿真任务在仿真网格中的三种调度模式:以进程为单位的调度、以联邦成员为单位的调度、以联邦为单位的调度等。通过研究初步实现了仿真网格的原型系统,并对HLA仿真任务的三种调度模式进行了简单的测试。     

Linear compound algorithms for the partitioning problem

For a given set S of nonnegative integers the partitioning problem asks for a partition of S into two disjoint subsets S₁ and S₂ such that the sum of elements in S₁ is equal to the sum of elements in S₂. If additionally two elements (the kernels) r₁, r₂ ∈ S are given which must not be assigned to the same set S_i, we get the partitioning problem with kernels. For these NP‐complete problems the authors present two compound algorithms which consist both of three linear greedylike algorithms running independently. It is shown that the worst‐case performance of the heuristic for the ordinary partitioning problem is 12/11, while the second procedure for partitioning with kernels has a bound of 8/7. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 593–601, 2000     

通用装备保障训练需求分析框架研究

针对目前通用装备保障训练需求分析缺少系统规范方法的问题,建立了一套面向任务、基于能力的装备保障训练需求分析框架。通过结构化的分析过程,该方法能够辅助决策者合理地判断保障任务对保障者的能力要求,获得保障者的能力（或素质）＂状态缺口＂、形成初步的训练方案。并以复杂电磁环境下装备指挥活动为案例进行了分析,提出了装备指挥人员在复杂电磁环境下应具备的能力。     

面向作战任务的最小风险传感器调度方法

基于风险理论提出一种面向不同目标探测任务的传感器调度方法。将主动传感器辐射被截获风险和目标探测风险结合起来,建立一般目标探测框架下的传感器最小风险调度模型。分目标跟踪、目标识别和目标威胁等级评估三种情况将传感器最小风险调度模型具体化,给出不同情况下目标探测风险值的计算方法。针对模型的求解提出一种基于混沌思想、反向学习和双向轮盘赌的改进人工蜂群算法。通过仿真实验证明了模型的可行性和算法的有效性。