Optimized appointment scheduling

In service systems, in order to balance the server’s idle times and the customers’ waiting times, one may fix the arrival times of the customers beforehand in an appointment schedule. We propose a procedure for determining appointment schedules in such a D/G/1-type of system by sequentially minimizing the per-customer expected loss. Our approach provides schedules for any convex loss function; for the practically relevant cases of the quadratic and absolute value loss functions appealing closed-form results are derived. Importantly, our approach does not impose any conditions on the service time distribution; it is even allowed that the customers’ service times have different distributions.     

Improving appointment scheduling for medical screening

We investigate the optimization of appointment scheduling forbreast cancer screening, using the fact that a woman's attendanceprobability can be predicted. The methodology used applies tomedical screening in general. The results of the mathematical investigation presented in thispaper include a new formula for the cost of a screening session,a probabilistic model of rebooking appointments, a model ofattendance probability as a function of previous performance,and a heuristic cost optimization procedure. Breast Test Wales have improved efficiency by introducing heavilyoverbooked sessions for patients who are unlikely to attend.We use simulation modelling and insights from probability theoryto confirm the gain achieved by the Wales procedure and to assessthe further gain achievable by optimization of appointment scheduling.It is found that a gain in throughput of at least 10% can beobtained by optimizing appointment scheduling for screeningsessions, in particular by inviting patients in decreasing orderof attendance probability, and by overbooking near the end ofthe session. This avoids the need to set up dedicated sessionsfor poor attenders. Another possibility is to book patientswho change their appointment time, and who are therefore verylikely to attend, into dedicated sessions. The provision of appointment scheduling software with a built-insimulation and optimization module along the lines describedin this paper could enable radiographers to tailor appointmentscheduling for each area and so to schedule appointments veryefficiently.     

Outpatient appointment scheduling in presence of seasonal walk-ins

This study investigates appointment systems (AS), as combinations of access rules and appointment-scheduling rules, explicitly designed for dealing with walk-in seasonality. In terms of ‘access rules’, strategies are tested for adjusting capacity through intra-week, or monthly seasonality of walk-ins, or their combined effects. In terms of ‘appointment rules’, strategies are tested to determine which particular slots to double-book or leave open in cases where seasonal walk-in rates exceed or fall short of the overall yearly rate. In that regard, this study integrates capacity and appointment decisions, which are usually addressed in an isolated manner in previous studies. Simulation optimization is used to derive heuristic solutions to the appointment-scheduling problem, and the findings are compared in terms of in-clinic measures of patient wait time, physician idle time and overtime. The goal is to provide practical guidelines for healthcare practitioners on how to best design their AS when seasonal walk-ins exist.     

Outpatient appointment scheduling given individual day-dependent no-show predictions

This paper examines the combined use of predictive analytics, optimization, and overbooking to schedule outpatient appointments in the presence of no-shows. We tackle the problem of optimally overbooking appointments given no-show predictions that depend on the individual appointment characteristics and on the appointment day. The goal is maximizing the number of patients seen while minimizing waiting time and overtime. Our analysis leads to the definition of a near-optimal and simple heuristic which consists of giving same-day appointments to likely shows and future-day appointments to likely no-shows. We validate our findings by performing extensive simulation tests based on an empirical data set of nearly fifty thousand appointments from a real outpatient clinic. The results suggest that our heuristic can lead to a substantial increase in performance and that it should be preferred to open access under most parameter configurations. Our paper will be of great interest to practitioners who want to improve their clinic performance by using individual no-show predictions to guide appointment scheduling.     

Two-day appointment scheduling with patient preferences and geometric arrivals

We consider an appointment system where the patients have preferences about the appointment days. A patient may be scheduled on one of the days that is acceptable to her, or be denied appointment. The patient may or may not show up at the appointed time. The net cost is a convex function of the actual number of patients served on a given day. We study the optimal scheduling policy that minimizes the long-run average cost and study its structural properties. We advocate an index policy, which is easy to implement, performs well in comparison with other heuristic policies, and is close to the optimal policy.     

Stochastic scheduling in an in-forest

Consider a problem of scheduling activities of a research and development project, where precedence relations of the activities constituting the project are represented by edges of an in-forest. Each activity is characterized by two parameters: a cost for attempting that activity and a probability that attempting the activity will lead to successful completion. The problem is to find a policy for attempting activities that minimizes the expected cost incurred until termination (successful completion of the project or the first activity failure). The main result of the paper is the design of an efficient algorithm to determine an optimal sequence in which to attempt the activities; a result which is established for linear and exponential utility functions. It is also shown that, unlike the related problem with out-forest precedence relations, there need not exist an optimal policy that is based on an index-rule for determining priority of edges by evaluating their successors.     

Stochastic scheduling problems II-set strategies-

The paper introduces the finite class of set strategies for stochastic scheduling problems. It is shown that the knownstable classes of strategies such as ES and MES strategies are of this type, as arelist-scheduling strategies such as LEPT and SEPT and other, more complicatedpriority-type strategies. Roughly speaking, set strategies are characterized by the fact that the decision as to which jobs should be started at timet depends only on the knowledge of the two sets of jobs finished up to timet and being processed at timet. Contrary to list scheduling strategies, set strategies may involve deliberate idleness of machines, i.e. may not be greedy and can therefore not generally be induced by priority rules. It is demonstrated that set strategies have useful properties. They are e.g. ⁿ -almost everywhere continuous and therefore show satisfactorystability behaviour w.r.t. weak convergence of the joint distribution of job durations. Furthermore, the optimum w.r.t.all strategies is already attained on this class if job durations are independent and exponentially distributed and the performance measure fulfills a certainshift condition. This shift property is a quite natural concept and generalizes aspects of the notion ofadditivity in semi-Markov decision theory and stochastic dynamic optimization. Its complete analytical characterization is a major object of this paper. Typical additive cost criteria such as makespan and flowtime are of course covered, which yields simultaneously a first step towards generalization of optimality of LEPT and SEPT rules, as known for special cases. In fact, in view of the obtained optimality result, the question of when deliberate idleness of machines can be avoided, gains considerable interest, as it characterizes stochastic environments in whichpriority strategies are optimal. This provides a major link with current research on the analysis of networks of queues in the context of computer systems.The work of the first two authors was supported by the Minister für Wissenschaft und Forschung des Landes Nordrhein-Westfalen, while the work of the last author was supported by DAAD.     

Stochastic scheduling with optimal customer service

Existing research in stochastic scheduling often ignores the need to achieve high service levels. Optimality is usually defined in terms of minimizing the expected makespan, with the intent to increase the expected utilization of the facility. We argue that this does not address the full ramifications of stochastic variation. Instead, we should minimize our total cost, including losses due to the variation. This, we show, leads to focusing on optimal service level. Furthermore, we show how to compare the mean and the standard deviation of the makespan directly. While this method applies for any distribution, we demonstrate it specifically for the important special case where the makespan distribution is (at least approximately) normal. Finally, we show by simulation (i) that it is very important to take into account that high variation in individual operations causes increases both in the mean and the variance of the final makespan; and (ii) that using the normal distribution results is a good approximation.     

Stochastic programming approaches to stochastic scheduling

Practical scheduling problems typically require decisions without full information about the outcomes of those decisions. Yields, resource availability, performance, demand, costs, and revenues may all vary. Incorporating these quantities into stochastic scheduling models often produces diffculties in analysis that may be addressed in a variety of ways. In this paper, we present results based on stochastic programming approaches to the hierarchy of decisions in typical stochastic scheduling situations. Our unifying framework allows us to treat all aspects of a decision in a similar framework. We show how views from different levels enable approximations that can overcome nonconvexities and duality gaps that appear in deterministic formulations. In particular, we show that the stochastic program structure leads to a vanishing Lagrangian duality gap in stochastic integer programs as the number of scenarios increases.This author's work was supported in part by the National Science Foundation under Grants ECS 88-15101, ECS 92-16819, and SES 92-11937.This author's work was supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant A-5489 and by the UK Engineering and Physical Sciences Research Council under Grants J90855 and K17897.     

Optimization models for radiotherapy patient scheduling

The efficient radiotherapy patient scheduling, within oncology departments, plays a crucial role in order to ensure the delivery of the right treatment at the right time. In this context, generating a high quality solution is a challenging task, since different goals (i.e., all the activities are scheduled as soon as possible, the patient waiting time is minimized, the device utilization is maximized) could be achieved and a large set of constraints (i.e., every device can be used by only one patient at time, the treatments have to be performed in an exact time order) should be taken into account. We propose novel optimization models dealing with the efficient outpatient scheduling within a radiotherapy department defined in such a way to represent different real-life situations. The effectiveness of the proposed models is evaluated on randomly generated problems and on a real case situation. The results are very encouraging since the developed optimization models allow to overcome the performance of human experts (i.e., the number of patients that begin the radiotherapy treatment is maximized).      

Optimal appointment scheduling in continuous time: The lag order approximation method

We study appointment scheduling problems in continuous time. A finite number of clients are scheduled such that a function of the waiting time of clients, the idle time of the server, and the lateness of the schedule is minimized. The optimal schedule is notoriously hard to derive within reasonable computation times. Therefore, we develop the lag order approximation method, that sets the client’s optimal appointment time based on only a part of his predecessors. We show that a lag order of two, i.e., taking two predecessors into account, results in nearly optimal schedules within reasonable computation times. We illustrate our approximation method with an appointment scheduling problem in a CT-scan area.     

Stochastic scheduling to minimize expected maximum lateness

This paper is concerned with the problems in scheduling a set of jobs associated with random due dates on a single machine so as to minimize the expected maximum lateness in stochastic environment. This is a difficult problem and few efforts have been reported on its solution in the literature. In this paper, we first derive a deterministic equivalent to the expected maximum lateness and then propose a dynamic programming algorithm to obtain the optimal solutions. The procedures to compute optimal solutions are initially developed in the case of deterministic processing times, and then extended to stochastic processing times following arbitrary probability distributions. Moreover, several heuristic rules are suggested to compute near-optimal solutions, which are shown to be highly efficient and accurate by computer-based experiments.     

Stochastic scheduling problems I — General strategies

The paper contains an introduction to recent developments in the theory of non-preemptive stochastic scheduling problems. The topics covered are: arbitrary joint distributions of activity durations, arbitrary regular measures of performance and arbitrary precedence and resource constraints. The possible instability of the problem is demonstrated and hints are given on stable classes of strategies available, including the combinatorial vs. analytical characterization of such classes. Given this background, the main emphasis of the paper is on the monotonicity behaviour of the model and on the existence of optimal strategies. Existing results are presented and generalized, in particular w.r.t. the cases of lower semicontinuous performance measures or joint duration distributions having a Lebesgue density.     

Stochastic programming for off-line adaptive radiotherapy

In intensity-modulated radiotherapy (IMRT), a treatment is designed to deliver high radiation doses to tumors, while avoiding the healthy tissue. Optimization-based treatment planning often produces sharp dose gradients between tumors and healthy tissue. Random shifts during treatment can cause significant differences between the dose in the ??optimized?? plan and the actual dose delivered to a patient. An IMRT treatment plan is delivered as a series of small daily dosages, or fractions, over a period of time (typically 35 days). It has recently become technically possible to measure variations in patient setup and the delivered doses after each fraction. We develop an optimization framework, which exploits the dynamic nature of radiotherapy and information gathering by adapting the treatment plan in response to temporal variations measured during the treatment course of a individual patient. The resulting (suboptimal) control policies, which re-optimize before each fraction, include two approximate dynamic programming schemes: certainty equivalent control (CEC) and open-loop feedback control (OLFC). Computational experiments show that resulting individualized adaptive radiotherapy plans promise to provide a considerable improvement compared to non-adaptive treatment plans, while remaining computationally feasible to implement.     

Non-block scheduling with priority for radiotherapy treatments

In this paper, a quite challenging operational problem within health care delivery has been considered: the optimal management of patients waiting for radiotherapy treatments. Long waiting times for radiotherapy treatments of several cancers are largely documented all over the world. This problem is mainly due to an imbalance between supply and demand of radiotherapy services, which negatively affects the effectiveness and the efficiency of the health care delivered. Within this context, the paper presents an innovative solution approach for effectively scheduling a set of patients waiting to start the radiotherapy plan. The proposed approach is based on a well tailored integer linear optimization program, modelling a non-block scheduling strategy, with the aim to minimize the mean waiting time or maximize the number of new scheduled patients. The model has been tested and evaluated by carrying out some numerical experiments on suitable use-case scenarios, and the obtained results demonstrate the effectiveness and reliability of the proposed approach.     

Stochastic scheduling of parallel queues with set-up costs

We consider the problem of allocating a single server to a system of queues with Poisson arrivals. Each queue represents a class of jobs and possesses a holding cost rate, general service distribution, and a set-up cost. The objective is to minimize the expected cost due to the waiting of jobs and the switching of the server. A set-up cost is required to effect an instantaneous switch from one queue to another. We partially characterize an optimal policy and provide a simple heuristic scheduling policy. The heuristic's performance is evaluated in the cases of two and three queues by comparison with a numerically obtained optimal policy. Simulation results are provided to demonstrate the effectiveness of our heuristic over a wide range of problem instances with four queues.     

Stochastic flow shop scheduling model for the Panama Canal

Reducing transit time is becoming increasingly important in maritime shipping of manufactured goods and commodities. Traversing the Panama Canal is a principal component of many global companies’ strategies to reduce shipping time in their supply chain. Operations in the Panama Canal can be described by a capacitated queueing network. In this study we used a metaheuristic approach based on Nested Partitions to find near optimal schedules for daily vessel traffic consisting of large vessels that want to pass through the Panama Canal. Results indicate that the metaheuristic technique consistently reduced the makespan of a set of vessels as compared to historical schedules used in canal operations. We also found distinct patterns in the schedules in which certain vessels consistently appeared at a certain position in the schedule.     

Stochastic cyclic scheduling problem in synchronous assembly and production lines

In this paper we address the stochastic cyclic scheduling problem in synchronous assembly and production lines. Synchronous lines are widely used in the production and assembly of various goods such as automobiles or household appliances. We consider cycle time minimisation (or throughput rate maximisation) as the objective of the scheduling problem with the assumption that the processing times are independent random variables. We first discuss the two-station case and present a lower bounding scheme and an approximate solution procedure for the scheduling problem. For the general case of the problem, two heuristic solution procedures are presented. An extension of the two-station lower bound to the general case of the problem is also discussed. The performance of the proposed heuristics on randomly generated problems is documented, and the impact of scheduling decisions on problems with different levels of variability in processing times are analysed. We also analyse the problem of sequence determination when the available information is limited to the expected values of individual processing times.