Operations & Supply Chain Management

In 1991, D. J. Bertsimas and G. van Ryzin introduced and analyzed a model for stochastic and dynamic vehicle routing in which a single, uncapacitated vehicle traveling at a constant velocity in a Euclidian region must service demands whose time of arrival, location and on-site service are stochastic. The objective is to find a policy to service demands over an infinite horizon that minimizes the expected system time (wait plus service) of the demands. This paper extends our analysis in several directions.

We investigate optimal production controls for a tandem two-machine system with an internal buffer and unreliable machines. First, numerical methods are used to generate optimal policies for specific examples. Then, based on diese numerical results, an approximate suboptimal control policy is developed that divides the state space into distinct regions and uses only simple hedging-point policies in each region. Algorithms to obtain hedging points are provided.

In this chapter we discuss planning models for multi-echelon systems which allow for uncertain and nonstationary demand and lead time processes. We confine ourselves to so-called PUSH systems with a central decision maker, who possesses continuously or periodically updated information about all inventories of all products at all relevant facilities and production stages; all replenishment decisions in the system are determined centrally on the basis of this information.

We develop a simple O(n log n) solution method for the standard lot-sizing model with backlogging and a study horizon of n periods. Production costs are fixed plus linear and holding and backlogging costs are linear with general time-dependent parameters. The algorithm has linear [O(n)] time complexity for several important subclasses of the general model. We show how a slight adaptation of the algorithm can be used for the detection of a minimal forecast horizon and associated planning horizon.

We consider an inventory system with compound Poisson demands replenished by discrete production of units on a single-server facility. This facility may start a vacation at any production completion epoch; at the completion of a vacation the inventory level is inspected to decide whether or not to resume production. Unit production and vacation times are independent and identically distributed with general distributions.

We consider distribution systems with a single depot and many retailers each of which faces external demands for a single item that occurs at a specific deterministic demand rate. All stock enters the systems through the depot where it can be stored and then picked up and distributed to the retailers by a fleet of vehicles, combining deliveries into efficient routes. We extend earlier methods for obtaining low complexity lower bounds and heuristics for systems without central stock.

Manufacturing and service organizations routinely face the challenge of scheduling jobs, orders, or individual customers in a schedule that optimizes either (i) an aggregate efficiency measure, (ii) a measure of performance balance, or (iii) some combination of these two objectives. We address these questions for single-machine job scheduling systems with fixed or controllable due dates.

We consider a production/distribution network represented by a general directed acyclic network. Each node is associated with a specific "product" or item at a given location and/or production stage. An arc (i, j) indicates that item i is used to "produce" item j. External demands may occur at any of the network's nodes. These demands occur continuously at item specific constant rates. Components may be assembled in any given proportions.

We consider inventory systems with several distinct items. Demands occur at constant, item specific rates. The items are interdependent because of jointly incurred fixed procurement costs: The joint cost structure reflects general economies of scale, merely assuming a monotonicity and concavity (submodularity) property. Under a power-of-two policy each item is replenished with constant reorder intervals which are power-of-two multiples of some fixed or variable base planning period.