bluuebunny/crossref_metadata_2025 huggingface dataset:
Optimal Scheduling of Fallible Inspections
Authors: Parmigiani Giovanni
Published: November 2008

This paper gives the exact optimal solution to the problem of designing inspection schedules with fallible and time-consuming test procedures. The optimality criterion is designed to achieve a balance between the cost of inspections and the cost of undetected failure. The solution is derived in continuous time, with arbitrary failure distribution, and is based on infinite-horizon dynamic programming with time-dependent utilities, and with an additional optimization with respect to initial conditions. Results include uniqueness and monotonicity properties of the optimal solution, as well as computational algorithms.
Spatial Market Policy Modeling with Goal Targets
Authors: Nagurney Anna , Thore Sten , Pan Jie
Published: November 2008

In this paper we show how the theory of variational inequalities can be applied to the formulation, qualitative analysis, and computation of a new competitive spatial market model in the presence of goal targets. The model allows the decision maker to impose supply goals at production locations, demand goals at consumption locations, and transportation goals between supply and demand locations, along with associated penalties for failure to comply. This work may be viewed as a contribution to the growing literature on the development of mathematical methodologies for policy modeling.
On the Max-Min 0-1 Knapsack Problem with Robust Optimization Applications
Authors: Yu Gang
Published: November 2008

Given a set of items, a set of scenarios, and a knapsack of fixed capacity, a nonnegative weight is associated with each item; and a value is associated with each item under each scenario. The max-min Knapsack (MNK) problem is defined as filling the knapsack with a selected set of items so that the minimum total value gained under all scenarios is maximized. The MNK problem is a generalization of the conventional knapsack problem to situations with multiple scenarios. This extension significantly enlarges its scope of applications, especially in the application of recent robust optimization developments. In this paper, the MNK problem is shown to be strongly NP-hard for an unbounded number of scenarios and pseudopolynomially solvable for a bounded number of scenarios. Effective lower and upper bounds are generated by surrogate relaxation. The ratio of these two bounds is shown to be bounded by a constant for situations where the data range is limited to be within a fixed percentage from its mean. This result leads to an approximation algorithm for MNK in the special case. A branch-and-bound algorithm has been implemented to efficiently solve the MNK problem to optimality. Extensive computational results are presented.
A Two-State Partially Observable Markov Decision Process with Uniformly Distributed Observations
Authors: Grosfeld-Nir Abraham
Published: November 2008

A controller observes a production system periodically, over time. If the system is in the GOOD state during one period, there is a constant probability that it will deteriorate and be in the BAD state during the next period (and remains there). The true state of the system is unobservable and can only be inferred from observations (quality of output). Two actions are available: CONTINUE or REPLACE (for a fixed cost). The objective is to maximize the expected discounted value of the total future income. For both the finite- and infinite-horizon problems, the optimal policy is of a CONTROL LIMIT (CLT) type: continue if the good state probability exceeds the CLT, and replace otherwise. The computation of the CLT involves a functional equation. An analytical solution for this equation is as yet unknown.

For uniformly distributed observations we obtain the infinite-horizon CLT analytically. We also show that the finite horizon CLTs, as a function of the time remaining, are not necessarily monotone, which is counterintuitive.
Minimizing Some Cost Functions Related to Both Burn-In and Field Use
Authors: Mi Jie
Published: November 2008

Burn-in procedure is used to improve the quality of products. In field operation only those components which survive the burn-in process will be used. Various additive cost functions are considered in this paper. One part of the cost function is the expense incurred until the first component surviving burn-in is obtained. The other part of cost function is either (i) the gain proportional to the mean life in field operation or (ii) the expenditure due to replacement at failure during field operation. We assume that the component before undergoing the burn-in procedure has a bathtub-shaped failure rate function with change points t1 and t2. It is shown that the optimal burn-in time b* minimizing the cost function is always before t1. It is also shown that a large initial failure rate justifies burn-in, i.e., b* > 0.
A Survey of Machine Scheduling Problems with Blocking and No-Wait in Process
Authors: Hall Nicholas G. , Sriskandarajah Chelliah
Published: November 2008

An important class of machine scheduling problems is characterized by a no-wait or blocking production environment, where there is no intermediate buffer between machines. In a no-wait environment, a job must be processed from start to completion, without any interruption either on or between machines. Blocking occurs when a job, having completed processing on a machine, remains on the machine until a downstream machine becomes available for processing. A no-wait or blocking production environment typically arises from characteristics of the processing technology itself, or from the absence of storage capacity between operations of a job. In this review paper, we describe several well-documented applications of no-wait and blocking scheduling models and illustrate some ways in which the increasing use of modern manufacturing methods gives rise to other applications. We review the computational complexity of a wide variety of no-wait and blocking scheduling problems and describe several problems which remain open as to complexity. We study several deterministic flowshop, jobshop, and openshop problems and describe efficient and enumerative algorithms, as well as heuristics and results about their performance. The literature on stochastic no-wait and blocking scheduling problems is also reviewed. Finally, we provide some suggestions for future research directions.
Pooled Testing for HIV Screening: Capturing the Dilution Effect
Authors: Wein Lawrence M. , Zenios Stefanos A.
Published: November 2008

We study pooled (or group) testing as a cost-effective alternative for screening donated blood products (sera) for HIV; rather than test each sample individually, this method combines various samples into a pool, and then tests the pool. A group testing policy specifies an initial pool size, and based on the HIV test result, either releases all samples in the pool for transfusion, discards all samples in the pool, or divides the pool into subpools for further testing. We develop a hierarchical statistical model that relates the HIV test output to the antibody concentration in the pool, thereby capturing the effect of pooling together different samples. The model is validated using data from a variety of field studies. The model is embedded into a dynamic programming algorithm that derives a group testing policy to minimize the expected cost due to false negatives, false positives, and testing. Because the implementation of the dynamic programming algorithm is cumbersome, a simplified version of the model is used to develop near optimal heuristic policies. A simulation study shows that significant cost savings can be achieved without compromising the accuracy of the test. However, the efficacy of group testing depends upon the use of a classification rule (that is, discard the samples in the pool, transfuse them or test them further) that is dependent on pool size, a characteristic that is lacking in currently implemented pooled testing procedures.
Single Resource Multi-Item Inventory Systems
Authors: Gallego Guillermo , Queyranne Maurice , Simchi-Levi David
Published: November 2008

We consider two economic order quantity models where multiple items use a common resource. In the tactical model, the objective is to establish and coordinate order quantities to minimize total inventory ordering and carrying costs without ever exceeding a capacity constraint on the resource. In the strategic model, the objective is to establish and coordinate order quantities to minimize the average cost which includes in addition to the ordering and inventory costs, a cost proportional to the peak usage of the resource. The common resource may be space in an automated warehouse or total capital invested in inventory. We show that a lower bound on the peak resource usage, known for certain subsets of policies, is valid for any feasible policy. We use this to derive lower bounds on the optimum average cost for both models and show that simple heuristics for either model have bounded worst-case performance ratios. More sophisticated heuristics require an effort to solve the embedded staggering problem of time-phasing the arrival of the orders to minimize the maximum use of the resource. We develop a heuristic for the staggering problem and use it to obtain efficient heuristics for the strategic and tactical models.
Scheduling Jobs on Several Machines with the Job Splitting Property
Authors: Serafini Paolo
Published: November 2008

This scheduling model is derived from the real problem of scheduling looms in a textile industry. Jobs may be independently split over several specified machines, and preemption is allowed. Deadlines are specified for each job, and jobs are assumed to be available. It is shown that minimizing maximum weighted tardiness can be done in polynomial time. The case of uniform machines (as in the considered application) can be modeled as a network flow, and minimization of maximum tardiness can be done in strongly polynomial time. The case of unrelated machines can be solved either by generalized flow techniques or by Linear Programming. Attention is also focused on the problem of finding so-called Unordered Lexico Optima, in order to schedule nonbinding jobs as early as possible.
A Decomposition Theorem for Polling Models: The Switchover Times are Effectively Additive
Authors: Cooper Robert B. , Niu Shun-Chen , Srinivasan Mandyam M.
Published: November 2008

We consider the classical polling model: queues served in cyclic order with either exhaustive or gated service, each with its own distinct Poisson arrival stream, service-time distribution, and switchover-time (the server's travel time from that queue to the next) distribution. Traditionally, models with zero switchover times (the server travels at infinite speed) and nonzero switchover times have been considered separately because of technical difficulties reflecting the fact that in the latter case the mean cycle time approaches zero as the travel speed approaches infinity. We argue that the zero-switchover-times model is the more fundamental model: the mean waiting times in the nonzero-switchover-times model decompose (reminiscent of vacation models) into a sum of two terms, one being a simple function of the sum of the mean switchover times, and the other the mean waiting time in a “corresponding” model obtained from the original by setting the switchover times to zero and modifying the service-time variances. This generalizes a recent result of S. W. Fuhrmann for the case of constant switchover times, where no variance modification is necessary. The effect of these studies is to reduce computation and to improve theoretical understanding of polling models.
Queue-Length Distribution for the Discriminatory Processor-Sharing Queue
Authors: Rege Kiran M. , Sengupta Bhaskar
Published: November 2008

In this paper, we study a multiple class discriminatory processor-sharing queue. The queue is assumed to have Poisson input and exponentially distributed service times. In this discipline there are K classes of customers. When there are ni customers present in the system of class i(i = 1, …, K), each member of class j receives a fraction of the server's capacity given by αj/∑i=1Kniαi. Thus, associated with class i customers is a weight αi which determines the level of service discrimination. For this problem, we find the moments of the queue-length distribution as a solution of linear simultaneous equations. We also prove a heavy traffic limit theorem for the joint queue-length distribution for this queue.
The Use of Linear Programming in Disentangling the Bankruptcies of Al-Manakh Stock Market Crash
Authors: Elimam Abdelghani A. , Girgis Maurice , Kotob Samir
Published: November 2008

A highly speculative parallel stock market, called Souk al-Manakh, emerged in Kuwait in 1980–81. Due to the absence of checks and balances, the default of one trader led to the collapse of al-Manakh in 1982. This triggered a major financial national crisis as debts arising from the crash reached a staggering US $94 billion, or more than four times Kuwait's GDP. The crash precipitated an economic recession, business failures, and more bankruptcies among traders. It was impossible for the government or the courts to untangle traders, one at a time, due to then simultaneous dependence on, and entanglement with, each other. We designed a linear programming model to disentangle the bankruptcies of al-Manakh's insolvents. It identified solvent from insolvent traders, determined their debt settlement ratios, and set a fair and equitable distribution of debtors' mixed assets to their respective creditors. We demonstrate the special properties of the LP model and its relationship to a system of linear equations through a numerical example. We also present the legal, financial, and economic controversies that arose during the course of resolving the stock market crash, which lasted about four years.
Enforcement or Treatment? Modeling the Relative Efficacy of Alternatives for Controlling Cocaine
Authors: Rydell C. Peter , Caulkins Jonathan P. , Everingham Susan S.
Published: November 2008

This paper presents a model that estimates the relative cost-effectiveness of four cocaine-control programs: three “supply control” programs (source-country control, interdiction, and domestic enforcement) and a “demand control” program (treating heavy users). Treatment emerges as by far the most cost-effective, and sensitivity analyses show that this result is very robust.
Comparison of Some Suboptimal Control Policies in Medical Drug Therapy
Authors: Hu Chuanpu , Lovejoy William S. , Shafer Steven L.
Published: November 2008

In drug therapy, efficient dosage policies are needed to maintain drug concentrations at target. The relationship between the concentration of a drug and the dosages is often described by compartment models in which the parameters are unknown, although prior knowledge may be available and can be updated after blood samples are taken during the therapy. In this paper we define some tractable policies for adaptive control of drug concentrations in compartment models and compare their performances using computer simulation in a one-compartment model. We also discuss the effects of assuming normal priors, discrete approximation of a continuous prior, using nonquadratic costs, and information probing. From the simulation we derive intuition as to what types of policies perform well and address the topic of actively versus passively learning.
On the Analysis of Two New Models for Transporting Hazardous Materials
Authors: Jin Honghua , Batta Rajan , Karwan Mark H.
Published: November 2008

This paper considers two new decision-making problems in the context of transporting hazardous materials (HM). These problems are motivated by the fact that many practical situations only have a finite number of shipments of HM to be made and that shipments are likely to be suspended after a threshold number of accidents. Both problems are nonlinear, constrained shortest path problems. Exact solution methods are proposed and computational results are reported for the case where the threshold number of accidents is one. Extension of the methodology for higher values of the threshold number of accidents is also outlined.
On the Characterization and Measure of Machine Cells in Group Technology
Authors: Ng Shu Ming
Published: November 2008

Group technology plays an important role in the design of an automated manufacturing system. The ideal situation is to partition the machines into machine cells and the parts into part families so that each machine cell together with the part family for the cell is independent of the rest of the system. We will give a characterization of the independent cells for an arbitrary manufacturing system. An efficient algorithm to identify these independent cells will also be discussed. An effective policy for subcell formation (not necessarily independent) from larger cells will also be discussed. Computational results show that our algorithms always obtain solutions with higher grouping efficiency compared with some of the existing algorithms. We also discuss the effectiveness of grouping efficiency as a measure for group technology.
Exponential Approximations for Tail Probabilities in Queues II: Sojourn Time and Workload
Authors: Abate Joseph , Choudhury Gagan L. , Whitt Ward
Published: November 2008

We continue to focus on simple exponential approximations for steady-state tail probabilities in queues based on asymptotics. For the G/GI/1 model with i.i.d. service times that are independent of an arbitrary stationary arrival process, we relate the asymptotics for the steady-state waiting time, sojourn time, and workload. We show that the three asymptotic decay rates coincide and that the three asymptotic constants are simply related. We evaluate the exponential approximations based on the exact asymptotic parameters and their approximations by making comparisons with exact numerical results for BMAP/G/1 queues, which have batch Markovian arrival processes. Numerical examples show that the exponential approximations for the tail probabilities are remarkably accurate at the 90th percentile and beyond. Thus, these exponential approximations appear very promising for applications.
Shop Problems With Two Machines and Time Lags
Authors: Dell'Amico Mauro
Published: November 2008

We consider Job-Shop and Flow-Shop scheduling problems with two machines, no more than two operations per job, and Time Lags, i.e., a minimum time interval between the completion time of the first operation and the starting time of the second one. We give complexity results for the preemptive and nonpreemptive cases and study the relationship between the two problems. For the Flow-Shop problem we give lower bounds and upper bounds and analyze their worst-case performances. Finally we define a Tabu Search algorithm and prove the effectiveness of the proposed bounds through extensive computational results.
Recursive Utility for Stochastic Trees
Authors: Hazen Gordon B. , Pellissier James M.
Published: November 2008

Stochastic trees are semi-Markov processes represented using tree diagrams. Such trees have been found useful for prescriptive modeling of temporal medical treatment choice. We consider utility functions over stochastic trees which permit recursive evaluation in a graphically intuitive manner analogous to decision tree rollback. Such rollback is computationally intractable unless a low-dimensional preference summary exists. We present the most general classes of utility functions having specific tractable preference summaries. We examine three preference summaries—memoryless, Markovian, and semi-Markovian—which promise both computational feasibility and convenience in assessment. Their use is illustrated by application to a previous medical decision analysis of whether to perform carotid endarterectomy.
Combined Multiple Recursive Random Number Generators
Authors: L'Ecuyer Pierre
Published: November 2008

We analyze the random number generators obtained by combining two or more multiple recursive generators. We study the lattice structure of such combined generators and argue that combination is a good way of obtaining robust generators, based on a recurrence with many nonzero coefficients, and which also possess a fast implementation.
Adaptive Routing on the Plane
Authors: Tassiulas Leandros
Published: November 2008

Demands for service arrive at random times, in random locations, in a region of the plane. The service time of each demand is random. A server that travels with constant speed moves from demand to demand providing service. The server spends its time either in providing service or in traveling. The objective is to route the server, based on the location of the current demands on the plane and the anticipated demand arrivals, such that the time spent in traveling is minimal and the service is provided efficiently. A routing policy is provided that achieves maximum throughput and is independent of the statistical parameters of the system, under the assumption that the arrival process is Poisson. For a renewal arrival process, a class of policies is specified that achieve maximum throughput based on some knowledge of the system parameters. Finally, an adaptive version of the partitioning policies is given, which makes them independent of the system statistics.
Air Network Design for Express Shipment Service
Authors: Barnhart Cynthia , Schneur Rina R.
Published: November 2008

Express shipment service requires that shipments be picked up and delivered within specified time intervals (e.g., 24 hours, 48 hours or 3–5 days). In this paper, we describe the express shipment service design problem faced by a carrier and present a model and column generation approach for its solution. Our approach can find near optimal air service designs for a fixed aircraft fleet or for a fleet of unspecified size and make-up. In the latter case, the service design, fleet size and fleet composition are determined simultaneously. We have implemented our solution procedure, and a large carrier is using it to plan their air service operations and to evaluate various operating scenarios. The results indicate that service designs are generated that allow for improved service with a reduction in annual operating costs measuring in the millions of dollars.
A Dynamic Subgradient-Based Branch-and-Bound Procedure for Set Covering
Authors: Balas Egon , Carrera Maria C.
Published: November 2008

We discuss a branch and bound algorithm for set covering, whose centerpiece is a new integrated upper bounding/lower bounding procedure called dynamic subgradient optimization (DYNSGRAD). This new procedure, applied to a Lagrangean dual at every node of the search tree, combines the standard subgradient method with primal and dual heuristics that interact to change the Lagrange multipliers and tighten the upper and lower bounds, fix variables, and periodically restate the Lagrangean itself. Extensive computational testing is reported. As a stand-alone heuristic, DYNSGRAD performs significantly better than other procedures in terms of the quality of solutions obtainable with a certain computational effort. When incorporated into a branch-and-bound algorithm, DYNSGRAD considerably advances the state of the art in solving set covering problems.
New Second-Order Bounds on the Expectation of Saddle Functions with Applications to Stochastic Linear Programming
Authors: Edirisinghe N. C. P.
Published: November 2008

This paper develops new bounds on the expectation of a convex-concave saddle function of a random vector with compact domains. The bounds are determined by replacing the underlying distribution by unique discrete distributions, constructed using second-order moment information. The results extend directly to new second moment lower bounds in closed-form for the expectation of a convex function. These lower bounds are better than Jensen's bound, the only previously known lower bound for the convex case, under limited moment information. Application of the second moment bounds to two-stage stochastic linear programming is reported. Computational experiments, using randomly generated stochastic programs, indicate that the new bounds may easily outperform the usual first-order bounds.
An Algorithm for Multistage Dynamic Networks with Random Arc Capacities, with an Application to Dynamic Fleet Management
Authors: Cheung Raymond K. , Powell Warren B.
Published: November 2008

We consider the class of multistage dynamic networks with random arc capacities a framework that is well suited to model dynamic fleet management problems. We propose a successive convex approximation approach that produces an approximation to the expected recourse function which captures the future effects of current decisions under uncertainty. This method decomposes the network in each stage into tree subproblems, whose expected recourse functions are easy to obtain. We also compare this method with two alternative methods on a set of dynamic fleet management problems. The numerical results show that this method is superior to the two alternative methods.
A Transform-Free Approximation for the Finite Capacity M/G/s Queue
Authors: Kimura Toshikazu
Published: November 2008

This paper develops a transform-free approximation for the steady-state queue-length distribution in an M/G/s queue with finite waiting spaces. The approximation is obtained by using a conservation law and some heuristics. It is shown that the approximation is exact for the cases with either no extra waiting space, exponential service-time distribution, or a certain two-parameter family of service-time distributions. It is also shown that the approximation has the same light-traffic properties as the known light-traffic limit theorem for the infinite capacity case when the number of waiting spaces is not less than one.
Managing Capacity and Flow at Theme Parks
Authors: Ahmadi Reza H.
Published: November 2008

The growth of service industries and their impact on the U.S. economy have attracted considerable attention in recent years. While some service sectors, most notably airline and telecommunication industries, have been in the forefront of model development, the industry is rather fragmented, and similar rigor is lacking in most other sectors.

This paper describes an application of a model-based approach to some of the short-term ride capacity and visitor flow issues faced by the Six Flags Magic Mountain (SFMM), a major national theme park. Specifically, we consider daily operations at the theme park and focus on the generation and evaluation of alternative strategies for managing ride capacities and visitor flow. Management of demand involves two aspects: (a) understanding customer preferences as revealed by routing behavior, and (b) using the model to evaluate the implications of changes in transition-behavior.

A crucial component of the study relates to the empirical data collected. Besides verifying the validity of the models, these data provide several insights for developing schemes to manage the day-to-day operations of the park. The SFMM management was actively involved in various phases of this study and as a result has been introducing the proposed models in a phased manner.
Optimal Load Balancing on Sonet Bidirectional Rings
Authors: Myung Young-Soo , Kim Hu-Gon , Tcha Dong-Wan
Published: November 2008

In this paper we consider the Ring Loading Problem, which arises in the design of SONET bidirectional rings. The issue of demand splitting divides the ring loading problem into the two kinds. One allows a demand to be split and routed in two different directions and the other does not. The former kind becomes a relaxation of the latter. We present an efficient exact solution procedure for the case with demand splitting, and a two-approximation algorithm for the case without demand splitting. Computational results are also shown to prove the efficiency of the proposed procedures.
The Competitive Newsboy
Authors: Lippman Steven A. , McCardle Kevin F.
Published: November 2008

We consider a competitive version of the classical newsboy problem—in which a firm must choose an inventory or production level for a perishable good with random demand, and the optimal solution is a fractile of the demand distribution—and investigate the impact of competition upon industry inventory. A splitting rule specifies how initial industry demand is allocated among competing firms and how any excess demand is allocated among firms with remaining inventory. We examine the relation between equilibrium inventory levels and the splitting rule and provide conditions under which there is a unique equilibrium. Our most general result is that if all excess demand is reallocated, i.e., there is perfect substitutability, then competition never leads to a decrease in industry inventory.
Single Machine Scheduling Problems with General Breakdowns, Earliness and Tardiness Costs
Authors: Federgruen A. , Mosheiov G.
Published: November 2008

In this paper we consider single machine scheduling problems with a common due-date for all jobs, arbitrary monotone earliness and tardiness costs and arbitrary breakdown and repair processes. We show that the problem is equivalent to a deterministic one without breakdowns and repairs and with an equivalent cost function of a job's completion time. A V-shaped schedule without idle times is shown to be optimal, if this equivalent cost function is quasi-convex.

Conversely, we show that a V-shaped schedule may fail to be optimal if the property does not apply. We derive general conditions for the earliness and tardiness cost structure and repair and breakdown processes under which the equivalent cost function is quasi-convex. When a V-shaped schedule is optimal, an efficient (though pseudo-polynomial) algorithm can be used to compute an optimal schedule.
A Genetic Algorithm for the Multiple-Choice Integer Program
Authors: Ben Hadj-Alouane Atidel , Bean James C.
Published: November 2008

We present a genetic algorithm for the multiple-choice integer program that finds an optimal solution with probability one (though it is typically used as a heuristic). General constraints are relaxed by a nonlinear penalty function for which the corresponding dual problem has weak and strong duality. The relaxed problem is attacked by a genetic algorithm with solution representation special to the multiple-choice structure. Nontraditional reproduction, crossover and mutation operations are employed. Extensive computational tests for dual degenerate problem instances show that suboptimal solutions can be obtained with the genetic algorithm within running times that are shorter than those of the OSL optimization routine.
Computational Evaluation of Hierarchical Production Control Policies for Stochastic Manufacturing Systems
Authors: Samaratunga Chand , Sethi Suresh P. , Zhou Xun Yu
Published: November 2008

This paper is concerned with near-optimal control of manufacturing systems consisting of two unreliable machines in tandem and having the objective of minimizing the total discounted cost of inventories/shortages over an infinite horizon. Asymptotic optimal feedback controls are constructed with respect to the rate of machine breakdown/repair as compared to the given discount rate. Performance of these controls, known as hierarchical controls, is compared with the optimal cost (when possible) and the costs obtained with two well-known heuristics, known as Kanban controls and two boundary controls. It is shown that hierarchical controls perform better than Kanban controls in some cases and no worse in others. Costs of hierarchical and two boundary controls are not significantly different, although the former is a simpler policy than the latter. Also examined computationally is the asymptotic nature of hierarchical controls.
One-Warehouse Multiretailer Systems with Centralized Stock Information
Authors: Chen Fangruo , Zheng Yu-Sheng
Published: November 2008

We consider a distribution system with a central warehouse and multiple retailers. The warehouse orders from an outside supplier and replenishes the retailers which in turn satisfy customer demand. The retailers are nonidentical, and their demand processes are independent compound Poisson. There are economies of scale in inventory replenishment, which is controlled by an echelon-stock, batch-transfer policy. For the special case with simple Poisson demand, we develop an exact method for computing the long-run average holding and backorder costs of the system. Based on this exact method, we provide approximations for compound Poisson demand. Numerical examples are used to illustrate the accuracy of the approximations. We also present a numerical comparison between the average costs of a heuristic, echelon-stock policy and an existing lower bound on the average costs of all feasible policies.
Easily Implementable Inventory Control Policies
Authors: Hopp Wallace J. , Spearman Mark L. , Zhang Rachel Q.
Published: November 2008

This work was initiated and supported by a manufacturer of mail processing equipment, which stocks 30,000 distinct parts in a distribution center to support field maintenance of their equipment. To find an effective stocking policy for this system we formulate a constrained optimization model with the objective of minimizing overall inventory investment at the distribution center subject to constraints on customer service and order frequency. Because size, integrality, and nonconvexity make this problem intractable to exact analysis, we develop three heuristic algorithms based on simplified representations of the inventory and service expressions. These lead to what we call easily implementable inventory policies, in which the control parameters for a newly introduced part can be computed in closed form without reoptimizing the rest of the system. Numerical comparisons against a lower bound on the cost function show that even our simplest heuristic works well when a high service level is required. However, we show that a more sophisticated heuristic is more robustly accurate. We also compare our heuristics to methods previously in use by the firm whose system motivated this research and show that they are more efficient in the sense of attaining the same customer service level with a 20–25% smaller inventory investment. Finally, we discuss implementation issues related to the specific needs of the client firm, such as how to handle parts with no or low recent usage and dynamically changing demand for parts.
Rendezvous Search on the Line with More Than Two Players
Authors: Lim Wei Shi , Alpern Steve , Beck Anatole
Published: November 2008

Suppose n blind, speed one, players are placed by a random permutation onto the integers 1 to n, and each is pointed randomly to the right or left. What is the least expected time required form m ≤ n of them to meet together at a single point? If they must all use the same strategy we call this time the symmetric rendezvous value Rn,ms; otherwise the asymmetric value Rn,ma. We show that R3,2a = 47/48, and that Rn,ns is asymptotic to n/2. These results respectively extend those for two players given by Alpern and Gal (Alpern, S., S. Gal. 1995. Rendezvous search on the line with distinguishable players. SIAM J. Control Optim. 33 1270–1276.) and Anderson and Essegaier (Anderson, E. J., S. Essegaier. 1995. Rendezvous search on the line with indistinguishable players. SIAM J. Control Optim. 33 1637–1642.).
Dynamic Programming Strategies for the Traveling Salesman Problem with Time Window and Precedence Constraints
Authors: Mingozzi Aristide , Bianco Lucio , Ricciardelli Salvatore
Published: November 2008

The Traveling Salesman Problem with Time Window and Precedence Constraints (TSP-TWPC) is to find an Hamiltonian tour of minimum cost in a graph G = (X, A) of n vertices, starting at vertex 1, visiting each vertex i ∈ X during its time window and after having visited every vertex that must precede i, and returning to vertex 1. The TSP-TWPC is known to be NP-hard and has applications in many sequencing and distribution problems. In this paper we describe an exact algorithm to solve the problem that is based on dynamic programming and makes use of bounding functions to reduce the state space graph. These functions are obtained by means of a new technique that is a generalization of the “State Space Relaxation” for dynamic programming introduced by Christofides et al. (Christofides, N., A. Mingozzi, P. Toth. 1981b. State space relaxation for the computation of bounds to routing problems. Networks 11 145–164.). Computational results are given for randomly generated test problems.
An Optimization Algorithm for the Vehicle Routing Problem with Time Windows Based on Lagrangian Relaxation
Authors: Kohl Niklas , Madsen Oli B. G.
Published: November 2008

Our paper presents a new optimization method for the Vehicle Routing Problem with Time Windows (VRPTW). The VRPTW is a generalization of the Vehicle Routing Problem, where the service of a customer must start within a given time interval—a so-called time window. Our method is based on a Lagrangian relaxation of the constraint set requiring that each customer must be serviced. The master problem consists of finding the optimal Lagrangian multipliers and the subproblem is a Shortest Path Problem with Time Windows and Capacity Constraints. The optimal multipliers are found using a method exploiting the benefits of subgradient methods as well as a bundle method. The method has been implemented and tested on a series of well-known benchmark problems of size up to 100 customers. Our algorithm turns out to be very competitive compared to algorithms considered in the literature, and we have succeeded in solving several previously unsolved problems.
Pricing, Production, Scheduling, and Delivery-Time Competition
Authors: Lederer Phillip J. , Li Lode
Published: November 2008

This paper studies competition between firms that produce goods or services for customers sensitive to delay time. Firms compete by setting prices and production rates for each type of customer and by choosing scheduling policies. The existence of a competitive equilibrium is proved. The competitive equilibrium is well defined whether or not a firm can differentiate between customers based upon physical characteristics because each customer has incentive to truthfully reveal its delay cost. Further insights are derived in two special cases. A unique equilibrium exists for each of the cases. In the first case, firms are differentiated by cost, mean processing time, and processing time variability, but customers are homogeneous. The conclusions include that a faster, lower variability and lower cost firm always has a larger market share, higher capacity utilization, and higher profits. However, this firm may have higher prices and faster delivery time, or lower prices and longer delivery time. In the second case, firms are differentiated by cost and mean processing time, but customers are differentiated by demand function and delay sensitivity. The results include that customers with higher waiting costs pay higher full prices, and that each firm charges a higher price and delivers faster to more Impatient customers. Competing firms that jointly serve several types of customers tend to match prices and delivery times.
Scheduling in Robotic Cells: Classification, Two and Three Machine Cells
Authors: Hall Nicholas G. , Kamoun Hichem , Sriskandarajah Chelliah
Published: November 2008

This paper considers the scheduling of operations in a manufacturing cell that repetitively produces a family of similar parts on two or three machines served by a robot. We provide a classification scheme for scheduling problems in robotic cells. We discuss finding the robot move cycle and the part sequence that jointly minimize the production cycle time, or equivalently maximize the throughput rate. For multiple part-type problems in a two-machine cell, we provide an efficient algorithm that simultaneously optimizes the robot move and part sequencing problems. This algorithm is tested computationally. For a three-machine cell with general data and identical parts, we address an important conjecture about the optimality of repeating one-unit cycles, and show that such a procedure dominates more complicated cycles producing two units. For a three-machine cell producing multiple part-types, we prove that four out of the six potentially optimal robot move cycles for producing one unit allow efficient identification of the optimal part sequence. Several efficiently solvable special cases with practical relevance are identified, since the general problem of minimizing cycle time is intractable. Finally, we discuss ways in which a robotic cell converges to a steady state.
Multiclass Queueing Systems in Heavy Traffic: An Asymptotic Approach Based on Distributional and Conservation Laws
Authors: Bertsimas Demitris , Mourtzinou Georgia
Published: November 2008

We propose a new approach to analyze multiclass queueing systems in heavy traffic based on what we consider as fundamental laws in queueing systems, namely distributional and conservation laws. Methodologically, we extend the distributional laws from single class queueing systems to multiple classes and combine them with conservation laws to find the heavy traffic behavior of the following systems: (a) ∑GI/G/1 queue under FIFO, (b) ∑GI/G/1 queue with priorities, (c) Polling systems with general arrival distributions. Compared with traditional heavy traffic analysis via Brownian processes, our approach gives new insight to the asymptotics used, solves systems that traditional heavy traffic theory has not fully addressed, and, more importantly, leads to closed form answers, which compared to simulation are very accurate even for moderate traffic.
Proportional Equity Flow Problem for Terminal Arcs
Authors: Betts Lisa M. , Brown J. Randall
Published: November 2008

The proportional equity flow problem extends a class of problems referred to as equity flow problems whose objective is to equitably distribute flow among the arcs in a flow circulation network. The proportionally bounded flow circulation problem places lower and upper bounds on each arc flow that are nondecreasing continuous functions of the flow through one special arc, and the objective is to maximize the flow through the special arc. The proportional equity flow problem for terminal arcs (Problem TA) is then defined as a special case where all the proportional arcs enter a sink vertex. Applications of both the general problem and Problem TA are given. Two optimality conditions for Problem TA are developed, as well as an algorithm that is polynomially bounded for many types of nondecreasing, continuous, proportional bounding functions. Specifically, the algorithm is shown to be polynomially bounded if the largest root of an equation can be found in polynomial time.
A Little's Result Approach to the Service Constrained Spares Provisioning Problem for Repairable Items
Authors: Abboud Nadim E. , Daigle John N.
Published: November 2008

A set of identical machines are deployed to meet a known and constant demand. If a machine fails, a replacement part must be available before repair of the machine may be initiated. If the part is currently out of stock, it must be ordered. Once repaired at one of a finite number of repair stations, the machine serves as an “operational ready” standby if demand is currently being met; otherwise, the machine is immediately deployed. Machine time-to-failure, ordering leadtimes, and repair times are all assumed to be exponentially distributed. The objective is to determine the number of machines and repair channels that minimize a cost function subject to the service constraint; i.e., on average, the number of machines operating should be at least some fraction of the demand. We present an algorithm that efficiently generates all the boundary points of the feasible region, from which the optimal solution is readily identified, for the special cases in which there is either zero or infinite stock. Use of the algorithm, which is based upon Little's result and first-passage time analysis, requires negligible storage and computational effort. In fact, for problems of moderate size, computation of optimal solutions via a nonprogrammable pocket calculator is feasible.
An Approximation Algorithm for the Traveling Salesman Problem with Backhauls
Authors: Gendreau Michel , Laporte Gilbert , Hertz Alain
Published: November 2008

The Traveling Salesman Problem with Backhauls (TSPB) is defined on a graph G = (V, E). The vertex set is partitioned into V = ({v1}, L, B), where v1 is a depot, L is a set of linehaul customers, and B is a set of backhaul customers. A cost matrix satisfying the triangle inequality is defined on the edge set E. The TSPB consists of determining a least-cost Hamiltonian cycle on G such that all vertices of L are visited contiguously after v1, followed by all vertices of B. Following a result by Christofides for the Traveling Salesman Problem, we propose an approximation algorithm with worst-case performance ratio of 3/2 for the TSPB.
Minimizing Makespan in a Class of Reentrant Shops
Authors: Wang M. Y. , Sethi S. P. , van de Velde S. L.
Published: November 2008

We study the problem of scheduling a chain-reentrant shop, in which each job goes for its processing first to a machine called the primary machine, then to a number of other machines in a fixed sequence, and finally back to the primary machine for its last operation. The problem is to schedule the jobs so as to minimize the makespan. This problem is unary NP-hard for a general number of machines. We focus in particular on the two-machine case that is also at least binary NP-hard. We prove some properties that identify a specific class of optimal schedules, and then use these properties in designing an approximation algorithm and a branch-and-bound type optimization algorithm. The approximation algorithm, of which we present three versions, has a worst-case performance guarantee of 3/2 along with an excellent empirical performance. The optimization algorithm solves large instances quickly. Finally, we identify a few well solvable special cases and present a pseudo-polynomial algorithm for the case in which the first and the last operations of any job (on the primary machine) are identical.
Waiting and Interdeparture Times in Priority Queues with Poisson- and General-Arrival Streams
Authors: Stanford David A.
Published: November 2008

This paper presents new results for the interdeparture time distributions in single-server priority queues with an arbitrary number of high-priority Poisson-arrival classes and one lowest-priority general-arrival class. Little-known results for the waiting time distributions in the same queue are presented, including a new proof for the powerful result that the waiting time distribution in the non-preemptive priority queue is insensitive to the interarrival time distributions of lower-priority classes, beyond their mean.
A Minimal Algorithm for the 0-1 Knapsack Problem
Authors: Pisinger David
Published: November 2008

Several types of large-sized 0-1 Knapsack Problems (KP) may be easily solved, but in such cases most of the computational effort is used for sorting and reduction. In order to avoid this problem it has been proposed to solve the so-called core of the problem: a Knapsack Problem defined on a small subset of the variables. The exact core cannot, however, be identified before KP is solved to optimality, thus, previous algorithms had to rely on approximate core sizes.

In this paper we present an algorithm for KP where the enumerated core size is minimal, and the computational effort for sorting and reduction also is limited according to a hierarchy. The algorithm is based on a dynamic programming approach, where the core size is extended by need, and the sorting and reduction is performed in a similar “lazy” way.

Computational experiments are presented for several commonly occurring types of data instances. Experience from these tests indicate that the presented approach outperforms any known algorithm for KP, having very stable solution times.