Evaluating appointment postponement in scheduling patients at a diagnostic clinic

Diagnostic clinics are among healthcare facilities that suffer from long waiting times which can worsen medical outcomes and increase patient no-shows. Reducing waiting times without significant capital investments is a challenging task. We tackle this challenge by proposing a new appointment scheduling policy that does not require significant investments for diagnostic clinics. The clinic in our study serves outpatients, inpatients, and emergency patients. Emergency patients must be seen on arrival, and inpatients must be given next day appointments. Outpatients, however, can be given later appointments. The proposed policy takes advantage of this by allowing the postponement of the acceptance of appointment requests from outpatients. The appointment scheduling process is modeled as a two-stage stochastic programming problem where a portion of the clinic capacity is allocated to inpatients and emergency patients in the first stage. In the second stage, outpatients are scheduled based on their priority classes. After a detailed analysis of the solutions obtained from the two-stage stochastic model, we develop a simple, non-anticipative policy for patient scheduling. We evaluate the performance of this proposed, easy-to-implement policy in a simulation study which shows significant improvements in outpatient indirect waiting times.     

Due‐window assignment with unit processing‐time jobs

In due‐window assignment problems, jobs completed within a designated time interval are regarded as being on time, whereas early and tardy jobs are penalized. The objective is to determine the location and size of the due‐window, as well as the job schedule. We address a common due‐window assignment problem on parallel identical machines with unit processing time jobs. We show that the number of candidate values for the optimal due‐window starting time and for the optimal due‐window completion time are bounded by 2. We also prove that the starting time of the first job on each of the machines is either 0 or 1, thus introducing a fairly simple, constant‐time solution for the problem. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

An efficient metaheuristic for integrated scheduling and staffing IT projects based on a generalized minimum cost flow network

Scheduling IT projects and assigning the project work to human resources are an important and common tasks in almost any IT service company. It is particularly complex because human resources usually have multiple skills. Up to now only little work has considered IT‐specific properties of the project structure and human resources. In this article, we present an optimization model that simultaneously schedules the activities of multiple IT projects with serial network structures and assigns the project work to multiskilled internal and external human resources with different efficiencies. The goal is to minimize costs. We introduce a metaheuristic that decomposes the problem into a binary scheduling problem and a continuous staffing problem where the latter is solved efficiently by exploiting its underlying network structure. For comparison, we solve the mixed–binary linear program with a state–of–the–art commercial solver. The impacts of problem parameters on computation time and solution gaps between the metaheuristic and the solver are assessed in an experimental study. Our results show that the metaheuristic provides very favorable results in considerable less time than the solver for midsize problems. For larger problems, it shows a similar performance while the solver fails to return feasible solutions. © 2012 Wiley Periodicals, Inc. Naval Research Logistics 59: 111–127, 2012     

面向能耗有效高性能嵌入式微处理器的VLIW调度

为了降低功耗,目前能耗有效的嵌入式微处理器一般都采用分布式与层次化的寄存器文件结构。第一层的超小寄存器文件(TORF)的极小容量使得很多数据必须存放到第二层的通用寄存器文件(GRF)中,这给编译器带来了新的挑战。通过分析程序特征,提出了新的VLIW调度算法,通过在编译时对变量进行检测,在恰当的时机插入虚拟的copy操作并进行指令与通信调度,为对寄存器需求较大的全局变量与软流水变量构建了新的包含GRF的数据传输路由,将对TORF的压力转移到GRF中。实验结果表明,新的VLIW调度算法符合处理器的设计初衷。与不使用GRF相比,在程序性能只降低约8%的情况下,降低了约51%的寄存器访问能耗,43%的处理器能耗。最关键的是避免了程序员手工分配优化的难题。     

航天测控调度问题的拉格朗日启发式算法

通过分析航天测控调度问题的测控需求,建立了航天测控调度0-1整数规划模型,运用拉格朗日松弛方法对模型中的任务约束和设备约束进行了松弛,运用次梯度优化算法求得了航天测控调度问题上界,同时得到了决策变量对应的拉格朗日权重,可以作为决策变量在最优解中是否被调度的启发式信息,对拉格朗日权重进行分析,提出了求解问题可行解的拉格朗日启发式算法。最后,通过对两个场景的试验分析验证了拉格朗日启发式算法所求可行解的优越性。     

多专业批量维修任务调度方法研究

通过对不同专业设置方式下的维修任务调度问题进行分析,以最小化批量维修任务的维修时间为目标,将考虑专业维修顺序的批量维修任务调度问题分成两步进行求解,首先,建立了批量维修任务在专业领域内的调度及优化模型;其次,提出了基于NEH的批量维修任务排序方法．最后,通过实例对模型和方法的正确性和可行性进行了说明和验证,实例结果表明,该方法更贴近于实际,实现了快速、有效地解决维修任务调度问题,     

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.