Coordinating lead times and safety stocks under autocorrelated demand

We consider a supply chain in which orders and lead times are linked endogenously, as opposed to assuming lead times are exogenous. This assumption is relevant when a retailer’s orders are produced by a supplier with finite capacity and replenished when the order is completed. The retailer faces demands that are correlated over time – either positively or negatively – which may, for example, be induced by a pricing or promotion policy. The auto-correlation in demand affects the order stream placed by the retailer onto the supplier, and this in turn influences the resulting lead times seen by the retailer. Since these lead times also determine the retailer’s orders and its safety stocks (which the retailer must set to cover lead time demand), there is a mutual dependency between orders and lead times. The inclusion of endogenous lead times and autocorrelated demand represents a better fit with real-life situations. However, it poses some additional methodological issues, compared to assuming exogenous lead times or stationary demand processes that are independent over time. By means of a Markov chain analysis and matrix analytic methods, we develop a procedure to determine the distribution of lead times and inventories, that takes into account the correlation between orders and lead times. Our analysis shows that negative autocorrelation in demand, although more erratic, improves both lead time and inventory performance relative to IID demand. Positive correlation makes matters worse than IID demand. Due to the endogeneity of lead times, these effects are much more pronounced and substantial error may be incurred if this endogeneity is ignored.     

Analyzing <Emphasis Type="Italic">M/M/</Emphasis>1 Queues with Perturbations in the Arrival Process

This paper investigates when the M/M/1 model can be used to predict accurately the operating characteristics of queues with arrival processes that are slightly different from the Poisson process assumed in the model. The arrival processes considered here are perturbed Poisson processes. The perturbations are deviations from the exponential distribution of the inter-arrival times or from the assumption of independence between successive inter-arrival times. An estimate is derived for the difference between the expected numbers in perturbed and M/M/1 queueing systems with the same traffic intensity. The results, for example, indicate that the M/M/1 model can predict the performance of the queue when the arrival process is perturbed by inserting a few short inter-arrival times, an occasional batch arrival or small dependencies between successive inter-arrival times. In contrast, the M/M/1 is not a good model when the arrival process is perturbed by inserting a few long inter-arrival times.     

A framework for user equilibrium dynamic traffic assignment

Several analytic approaches have been developed to describe or predict traffic flows on networks with time-varying (dynamic) travel demands, flows and travel times. A key component of these models lies in modelling the flows and/or travel times on the individual links, but as this is made more realistic or accurate it tends to make the overall model less computationally tractable. To help overcome this, and for other reasons, we develop a bi-level user equilibrium (UE) framework that separates the assignment or loading of flows on the time–space network from the modelling of flows and trip times within individual links. We show that this model or framework satisfies appropriate definitions of UE satisfies a first-in-first-out (FIFO) property of road traffic, and has other desirable properties. The model can be solved by iterating between (a) a linear network-loading model that takes the lengths of time–space links as fixed (within narrow ranges), and (b) a set of link flow sub-models which update the link trip times to construct a new time–space network. This allows links to be processed sequentially or in parallel and avoids having to enumerate paths and compute path flows or travel times. We test and demonstrate the model and algorithms using example networks and find that the algorithm converges quickly and the solutions behave as expected. We show how to extend the model to handle elastic demands, multiple destinations and multiple traffic types, and traffic spillback within links and from link to link.     

The impact of stochastic lead time reduction on inventory cost under order crossover

We use exponential lead times to demonstrate that reducing mean lead time has a secondary reduction of the variance due to order crossover. The net effect is that of reducing the inventory cost, and if the reduction in inventory cost overrides the investment in lead time reduction, then the lead time reduction strategy would be tenable.We define lead time reduction as the process of decreasing lead time at an increased cost. To date, decreasing lead times has been confined to deterministic instances. We examine the case where lead times are exponential, for when lead times are stochastic, deliveries are subject to order crossover, so that we must consider effective lead times rather than the actual lead times. The result is that the variance of these lead times is less than the variance of the original replenishment lead times.Here we present a two-stage procedure for reducing the mean and variance for exponentially distributed lead times. We assume that the lead time is made of one or several components and is the time between when the need of a replenishment order is determined to the time of receipt.     

A Class of Single Machine Central Tendency-Dispersion Bicriteria Problems

In this paper, a number of non-regular bicriteria penalty functions of completion times on a single machine are studied. In each function, one criterion is a measure of central tendency (CT) of completion times, for example, mean or median, and the other is a measure of completion time dispersion (DSP). Five different DSP measures are considered in the paper. We discuss the characterizations of optimal sequences for some new functions and summarize previous results when appropriate for the pure bicriteria problem as well as for the convex combination of CT and DSP. Further, in the context of minimizing a dispersion measure, a comparison is made between the two dispersion measures of variance of completion times and total absolute deviations of completion times (TADC).     

Stability,monotonicity and invariant quantities in general polling systems

Consider a polling system withK1 queues and a single server that visits the queues in a cyclic order. The polling discipline in each queue is of general gated-type or exhaustive-type. We assume that in each queue the arrival times form a Poisson process, and that the service times, the walking times, as well as the set-up times form sequences of independent and identically distributed random variables. For such a system, we provide a sufficient condition under which the vector of queue lengths is stable. We treat several criteria for stability: the ergodicity of the process, the geometric ergodicity, and the geometric rate of convergence of the first moment. The ergodicity implies the weak convergence of station times, intervisit times and cycle times. Next, we show that the queue lengths, station times, intervisit times and cycle times are stochastically increasing in arrival rates, in service times, in walking times and in setup times. The stability conditions and the stochastic monotonicity results are extended to the polling systems with additional customer routing between the queues, as well as bulk and correlated arrivals. Finally, we prove that the mean cycle time, the mean intervisit time and the mean station times are invariant under general service disciplines and general stationary arrival and service processes.     

A polynomial time heuristic for the two-machine flowshop scheduling problem with setup times and random processing times

The two-machine flowshop scheduling problem to minimize makespan is addressed. Jobs have random processing times which are bounded within certain intervals. The distributions of job processing times are not known. This problem has been addressed in the literature with the assumption that setup times are included in processing times or are zero. In this paper, we relax this assumption and treat setup times as separate from processing times. We propose a polynomial time heuristic algorithm. Both Johnson algorithm and Yoshida and Hitomi algorithm, both of which developed for the deterministic problem, are special cases of the proposed algorithm. The heuristic algorithm uses a weighted average of lower and upper bounds for processing times. For different weights, the results of the proposed algorithm are compared based on randomly generated data. The computational analysis has shown that the proposed algorithm, with equal weights given to the lower and upper bounds, performs considerably well with an overall average error of 0.36%. The analysis has also shown that the proposed algorithm can safely be used regardless of processing time distributions and the range between lower and upper bounds.     

A Study of Multiple Finite-Source Queueing Models

In this paper, the effects of the head-of-the-line priority and the first-come-first-served service disciplines and the variability of the service-time density functions on the mean values of performance measures of multiple finite-source queueing models are studied. In these models, with a single server, the times between the service completion and the next service requirement are exponentially distributed and the service times follow exponential, hypo-exponential or hyper-exponential probability density functions. The effects are compared with the known behaviour of multiple infinite-source queueing models.     

Travel times in queueing networks and network sojourns

We first describe expected values of sojourn times for semi-stationary (or synchronous) networks. This includes sojourn times for units and sojourn times for the entire network. A typical sojourn time of a unit is the time it spends in a sector (set of nodes) while it travels through the network, and a typical network sojourn time is the busy period of a sector. Our results apply to a wide class of networks including Jackson networks with general service times, general Markov or regenerative networks, and networks with batch processing and concurrent movement of units. The results also shed more light on when Little's law for general systems, holds for expectations as well as for limiting averages. Next, we describe the expectation of a unit's travel time on a general route in a basic Markov network process (such as a Jackson process). Examples of travel times are the time it takes for a unit to travel from one sector to another, and the time between two successive entrances to a node by a unit. Finally, we characterize the distributions of the sojourn times at nodes on certain overtake-free routes and the travel times on such routes for Markov network processes.This research was supported in part by the Air Force Office of Scientific Research under contract 89-0407 and NSF grant DDM-9007532.     

On the construction of analytic solutions for a diffusion-reaction equation with a discontinuous switch mechanism

The existence of waiting times, before boundary motion sets in, for a diffusion-diffusion reaction equation with a discontinuous switch mechanism, is demonstrated. Limit cases of the waiting times are discussed in mathematical rigor. Further, analytic solutions for planar and circular wounds are derived. The waiting times, as predicted using these analytic solutions, are perfectly between the derived bounds. Furthermore, it is demonstrated by both physical reasoning and mathematical rigor that the movement of the boundary can be delayed once it starts moving. The proof of this assertion resides on continuity and monotonicity arguments. The theory sustains the construction of analytic solutions. The model is applied to simulation of biological processes with a threshold behavior, such as wound healing or tumor growth.     

Path comparisons for a priori and time-adaptive decisions in stochastic,time-varying networks

Travel times in congested transportation networks are time-varying quantities that can at best be known a priori probabilistically. In such networks, the arc weights (travel times) are represented by random variables whose probability distribution functions vary with time. These networks are referred to herein as stochastic, time-varying, or STV, networks. The determination of “least time” routes in STV networks is more difficult than in deterministic networks, in part because, for a given departure time, more than one path may exist between an origin and destination, each with a positive probability of having the least travel time. In this paper, measures for comparing time-varying, random path travel times over a time period are given for both a priori optimization and time-adaptive choices (where a driver may react to revealed arrival times at intermediate nodes). The resulting measures are central to the development of methodologies for determining “optimal” paths in STV networks.     

User equilibrium traffic network assignment with stochastic travel times and late arrival penalty

The classical Wardrop User Equilibrium (UE) assignment model assumes traveller choices are based on fixed, known travel times, yet these times are known to be rather variable between trips, both within and between days; typically, then, only mean travel times are represented. Classical Stochastic User Equilibrium (SUE) methods allow the mean travel times to be differentially perceived across the population, yet in a conventional application neither the UE or SUE approach recognises the travel times to be inherently variable. That is to say, there is no recognition that drivers risk arriving late at their destinations, and that this risk may vary across different paths of the network and according to the arrival time flexibility of the traveller. Recent work on incorporating risky elements into the choice process is seen either to neglect the link to the arrival constraints of the traveller, or to apply only to restricted problems with parallel alternatives and inflexible travel time distributions. In the paper, an alternative approach is described based on the ‘schedule delay’ paradigm, penalising late arrival under fixed departure times. The approach allows flexible travel time densities, which can be fitted to actual surveillance data, to be incorporated. A generalised formulation of UE is proposed, termed a Late Arrival Penalised UE (LAPUE). Conditions for the existence and uniqueness of LAPUE solutions are considered, as well as methods for their computation. Two specific travel time models are then considered, one based on multivariate Normal arc travel times, and an extended model to represent arc incidents, based on mixture distributions of multivariate Normals. Several illustrative examples are used to examine the sensitivity of LAPUE solutions to various input parameters, and in particular its comparison with UE predictions. Finally, paths for further research are discussed, including the extension of the model to include elements such as distributed arrival time constraints and penalties.     

A linear regression model with persistent level shifts: An alternative to infill asymptotics

A changepoint in a time series is a time of change in the marginal distribution, autocovariance, or any other distributional structure of the series. Examples include mean level shifts and volatility (variance) changes. Climate data, for example, is replete with mean shift changepoints, occurring whenever a recording instrument is changed or the observing station is moved. Here, we consider the problem of incorporating known changepoint times into a regression model framework. Specifically, we establish consistency and asymptotic normality of ordinary least squares regression estimators that account for an arbitrary number of mean shifts in the record. In a sense, this provides an alternative to the customary infill asymptotics for regression models that assume an asymptotic infinity of data observations between all changepoint times.     

Estimating bus passenger waiting times from incomplete bus arrivals data

This paper considers the problem of estimating bus passenger waiting times at bus stops using incomplete bus arrivals data. This is of importance to bus operators and regulators as passenger waiting time is a key performance measure. Average waiting times are usually estimated from bus headways, that is, time gaps between buses. It is both time-consuming and expensive to measure bus arrival times manually so methods using automatic vehicle location systems are attractive; however, these systems do not usually provide 100% data coverage and missing data are problematical. The paper contributes to the general theory of estimating headway variance using incomplete data. Various methods for replacing missing buses or discarding spurious bus headways are compared and tested on different data sets.     

The track formulation for the Train Dispatching problem

With few exceptions, train movements are still controlled by human operators, the dispatchers. They establish routes and precedence between trains in real-time in order to cope with normal operations but also to recover from deviations from the timetable, and minimize overall delays. Implicitly they tackle and solve repeatedly a hard optimization problem, the Train Dispatching Problem. We recently developed a decomposition approach which allowed us to solve real-life instances to optimality or near optimality in times acceptable for dispatchers. We present here some new ideas which appear to significantly reduce computational times while solving to optimality even large instances.     

Scheduling time-dependent jobs under mixed deterioration

We consider a new model of time-dependent scheduling. A set of deteriorating jobs has to be processed on a single machine which is available starting from a non-zero time. The processing times of some jobs from this set are constant, while other ones are either proportional or linear functions of the job starting times. The applied criteria of schedule optimality include the maximum completion time, the total completion time, the total weighted completion time, the maximum lateness and the number of tardy jobs. We delineate a sharp boundary between computationally easy and difficult problems, showing polynomially solvable and NP-hard cases.     

Subgame-perfection in free transition games

We prove the existence of a subgame-perfect ε-equilibrium, for every ε > 0, in a class of multi-player games with perfect information, which we call free transition games. The novelty is that a non-trivial class of perfect information games is solved for subgame-perfection, with multiple non-terminating actions, in which the payoff structure is generally not (upper or lower) semi-continuous. Due to the lack of semi-continuity, there is no general rule of comparison between the payoffs that a player can obtain by deviating a large but finite number of times or, respectively, infinitely many times. We introduce new techniques to overcome this difficulty.     

Estimation of Travel Times in Multiple Mode Systems<Superscript>†</Superscript>

This paper describes a procedure for generating estimates of the minimum travel times (shortest distances, least cost routes) between pairs of points on a standard map. The procedure exhibits substantial improvements in accuracy over the traditional generation methods involving simple orthogonal and vector-directed distance metrics. These improvements are achieved by combining the traditional methods with algorithms which find shortest routes in networks. The new procedure is particularly appropriate to the analysis of transportation or distribution systems which entail "multiple-mode travel", e.g. surface road vs. expressway travel, or railway vs. air travel. The advantages of the procedure are illustrated with empirical evidence from a simulation study of travel times in a large urban area. Finally, the generality of this procedure to a wide class of problems is discussed.     

Using copulas to model repeat purchase behaviour – An exploratory analysis via a case study

We develop a model of the evolution of inter-purchase times for a consumer-packaged product. After the introduction of the product, a consumer waits to make the initial purchase, then either waits to repurchase or decides not to. A repurchasing consumer repeats this decision process. The components of the model are the repurchase probability and the density function of the time to repurchase at each stage of the purchasing cycle. Issues of interest are: the strength of the dependency between successive repurchase times; the number of repeat purchases before stability occurs; the effects of consumer characteristics on inter-purchase times. The model of individual purchasing behaviour can be transformed via simulation to produce sales time series for a given population. As an example, the model is estimated for a product using Australian panel data. The accuracy of the model’s prediction is compared with an existing model.