A branch-and-price algorithm for an integrated production and inventory routing problem

With globalization, the need to better integrate production and distribution decisions has become ever more pressing for manufacturers trying to streamline their supply chain. This paper investigates a previously developed mixed-integer programming (MIP) model aimed at minimizing production, inventory, and delivery costs across the various stages of the system. The problem being modeled includes a single production facility, a set of customers with time varying demand, a finite planning horizon, and a fleet of homogeneous vehicles. Demand can be satisfied from either inventory held at a customer site or from daily product distribution. Whether a customer is visited on a particular day is determined by an implicit tradeoff between inventory and distribution costs. Once the decision is made, a vehicle routing problem must be solved for those customers who are scheduled for a delivery.A hybrid methodology that combines exact and heuristic procedures within a branch-and-price framework is developed to solve the underlying MIP. The approach takes advantage of the efficiency of heuristics and the precision of branch and price. Implementation required devising a new branching strategy to accommodate the unique degeneracy characteristics of the master problem, and a new procedure for handling symmetry. A novel column generation heuristic and a rounding heuristic were also implemented to improve algorithmic efficiency. Computational testing on standard data sets showed that the hybrid scheme can solve instances with up to 50 customers and 8 time periods within 1 h. This level of performance could not be matched by either CPLEX or standard branch and price alone.     

Multiplexing of periodic arrival processes with different packet sizes

For the N * D/D/1 queue, the exact formulas for the virtual waiting time distribution and the waiting time distribution are well known. The exact formulas are extended to the case of the /spl Sigma/ N/sub k/D(X/sub k/)/D/1 queue, where different arrival processes can have different packet sizes. Numerical examples are also presented to illustrate their practical applications.     

Pade approximation for stochastic discrete-event systems

We show that Pade approximation can be effectively used for approximation of performance functions in discrete-event systems. The method is (1) obtaining the MacLaurin coefficients of the performance function and (2) finding a Pade approximant from the MacLaurin coefficients and use it to approximate the function. We use the method with the expected number of renewals in a random interval, GI/G/1 systems, and inventory systems. The results are very good     

Network dimensioning at the call level for the always‐on network

It is becoming common for the network to provide always‐on access services, where subscribers are guaranteed that their call requests will never be blocked. This paper studies the call‐level link dimensioning for the always‐on network with single‐class traffic. The call‐level QoS requirement is expressed in terms of the probability of a poor‐quality call, which is the probability that a call experiences packet‐level QoS violation at any time during its duration, as opposed to the probability of blocking in the network with call admission control (CAC). The system is modelled as the M/M/infinite system with finite population and an analytic expression for the probability of a poor‐quality call is derived based on performability analysis. The effects of the call‐level traffic characteristics on the required link resources are studied. It is also shown that the call‐level link dimensioning for the always‐on network needs more link resources than the network with CAC, and the call‐level link dimensioning based on the analytic expression can be used to conservatively dimension the always‐on network with arbitrarily distributed call holding time and inter‐call time. The paper also studies the problem of estimating the call‐level traffic characteristics when the knowledge of call boundaries is not available. Copyright © 2004 John Wiley & Sons, Ltd.     

Heuristics for a multiperiod inventory routing problem with production decisions

Manufacturers who resupply a large number of retailers on a periodic basis continually struggle with the question of how to formulate a replenishment strategy. This paper presents a comparative analysis of a series of heuristics for an inventory routing problem (IRP) that arises in a manufacturing supply chain. The IRP is formulated as a mixed integer program with the objective of maximizing the net benefits associated with making deliveries in a specific time period to a widely dispersed set of customers. It is assumed that inventory can accumulate at the customer sites, but that all demand must be met without backlogging. Because optimal solutions were not within reach of exact methods, a two-step procedure was developed that first estimates daily delivery quantities and then solves a vehicle routing problem for each day of the planning horizon. As part of the methodology, a linear program is used to determine which days it is necessary to make at least some deliveries to avoid stockouts.The IRP is investigated in the context of an integrated production–inventory–distribution–routing problem (PIDRP). The full model takes into account production decisions and inventory flow balance in each period. For the computations, a previously developed branch-and-price algorithm is used that requires the solution of multiple IRPs (one in each period) to generate columns for the master problem. Testing showed that PIDRP instances with up to eight time periods and 50 customers can be solved within 1 h. This level of performance could not be matched by either CPLEX or an exact version of the branch-and-price algorithm.     

The integrated production–inventory–distribution–routing problem

The integration of production and distribution decisions presents a challenging problem for manufacturers trying to optimize their supply chain. At the planning level, the immediate goal is to coordinate production, inventory, and delivery to meet customer demand so that the corresponding costs are minimized. Achieving this goal provides the foundations for streamlining the logistics network and for integrating other operational and financial components of the system. In this paper, a model is presented that includes a single production facility, a set of customers with time varying demand, a finite planning horizon, and a fleet of vehicles for making the deliveries. Demand can be satisfied from either inventory held at the customer sites or from daily product distribution. In the most restrictive case, a vehicle routing problem must be solved for each time period. The decision to visit a customer on a particular day could be to restock inventory, meet that day’s demand or both. In a less restrictive case, the routing component of the model is replaced with an allocation component only. A procedure centering on reactive tabu search is developed for solving the full problem. After a solution is found, path relinking is applied to improve the results. A novel feature of the methodology is the use of an allocation model in the form of a mixed integer program to find good feasible solutions that serve as starting points for the tabu search. Lower bounds on the optimum are obtained by solving a modified version of the allocation model. Computational testing on a set of 90 benchmark instances with up to 200 customers and 20 time periods demonstrates the effectiveness of the approach. In all cases, improvements ranging from 10–20% were realized when compared to those obtained from an existing greedy randomized adaptive search procedure (GRASP). This often came at a three- to five-fold increase in runtime, however.     

Efficiency and reliability of call admission control schemes using call-level behavior

While the efficiency of call admission control (CAC) schemes can be improved by taking advantage of call-level behavior, it is also important to make sure that the reliability of the CAC schemes is maintained. This paper studies the reliability aspect of CAC schemes for the reference model that consists of the M/M/c loss system at the call level, and the bufferless link with single-class exponential on-off fluid traffic at the burst level. As a measure of reliability, the probability that an admitted call violates a loss-ratio target is used, and its analytic expression is derived for the reference model by using performability analysis and the nearly completely decomposability approximation. It is shown that the CAC schemes previously proposed to take advantage of call-level behavior are not acceptably reliable. In addition, it is shown that, for most cases in practice, if the reliability of a CAC scheme taking advantage of call-level behavior is to be maintained at a reasonable level, the improvement in efficiency relative to the static scheme will be small.     

ATM traffic management considerations for facilitating broadbandaccess

Traffic management in ATM nodes plays a key role in providing the capability to support a wide range of integrated services while utilizing network resources, such as buffer space and bandwidth, in an efficient manner. In many cases, the issues arising in ATM access devices are very similar to those encountered in larger ATM backbone nodes. In this article, major issues in the design of traffic management schemes are discussed. These include switch fabric design, buffering strategies, service scheduling disciplines, usage parameter control, buffer management schemes, call admission control, and feedback flow control