Scheduling arrivals to a stochastic service mechanism

We consider the problem of scheduling the arrivals of a fixed number of customers to a stochastic service mechanism to minimize an expected cost associated with operating the system. We consider the special case of exponentially distributed service times and the problems in general associated with obtaining exact analytic solutions. For general service time distributions we obtain approximate numerical solutions using a stochastic version of gradient search employing Infinitesimal Perturbation Analysis estimates of the objective function gradient obtained via simulation.     

Proactive policies for the stochastic resource-constrained project scheduling problem

The resource-constrained project scheduling problem involves the determination of a schedule of the project activities, satisfying the precedence and resource constraints while minimizing the project duration. In practice, activity durations may be subject to variability. We propose a stochastic methodology for the determination of a project execution policy and a vector of predictive activity starting times with the objective of minimizing a cost function that consists of the weighted expected activity starting time deviations and the penalties or bonuses associated with late or early project completion. In a computational experiment, we show that our procedure greatly outperforms existing algorithms described in the literature.     

On the optimality of threshold control in queues with model uncertainty

We consider a single-stage queuing system where arrivals and departures are modeled by point processes with stochastic intensities. An arrival incurs a cost, while a departure earns a revenue. The objective is to maximize the profit by controlling the intensities subject to capacity limits and holding costs. When the stochastic model for arrival and departure processes are completely known, then a threshold policy is known to be optimal. Many times arrival and departure processes can not be accurately modeled and controlled due to lack of sufficient calibration data or inaccurate assumptions. We prove that a threshold policy is optimal under a max–min robust model when the uncertainty in the processes is characterized by relative entropy. Our model generalizes the standard notion of relative entropy to account for different levels of model uncertainty in arrival and departure processes. We also study the impact of uncertainty levels on the optimal threshold control.     

Applications of SMP Bounds to Multi-class Traffic in High-speed Networks

In this paper, we consider the stochastic fluid-flow model of a single node in a high-speed telecommunication network handling multi-class traffic. The node has multiple buffers, one for each class of traffic. The contents of these buffers are multiplexed onto a single output channel using one of the service scheduling policies: the Timed Round Robin Policy or the Static Priority Service Policy. The Quality of Service requirements for each class are based on cell loss probabilities. Using effective bandwidth methodologies and the recently developed bounds for semi-Markov modulated traffic, we solve call admission control problems for the two service scheduling policies at this node. We compare the performance of the effective bandwidth methodologies and the SMP bounds technique. We also numerically compare the performance of the two service scheduling policies.     

A mean-reverting stochastic model for the political business cycle

In this article, we look at the political business cycle problem through the lens of uncertainty. The feedback control used by us is the famous NKPC with stochasticity and wage rigidities. We extend the New Keynesian Phillips Curve model to the continuous time stochastic set up with an Ornstein–Uhlenbeck process. We minimize relevant expected quadratic cost by solving the corresponding Hamilton–Jacobi–Bellman equation. The basic intuition of the classical model is qualitatively carried forward in our set up but uncertainty also plays an important role in determining the optimal trajectory of the voter support function. The internal variability of the system acts as a base shifter for the support function in the risk neutral case. The role of uncertainty is even more prominent in the risk averse case where all the shape parameters are directly dependent on variability. Thus, in this case variability controls both the rates of change as well as the base shift parameters. To gain more insight we have also studied the model when the coefficients are time invariant and studied numerical solutions. The close relationship between the unemployment rate and the support function for the incumbent party is highlighted. The role of uncertainty in creating sampling fluctuation in this set up, possibly towards apparently anomalous results, is also explored.     

A multicut L-shaped based algorithm to solve a stochastic programming model for the mobile facility routing and scheduling problem

This paper considers the mobile facility routing and scheduling problem with stochastic demand (MFRSPSD). The MFRSPSD simultaneously determines the route and schedule of a fleet of mobile facilities which serve customers with uncertain demand to minimize the total cost generated during the planning horizon. The problem is formulated as a two-stage stochastic programming model, in which the first stage decision deals with the temporal and spatial movement of MFs and the second stage handles how MFs serve customer demands. An algorithm based on the multicut version of the L-shaped method is proposed in which several lower bound inequalities are developed and incorporated into the master program. The computational results show that the algorithm yields a tighter lower bound and converges faster to the optimal solution. The result of a sensitivity analysis further indicates that in dealing with stochastic demand the two-stage stochastic programming approach has a distinctive advantage over the model considering only the average demand in terms of cost reduction.     

Dynamic Routing and Admission Control in High-Volume Service Systems: Asymptotic Analysis via Multi-Scale Fluid Limits

Motivated by applications in telephone call centers, we consider a service system model with m customer classes and r server pools. The model is one with doubly stochastic arrivals, which means that the m-vector λ of instantaneous arrival rates is allowed to vary both temporally and stochastically. Two levels of dynamic control are considered: customers may be either blocked or accepted at the time of their arrival, and then accepted customers of each class must be routed, either immediately upon acceptance or after some period of waiting, to a server pool that is qualified to handle that class. Customers who are made to wait before commencement of their service are liable to defect. The objective is to minimize the expected sum of blocking costs, waiting costs and defection costs over a fixed and finite planning horizon. We consider an asymptotic parameter regime in which (i) the arrival rates, service rates and defection rates are uniformly accelerated by a large factor κ, then (ii) arrival rates are increased by an additional factor g(κ), and the number of servers in each pool is increased by g(κ) as well. This produces a separation of time scales, justifying a pointwise stationary stochastic fluid approximation for our original system model. In the stochastic fluid approximation, optimal admission control and routing decisions are determined by a simple linear program that uses the current arrival rate vector λ as data. We explain how to implement the fluid model's optimal control policy in our original service system context, and prove that the proposed implementation is asymptotically optimal in the first-order sense. AMS subject classification: 60K30, 90B15, 90B36     

Vehicle routing with stochastic time-dependent travel times

Assigning and scheduling vehicle routes in a stochastic time-dependent environment is a crucial management problem. The assumption that in a real-life environment everything goes according to an a priori determined static schedule is unrealistic. Our methodology builds on earlier work in which the traffic congestion is captured in an analytical way using queueing theory. The congestion is then applied to the VRP problem. In this paper, we introduce the variability in traffic flows into the model. This allows for an evaluation of the routes based on the uncertainty involved. Different experiments show that the risk taking behavior of the planner can be taken into account during optimization. As more weight is given to the variability component, the resulting optimal route will take a slightly longer travel time, but will be more reliable. We propose a powerful objective function that is easily implemented and that captures the trade-off between the average travel time and its variance. The evaluation of the solution is done in terms of the 95th-percentile of the travel time distribution (assumed to be lognormal), which reflects well the quality of the solution in this stochastic time-dependent environment.     

Project scheduling problem with mixed uncertainty of randomness and fuzziness

Project scheduling problem is to determine the schedule of allocating resources so as to balance the total cost and the completion time. This paper considers project scheduling problem with mixed uncertainty of randomness and fuzziness, where activity duration times are assumed to be random fuzzy variables. Three types of random fuzzy models as expected cost minimization model, (α, β)-cost minimization model and chance maximization model are built to meet different management requirements. Random fuzzy simulations for some uncertain functions are given and embedded into genetic algorithm to design a hybrid intelligent algorithm. Finally, some numerical experiments are given for the sake of illustration of the effectiveness of the algorithm.     

An enhanced decomposition algorithm for multistage stochastic hydroelectric scheduling

Handling uncertainty in natural inflow is an important part of a hydroelectric scheduling model. In a stochastic programming formulation, natural inflow may be modeled as a random vector with known distribution, but the size of the resulting mathematical program can be formidable. Decomposition-based algorithms take advantage of special structure and provide an attractive approach to such problems. We develop an enhanced Benders decomposition algorithm for solving multistage stochastic linear programs. The enhancements include warm start basis selection, preliminary cut generation, the multicut procedure, and decision tree traversing strategies. Computational results are presented for a collection of stochastic hydroelectric scheduling problems.     

Workforce planning at USPS mail processing and distribution centers using stochastic optimization

Service organizations that operate outside the normal 8-hour day and face wide fluctuations in demand constantly struggle to optimize the size and composition of their workforce. Recent research has shown that improved personnel scheduling methods that take demand uncertainty into account can lead to significant reductions in labor costs. This paper addresses a staff planning and scheduling problem that arises at United States Postal Service (USPS) mail processing & distribution centers (P&DCs) and develops a two-stage stochastic integer program with recourse for the analysis. In the first stage, before the demand is known, the number of full-time and part-time employees is determined for the permanent workforce. In the second stage, the demand is revealed and workers are assigned to specific shifts during the week. When necessary, overtime and casual labor are used to satisfy demand. This paper consists of two parts: (1) the analysis of the demand distribution in light of historical data, and (2) the development and analysis of the stochastic integer programming model. Using weekly demand for a three-year period, we first investigate the possibility that there exists an end-of-month effect, i.e., the week at the end of month has larger volume than the other weeks. We show that the data fail to indicate that this is the case. In the computational phase of the work, three scenarios are considered: high, medium, and low demand. The stochastic optimization problem that results is a large-scale integer program that embodies the full set of contractual agreements and labor rules governing the design of the workforce at a P&DC. The usefulness of the model is evaluated by solving a series of instances constructed from data provided by the Dallas facility. The results indicate that significant savings are likely when the recourse problem is used to help structure the workforce. This work was supported in part by the National Science Foundation under grants DMI-0218701 and DMI-0217927.     

Modeling and analysis of an auction-based logistics market

We consider a logistics spot market where the transportation orders from a number of firms are matched with two types of carriers through a reverse auction. In the spot market, local carriers compete with in-transit carriers that have lower costs. In order to analyze the effects of implementing a logistics spot market on these three parties: firms, local carriers, and in-transit carriers and also the effects of various system parameters, we develop a two-stage stochastic model. We first model the auction in a static setting and determine the expected auction price based on the number of carriers engaging in the auction and their cost distributions. We then develop a continuous-time Markov chain model to evaluate the performance of the system in a dynamic setting with random arrivals and possible abandonment of orders and carriers. By combining these two models, we evaluate the performance measures such as the expected auction price, price paid to the carriers, distribution of orders between local and in-transit carriers, and expected number of carriers and orders waiting at the logistics center in the long run. We present analytical and computational results related to the performance of the system and discuss operation of such a logistics spot market in Turkey.     

Solving project scheduling problem with the philosophy of fuzzy random programming

Project scheduling problem is to determine the schedule of allocating resources to achieve the trade-off between the project cost and the completion time. In real projects, the trade-off between the project cost and the completion time, and the uncertainty of the environment are both considerable aspects for managers. Due to the complex external environment, this paper considers project scheduling problem with coexisted uncertainty of randomness and fuzziness, in which the philosophy of fuzzy random programming is introduced. Based on different ranking criteria of fuzzy random variables, three types of fuzzy random models are built. Besides, a searching approach by integrating fuzzy random simulations and genetic algorithm is designed for searching the optimal schedules. The goal of the paper is to provide a new method for solving project scheduling problem in hybrid uncertain environments.     

A stochastic appointment scheduling system on multiple resources with dynamic call-in sequence and patient no-shows for an outpatient clinic

This research focuses on the stochastic assignment system motivated by outpatient clinics, especially the physical therapy in rehabilitation service. The aim of this research is to develop a stochastic overbooking model to enhance the service quality as well as to increase the utilization of multiple resources, like therapy equipment in a physical therapy room, with the consideration of patients’ call-in sequence. The schedule for a single-service period includes a fixed number of blocks of equal length. When patients call, they are assigned to an appointment time for that block, and an existing appointment is not allowed to be changed. In each visit, a patient might require more than one resource and a probability of no-show. Two estimation methods were proposed for the expected waiting and overtime cost with multiple resources: Convolution Estimation Method and Joint Cumulative Estimation Method for the upper and lower bound value; respectively. A numerical example based on a physical therapy room was used to show that this stochastic model was able to schedule patients for better profitability compared with traditional appointment systems based on four prioritization rules. The workload in each appointment slot was more balanced albeit more patients were assigned to the first slot to fill up the empty room.     

Stochastic optimization of an urban rail timetable under time‐dependent and uncertain demand

Urban rail planning is extremely complex, mainly because it is a decision problem under different uncertainties. In practice, travel demand is generally uncertain, and therefore, the timetabling decisions must be based on accurate estimation. This research addresses the optimization of train timetable at public transit terminals of an urban rail in a stochastic setting. To cope with stochastic fluctuation of arrival rates, a two‐stage stochastic programming model is developed. The objective is to construct a daily train schedule that minimizes the expected waiting time of passengers. Due to the high computational cost of evaluating the expected value objective, the sample average approximation method is applied. The method provided statistical estimations of the optimality gap as well as lower and upper bounds and the associated confidence intervals. Numerical experiments are performed to evaluate the performance of the proposed model and the solution method.     

An airline scheduling model and solution algorithms under stochastic demands

When setting a good flight schedule airlines not only have to consider their fleet supply and related operations, as well as market share, but also stochastic variations caused by daily passenger demands in actual operations. Most of the past research on short-term flight scheduling has used the average passenger demand as input to produce the final timetable and schedule, which means that daily passenger variations that occur in actual operations are neglected. To consider such stochastic disturbances we developed a stochastic-demand scheduling model. We employed arc-based and route-based strategies to develop two heuristic algorithms that can be used to solve the model. The test results, based on a major Taiwan airline’s operation, show the good performance of the model and the solution algorithms.     

An adaptive model with joint chance constraints for a hybrid wind-conventional generator system

We analyze scheduling a hybrid wind-conventional generator system to make it dispatchable, with the aim of profit maximization. Our models ensure that with high probability we satisfy the day-ahead power promised by the model, using combined output of the conventional and wind generators. We consider two scenarios, which differ in whether the conventional generator must commit to its schedule prior to observing the wind-power realizations or has the flexibility to adapt in near real-time to these realizations. We investigate the synergy between the conventional generator and wind farm in these two scenarios. Computationally, the non-adaptive model is relatively tractable, benefiting from a strong extended-variable formulation as an integer program. The adaptive model is a two-stage stochastic integer program with joint chance constraints. Such models have seen limited attention in the literature because of the computational challenges they pose. However, we develop an iterative regularization scheme in which we solve a sequence of sample average approximations under a growing sample size. This reduces computational effort dramatically, and our empirical results suggest that it heuristically achieves high-quality solutions. Using data from a wind farm in Texas, we demonstrate that the adaptive model significantly outperforms the non-adaptive model in terms of synergy between the conventional generator and the wind farm, with expected profit more than doubled.     

A scheduling policy for adjusting economic lot quantities to a feasible solution

A heuristic scheduling policy is introduced for a multi-item, single-machine production facility. The scheduling policy uses the presumed optimal order quantities derived from solving an Economic Lot Size Problem and checks that the quantities obtain a feasible production schedule according to current inventory levels and expected demand rates. If not, the scheduling policy modifies the order quantities to achieve a possible solution without shortages. The scheduling policy is inspired by modification of the similar heuristic Dynamic Cycle Lengths Policy by Leachman and Gascon from 1988, 1991. The main characteristics of this scheduling policy are successive batches of the same item are treated explicitly, due to that it is quite possible that one item be manufactured several times before one other item is manufactured once more; the batches are ordered in increasing run-out time; if the existing situation creates stock-outs with ordinary order quantities, then the order quantities are decreased with a common scaling factor to try to prevent inventory shortages; in case the decrease of the order quantities changes expected run-out times, the batches are reordered after new run-out times; no filling up to an explicit inventory level is done, the filling up is done by the desirable order quantity; to prevent possible excess inventory the policy suggests time periods where no production should be performed. The scheduling policy contains no economical evaluation; this is supposed to be done when the order quantities are calculated, the policy prevents shortages and excess inventory. A numerical example illustrates the suggested scheduling policy. Finally, it is discussed as to how the policy can also take into account stochastic behaviour of the demand rates and compensate the schedule by applying appropriate safety times.     

Single-Machine Scheduling with Exponential Processing Times and General Stochastic Cost Functions

We study a single-machine stochastic scheduling problem with n jobs, in which each job has a random processing time and a general stochastic cost function which may include a random due date and weight. The processing times are exponentially distributed, whereas the stochastic cost functions and the due dates may follow any distributions. The objective is to minimize the expected sum of the cost functions. We prove that a sequence in an order based on the product of the rate of processing time with the expected cost function is optimal, and under certain conditions, a sequence with the weighted shortest expected processing time first (WSEPT) structure is optimal. We show that this generalizes previous known results to more general situations. Examples of applications to practical problems are also discussed.This work was partially supported by the Research Grants Council of Hong Kong under Earmarked Grants No. CUHK4418/99E and No. PolyU 5081/00E.     

An Approach for Strategic Supply Chain Planning under Uncertainty based on Stochastic 0-1 Programming

We present a two-stage stochastic 0-1 modeling and a related algorithmic approach for Supply Chain Management under uncertainty, whose goal consists of determining the production topology, plant sizing, product selection, product allocation among plants and vendor selection for raw materials. The objective is the maximization of the expected benefit given by the product net profit over the time horizon minus the investment depreciation and operations costs. The main uncertain parameters are the product net price and demand, the raw material supply cost and the production cost. The first stage is included by the strategic decisions. The second stage is included by the tactical decisions. A tight 0-1 model for the deterministic version is presented. A splitting variable mathematical representation via scenario is presented for the stochastic version of the model. A two-stage version of a Branch and Fix Coordination (BFC) algorithmic approach is proposed for stochastic 0-1 program solving, and some computational experience is reported for cases with dozens of thousands of constraints and continuous variables and hundreds of 0-1 variables.