Deterministic and stochastic scheduling with teamwork tasks

We study a class of new scheduling problems which involve types of teamwork tasks. Each teamwork task consists of several components, and requires a team of processors to complete, with each team member to process a particular component of the task. Once the processor completes its work on the task, it will be available immediately to work on the next task regardless of whether the other components of the last task have been completed or not. Thus, the processors in a team neither have to start, nor have to finish, at the same time as they process a task. A task is completed only when all of its components have been processed. The problem is to find an optimal schedule to process all tasks, under a given objective measure. We consider both deterministic and stochastic models. For the deterministic model, we find that the optimal schedule exhibits the pattern that all processors must adopt the same sequence to process the tasks, even under a general objective function GC = F(f₁(C₁), f₂(C₂), … , f_n(C_n)), where f_i(C_i) is a general, nondecreasing function of the completion time C_i of task i. We show that the optimal sequence to minimize the maximum cost MC = max f_i(C_i) can be derived by a simple rule if there exists an order f₁(t) ≤ … ≤ f_n(t) for all t between the functions {f_i(t)}. We further show that the optimal sequence to minimize the total cost TC = ∑ f_i(C_i) can be constructed by a dynamic programming algorithm. For the stochastic model, we study three optimization criteria: (A) almost sure minimization; (B) stochastic ordering; and (C) expected cost minimization. For criterion (A), we show that the results for the corresponding deterministic model can be easily generalized. However, stochastic problems with criteria (B) and (C) become quite difficult. Conditions under which the optimal solutions can be found for these two criteria are derived. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

Predicting intensive care unit bed occupancy for integrated operating room scheduling via neural networks

In a master surgery scheduling (MSS) problem, a hospital's operating room (OR) capacity is assigned to different medical specialties. This task is critical since the risk of assigning too much or too little OR time to a specialty is associated with overtime or deficit hours of the staff, deferral or delay of surgeries, and unsatisfied—or even endangered—patients. Most MSS approaches in the literature focus only on the OR while neglecting the impact on downstream units or reflect a simplified version of the real‐world situation. We present the first prediction model for the integrated OR scheduling problem based on machine learning. Our three‐step approach focuses on the intensive care unit (ICU) and reflects elective and urgent patients, inpatients and outpatients, and all possible paths through the hospital. We provide an empirical evaluation of our method with surgery data for Universitätsklinikum Augsburg, a German tertiary care hospital with 1700 beds. We show that our model outperforms a state‐of‐the‐art model by 43% in number of predicted beds. Our model can be used as supporting tool for hospital managers or incorporated in an optimization model. Eventually, we provide guidance to support hospital managers in scheduling surgeries more efficiently.     

Scheduling maintenance and semiresumable jobs on a single machine

The majority of scheduling literature assumes that the machines are available at all times. In this paper, we study single machine scheduling problems where the machine maintenance must be performed within certain intervals and hence the machine is not available during the maintenance periods. We also assume that if a job is not processed to completion before the machine is stopped for maintenance, an additional setup is necessary when the processing is resumed. Our purpose is to schedule the maintenance and jobs to minimize some performance measures. The objective functions that we consider are minimizing the total weighted job completion times and minimizing the maximum lateness. In both cases, maintenance must be performed within a fixed period T, and the time for the maintenance is a decision variable. In this paper, we study two scenarios concerning the planning horizon. First, we show that, when the planning horizon is long in relation to T, the problem with either objective function is NP-complete, and we present pseudopolynomial time dynamic programming algorithms for both objective functions. In the second scenario, the planning horizon is short in relation to T. However, part of the period T may have elapsed before we schedule any jobs in this planning horizon, and the remaining time before the maintenance is shorter than the current planning horizon. Hence we must schedule one maintenance in this planning horizon. We show that the problem of minimizing the total weighted completion times in this scenario is NP-complete, while the shortest processing time (SPT) rule and the earliest due date (EDD) rule are optimal for the total completion time problem and the maximum lateness problem respectively. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 845–863, 1999     

向量巨型机高效程序设计技术

本文着重研究适应向量巨型机体系结构的高效程序设计技术。围绕减少指令流水线阻塞,提高多功能部件并行度,数据调度与局部化技术三个方面进行了深入的讨论,给出了一系列设计高效程序的方法和技巧。     

A new appointment rule for a single-server,multiple-customer service system

This paper proposes a new appointment rule for the single-server, multiple-customer service system. Unlike previous appointment rules, which perform well only in specific service environments, the new rule can be parameterized to perform well in different service environments. The new appointment rule is presented as a mathematical function of four environmental parameters, namely, the coefficient of variation of the service time, the percentage of customers' no-shows, the number of appointments per service session, and the cost ratio between the server's idle and customers' waiting cost per unit time. Once the values of these environmental parameters are estimated, the new appointment rule can be parameterized to perform well. The results show that new rule performs either as well as or better than existing appointment rules in a wide range of service environments. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 313–326, 1998     

电力市场环境下发电厂机组检修计划

分析了传统的统一调度下和电力市场环境下发电厂机组检修计划的不同,在此基础上提出不同于以往的检修计划方法。以检修费用、电价收益损失和违约金之和最小为目标函数,然后采用0-1整数规划的直接枚举法求解。最后通过算例论证了该方法的可行性。     

应用于流水时序调度的归一化定时数据流图理论

流水时序调度是专用数字信号处理器高层综合中的一个困难而急待解决的问题 ,文中提出了一种有着鲜明物理意义的归一化定时数据流图 ,基于节点移动研究了合法流水调度变换的内部机理 ,从而证明从任一合法的初始流水调度出发 ,通过合法的节点移动可以搜索到设计空间中任何一个合法的流水调度。一个合法、完备的变换集 ,为寻优搜索的算法应用于流水调度解决了理论和算法实现问题。文中还给出了一些实验结果。     

A comparative study of three tool replacement/operation sequencing strategies in a flexible manufacturing system

This paper studies three tool replacement/operation sequencing strategies for a flexible manufacturing system over a finite time horizon: (1) failure replacement—replace the tool only upon failure, (2) optimal preventive tool replacement for a fixed sequence of operations, and (3) joint scheduling of the optimal preventive tool replacement times and the optimal sequence of operations. Stochastic dynamic decision models are used for strategies 2 and 3. The optimization criterion for strategies 2 and 3 is the minimization of the total expected cost over the finite time horizon. We will show through numerical studies that, with the same amount of information, the total expected costs can be reduced considerably by choosing an optimal strategy. Our conclusion is that in flexible manufacturing, optimal tool replacement and optimal operations sequencing are not separate issues. They should be considered jointly to minimize the expected total cost. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 479–499, 2000     

基于变结构的应急航材调度策略

针对应急航材需求的随机性提出了变结构应急航材配送网络的概念,立足于物流运输车辆的优化调度,将现代优化算法引入应急航材的调度中,通过仿真算例的验证可以得出调运路径长度及应急航材需求量与调运时间成正比。     

机务保障要求到保障方案转换

首先以装备可靠性为依据,以任务要求中任务时间、出动飞机数量、任务可靠度等参数为约束,建立了保障资源的配置模型;在确定保障资源配置基础上再以保障任务时间为优化目标,建立保障任务调度模型和调度算法,按照保障专业调度优化,为保障方案制定奠定了重要基础,对实行精确化保障有重要现实意义,对基层级的保障工作有很强的指导作用。