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.     

An algorithm for the discrete bilevel programming problem

The bilevel programming problem (BLPP) is an example of a two-stage, noncooperative game in which the first player can influence but not control the actions of the second. This article addresses the linear formulation and presents a new algorithm for solving the zero-one case. We begin by converting the leader's objective function into a parameterized constraint, and then attempt to solve the resultant problem. This produces a candidate solution that is used to find a point in the BLPP feasible reagion. Incremental improvements are sought, which ultimately lead to a global optimum. An example is presented to highlight the computations and to demonstrate some basic characteristics of the solution. Computational experience indicates that the algorithm is capable of solving problems with up to 50 variables in a reasonable amount of time.     

Optimal empty vehicle redistribution for hub‐and‐spoke transportation systems

This article considers the empty vehicle redistribution problem in a hub‐and‐spoke transportation system, with random demands and stochastic transportation times. An event‐driven model is formulated, which yields the implicit optimal control policy. Based on the analytical results for two‐depot systems, a dynamic decomposition procedure is presented which produces a near‐optimal policy with linear computational complexity in terms of the number of spokes. The resulting policy has the same asymptotic behavior as that of the optimal policy. It is found that the threshold‐type control policy is not usually optimal in such systems. The results are illustrated through small‐scale numerical examples. Through simulation the robustness of the dynamic decomposition policy is tested using a variety of scenarios: more spokes, more vehicles, different combinations of distribution types for the empty vehicle travel times and loaded vehicle arrivals. This shows that the dynamic decomposition policy is significantly better than a heuristics policy in all scenarios and appears to be robust to the assumptions of the distribution types. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008