Reducing patient-flow delays in surgical suites through determining start-times of surgical cases

A scheduling strategy to determine starting times of surgeries in multiple operating rooms (OR) is presented. The constraints are resource limit of a downstream facility, post-anesthesia care unit (PACU), and the service time uncertainties. Given sets of surgeries that need to be done on a day, this problem is formulated as a flexible job shop model with fuzzy sets. Patient-waitings in the process flow, clinical resource idling, and total completion times are considered for evaluation. This multi-objective problem is solved by a two-stage decision process. A genetic algorithm is used for determining relative order of surgeries in the first stage and definite starting times for all the surgical cases are obtained by a decision-heuristic in the second stage. The resultant schedule is evaluated by a Monte-Carlo simulation. The performance is shown to be better than our previous approach, a simulation based scheduling which already outperforms simple scheduling rules in regional hospitals. Additionally, the ratio of PACU to OR is examined using the proposed scheduling strategy.     

An approximation algorithm for scheduling two parallel machines with capacity constraints

We consider the problem of scheduling n independent jobs on two identical parallel machines, with a limit on the number of jobs that can be assigned to each single machine, so as to minimize the total weighted completion time of the jobs. We study a semidefinite programming-based approximation algorithm for solving this problem and prove that the algorithm has a worst case ratio at most 1.1626.     

Dynamic journeying under uncertainty

We introduce a journey planning problem in multi-modal transportation networks under uncertainty. The goal is to find a journey, possibly involving transfers between different transport services, from a given origin to a given destination within a specified time horizon. Due to uncertainty in travel times, the arrival times of transport services at public transport stops are modeled as random variables. If a transfer between two services is rendered unsuccessful, the commuter has to reconsider the remaining path to the destination. The problem is modeled as a Markov decision process in which states are defined as paths in the transport network. The main contribution is a backward induction method that generates an optimal policy for traversing the public transport network in terms of maximizing the probability of reaching the destination in time. By assuming history independence and independence of successful transfers between services we obtain approximate methods for the same problem. Analysis and numerical experiments suggest that while solving the path dependent model requires the enumeration of all paths from the origin to the destination, the proposed approximations may be useful for practical purposes due to their computational simplicity. In addition to on-time arrival probability, we show how travel and overdue costs can be taken into account, making the model applicable to freight transportation problems.     

A stochastic model for operating room planning with elective and emergency demand for surgery

This paper describes a stochastic model for Operating Room (OR) planning with two types of demand for surgery: elective surgery and emergency surgery. Elective cases can be planned ahead and have a patient-related cost depending on the surgery date. Emergency cases arrive randomly and have to be performed on the day of arrival. The planning problem consists in assigning elective cases to different periods over a planning horizon in order to minimize the sum of elective patient related costs and overtime costs of operating rooms. A new stochastic mathematical programming model is first proposed. We then propose a Monte Carlo optimization method combining Monte Carlo simulation and Mixed Integer Programming. The solution of this method is proved to converge to a real optimum as the computation budget increases. Numerical results show that important gains can be realized by using a stochastic OR planning model.     

Easy distributions for combinatorial optimization problems with probabilistic constraints

We show how we can linearize individual probabilistic linear constraints with binary variables when all coefficients are independently distributed according to either N(μ_i,λμ_i), for some λ>0 and μ_i>0, or Γ(k_i,θ) for some θ>0 and k_i>0. The constraint can also be linearized when the coefficients are independent and identically distributed and either positive or strictly stable random variables.     

Stockpiling under price uncertainty and storage capacity constraints

A model is presented for the operation of an agent whose responsibility is to purchase and perhaps stockpile sufficient quantities of a certain commodity in order to satisfy an exogenous constant demand per time period. This is the situation faced by a state agency which is responsible for the purchasing of oil products to satisfy the demand of a country in which demand for energy has stabilized at a certain level.An important feature of the model is that the price of the commodity is described by a stochastic process. This reflects the volatility of prices of oil products. Furthermore, the model takes storage capacity constraints explicitly into account, and thus can help to assess the optimal level of storage capacity expansion.The relevant stochastic dynamic programming equations are derived and solved for the least cost function, which turns out to be piecewise linear in the inventory level. The storage capacity enters only in the computation of the constant term of the value function. The solution of the dynamic programming equation leads also to the optimal purchasing strategy of agencies with different levels of flexibility in their policy: in the model, an agency can be allowed or not to resell from the stock and it can have finite or infinite storage capacity.     

Optimizing revenue in CDMA networks under demand uncertainty

Mathematical programming models for telecommunications network design are prevalent in the literature, but little research has been reported on stochastic models for cellular networks. We present a stochastic revenue optimization model for CDMA networks inspired by bid pricing models from the airline industry. We describe the optimality conditions for the model and develop a supergradient algorithm to solve it. We provide computational results that show the effects of the distribution and variance of demand. Finally, we discuss areas of future research, including a method to optimize the locations of the towers.     

Integrated design and operation of remnant inventory supply chains under uncertainty

We consider the simultaneous design and operation of remnant inventory supply chains. Remnant inventory is generated when demand for various lengths of a product may be satisfied by existing inventory, or by cutting a large piece into smaller pieces. We formulate our problem as a two-stage stochastic mixed-integer program. In solving our stochastic program, we enhance the standard L-shaped method in two ways. Our computational experiments demonstrate that these enhancements are effective, dramatically reducing the solution time for large instances.     

Flexible supply policy with options and capacity constraints

This paper considers a class of multi-period flexible supply policies with options and capacity constraints. The main results are to characterize the optimal ordering and purchasing options policy and the minimum expected cost in a period and thereafter under the assumptions about the options and ordering quantities.     

Scheduling linearly shortening jobs under precedence constraints

We consider the problem of scheduling a set of dependent jobs on a single machine with the maximum completion time criterion. The processing time of each job is variable and decreases linearly with respect to the starting time of the job. Applying a uniform approach based on the calculation of ratios of expressions that describe total processing times of chains of jobs, we show basic properties of the problem. On the basis of these properties, we prove that if precedence constraints among jobs are in the form of a set of chains, a tree, a forest or a series–parallel digraph, the problem can be solved in O(n log n) time, where n denotes the number of the jobs.     

Combining Constraint Programming and Linear Programming on an Example of Bus Driver Scheduling

This paper provides details of a successful application where the Column Generation algorithm was used to combine Constraint Programming and Linear Programming. In the past, constraint programming and linear programming were considered to be two competing technologies that solved similar types of problems. Both these technologies had their strengths and weaknesses. This paper shows that the two technologies can be combined together to extract the strengths of both these technologies. Details of a real-world application to optimize bus driver duties is given here. This system was developed by ILOG for a major software house in Japan using ILOG-Solver and ILOG-CPLEX, constraint programming and linear programming C/C++ libraries.     

Heuristic Control of a Constraint-Based Algorithm for the Preemptive Job-Shop Scheduling Problem

In the recent years, constraint programming has been applied to a wide variety of academic and industrial non-preemptive scheduling problems, i.e., problems in which activities cannot be interrupted. In comparison, preemptive scheduling problems have received almost no attention from both the Operations Research and the Artificial Intelligence community. Motivated by the needs of a specific application, we engaged in a study of the applicability of constraint programming techniques to preemptive scheduling problems. This paper presents the algorithms we developed and the results we obtained on the preemptive variant of the famous job-shop scheduling problem. Ten heuristic search strategies, combined with two different constraint propagation techniques, are presented, and compared using two well-known series of job-shop scheduling instances from the literature. The best combination, which relies on limited discrepancy search and on edge-finding techniques, is shown to provide excellent solutions to the preemptive job-shop scheduling problem. A mean relative distance to the optimal solution of 0.32% is achieved in five minutes, on instances with 10 jobs and 10 machines (100 activities).     

基于多Agent系统的项目调度研究

近年来 ,大型项目特别是大型工程项目存在如下的发展趋势 :1 )项目规模越来越大 ;2 )项目的复杂程度不断增加 ;3 )项目必须由多方合作才能完成 .本文针对上述特点 ,提出了基于多 Agent系统 (MAS:Multi-Agent Systems)解决资源约束条件下的项目调度问题 (RCPSP:Resource Constrained ProjectScheduling Problems)的方法 ,并通过实例项目对所提出的算法进行了验证 .     

调度问题中两类分离约束传播算法的比较及一种改进算法

约束传播算法是求解约束满足问题的一种重要方法。调度问题是一种特殊的约束满足问题。本介绍了调度问题中的Edge-Finding和Energy-Reasoning两种分离约束传播算法，并对它们进行了比较，中最后给出了一种结合Energy-Reasoning的Edge-Finding改进算法。     

Cane Railway Scheduling via Constraint Logic Programming: Labelling Order and Constraints in a Real-Life Application

In Australia, cane transport is the largest unit cost in the manufacturing of raw sugar, making up around 35% of the total manufacturing costs. Producing efficient schedules for the cane railways can result in significant cost savings. This paper presents a study using Constraint Logic Programming (CLP) to solve the cane transport scheduling problem. Tailored heuristic labelling order and constraints strategies are proposed and encouraging results of application to several test problems and one real-life case are presented. The preliminary results demonstrate that CLP can be used as an effective tool for solving the cane transport scheduling problem, with a potential decrease in development costs of the scheduling system. It can also be used as an efficient tool for rescheduling tasks which the existing cane transport scheduling system cannot perform well.     

Multi-product newsboy problem with limited capacity and outsourcing

This paper considers a multi-product newsboy system that produces multiple products for fulfilling independently uncertain demands, which share the same production capacity. To deal with possible shortage of limited capacity, productions can be outsourced. We consider two outsourcing strategies: zero lead time outsourcing, and nonzero lead time outsourcing. The structural properties and solution procedures for the profit-maximization models are developed. Numerical results are provided for obtaining some managerial insights.     

网格环境下制造资源在线优化调度的区间规划模型

针对网格环境下影响制造资源优化调度的关键参数具有区间性的特点,本文基于区间数建立了在线处理模式下的资源优化调度模型,分别以任务完工的总成本最低与资源的利益最大为目标,将任务的成本限制及资源的价格转换为区间数,充分考虑了任务与资源工作时间限制,给出区间规划模型及其解法。最后通过算例分析得出该模型在反映市场需求以及快速应对市场变化基础上,可得出合理的优化调度方案,验证该方法的可行性与有效性。     

基于动态列生成算法的飞机排班问题研究

飞机排班是航空运输生产计划的重要环节,对航空公司的正常运营和整体效益有着决定性影响;飞机排班通常构建为大规模整数规划问题,是航空运筹学研究的重要课题,构建的模型属于严重退化的NP-Hard问题.在考虑对多种机型的飞机进行排班时,大大增加了问题的复杂性.针对航空公司实际情况,建立多种机型的飞机排班模型;为实现模型的有效求解,提出了基于约束编程的动态列生成算法;即用约束编程快速求解航班连线(航班串)并计算航班串简约成本,动态选择列集并与限制主问题进行迭代.最后,利用国内某航空公司干线航班网络实际数据验证模型和算法的有效性.     

地震期间应急资源调度方案的优化选取

应急资源的调度是地震救援工作的重点,为解决这个难题,本文构建了以时效性、伤亡性和经济性为三大分量的多目标函数,然后经过无量纲和Delphi加权处理,将其转化为单目标函数,并将其中的决策效用函数看成运筹学中指派问题的效率函数,最后运用匈牙利法计算出最大的目标函数值,从而得出最优的资源调度方案.与其他多目标的应急资源调度方法相比,本文构建的这种算法具有简易、实用的优点,可以说为地震期间应急资源调度方案的优化选取工作提供了一种切实、可行的途径.     

On joint probabilistic constraints with Gaussian coefficient matrix

The paper deals with joint probabilistic constraints defined by a Gaussian coefficient matrix. It is shown how to explicitly reduce the computation of values and gradients of the underlying probability function to that of Gaussian distribution functions. This allows us to employ existing efficient algorithms for calculating this latter class of functions in order to solve probabilistically constrained optimization problems of the indicated type. Results are illustrated by an example from energy production.