Economic lot sizing problem with inventory bounds

This paper studies a economic lot sizing (ELS) problem with both upper and lower inventory bounds. Bounded ELS models address inventory control problems with time-varying inventory capacity and safety stock constraints. An O(n²) algorithm is found by using net cumulative demand (NCD) to measure the amount of replenishment requested to fulfill the cumulative demand till the end of the planning horizon. An O(n) algorithm is found for the special case, the bounded ELS problem with non-increasing marginal production cost.     

A parallel algorithm for generating multiple ordering spanning trees in undirected weighted graphs

1.IntroductionLetG=(V,E,W)beaconnected,weightedandundirectedgraph,VeEE,w(e)(相似文献   

Directeds-t numberings,Rubber bands,and testing digraphk-vertex connectivity

LetG=(V, E) be a directed graph andn denote |V|. We show thatG isk-vertex connected iff for every subsetX ofV with |X| =k, there is an embedding ofG in the (k–1)-dimensional spaceR ^k–1,fVR ^k–1, such that no hyperplane containsk points of {f(v)|vV}, and for eachvV–X, f(v) is in the convex hull of {f(w)| (v, w)E}. This result generalizes to directed graphs the notion of convex embeddings of undirected graphs introduced by Linial, Lovász and Wigderson in Rubber bands, convex embeddings and graph connectivity,Combinatorica 8 (1988), 91–102.Using this characterization, a directed graph can be tested fork-vertex connectivity by a Monte Carlo algorithm in timeO((M(n)+nM(k)) · (logn)) with error probability<1/n, and by a Las Vegas algorithm in expected timeO((M(n)+nM(k)) ·k), whereM(n) denotes the number of arithmetic steps for multiplying twon×n matrices (M(n)=O(n ^2.376)). Our Monte Carlo algorithm improves on the best previous deterministic and randomized time complexities fork>n ^0.19; e.g., for , the factor of improvement is >n ^0.62. Both algorithms have processor efficient parallel versions that run inO((logn)²) time on the EREW PRAM model of computation, using a number of processors equal to logn times the respective sequential time complexities. Our Monte Carlo parallel algorithm improves on the number of processors used by the best previous (Monte Carlo) parallel algorithm by a factor of at leastn ²/(logn)³ while having the same running time.Generalizing the notion ofs-t numberings, we give a combinatorial construction of a directeds-t numbering for any 2-vertex connected directed graph.     

New scaling algorithms for the assignment and minimum mean cycle problems

In this paper we suggest new scaling algorithms for the assignment and minimum mean cycle problems. Our assignment algorithm is based on applying scaling to a hybrid version of the recentauction algorithm of Bertsekas and the successive shortest path algorithm. The algorithm proceeds by relaxing the optimality conditions, and the amount of relaxation is successively reduced to zero. On a network with 2n nodes,m arcs, and integer arc costs bounded byC, the algorithm runs in O( m log(nC)) time and uses very simple data structures. This time bound is comparable to the time taken by Gabow and Tarjan's scaling algorithm, and is better than all other time bounds under thesimilarity assumption, i.e.,C = O(n ^k ) for somek. We next consider the minimum mean cycle problem. Themean cost of a cycle is defined as the cost of the cycle divided by the number of arcs it contains. Theminimum mean cycle problem is to identify a cycle whose mean cost is minimum. We show that by using ideas of the assignment algorithm in an approximate binary search procedure, the minimum mean cycle problem can also be solved in O( m lognC) time. Under the similarity assumption, this is the best available time bound to solve the minimum mean cycle problem.     

Comparative studies on dynamic programming and integer programming approaches for concave cost production/inventory control problems

This paper is concerned with classical concave cost multi-echelon production/inventory control problems studied by W. Zangwill and others. It is well known that the problem with m production steps and n time periods can be solved by a dynamic programming algorithm in O(n ⁴ m) steps, which is considered as the fastest algorithm for solving this class of problems. In this paper, we will show that an alternative 0–1 integer programming approach can solve the same problem much faster particularly when n is large and the number of 0–1 integer variables is relatively few. This class of problems include, among others problem with set-up cost function and piecewise linear cost function with fewer linear pieces. The new approach can solve problems with mixed concave/convex cost functions, which cannot be solved by dynamic programming algorithms.     

Single Supplier Scheduling for Multiple Deliveries

The problem of scheduling the production and delivery of a supplier to feed the production of F manufacturers is studied. The orders fulfilled by the supplier are delivered to the manufacturers in batches of the same size. The supplier's production line has to be set up whenever it switches from processing an order of one manufacturer to an order of another manufacturer. The objective is to minimize the total setup cost, subject to maintaining continuous production for all manufacturers. The problem is proved to be NP-hard. It is reduced to a single machine scheduling problem with deadlines and jobs belonging to F part types. An O(NlogF) algorithm, where N is the number of delivery batches, is presented to find a feasible schedule. A dynamic programming algorithm with O(N ^F /F ^F–2) running time is presented to find an optimal schedule. If F=2 and setup costs are unit, an O(N) time algorithm is derived.     

Matching parentheses in parallel

Parallel algorithms for evaluating arithmetic expressions generally assume the computation tree form to be at hand. The computation tree form can be generated within the same resource bounds as the parenthesis matching problem can be solved. We provide a new cost optimal parallel algorithm for the latter problem, which runs in time O(log n) using O(n/log n) processors on an . We also prove that the algorithm is the fastest possible independently of the number of processors available.     

Edge-disjoint cycles in regular directed graphs

We prove that any k-regular directed graph with no parallel edges contains a collection of at least O(k²) edge-disjoint cycles; we conjecture that in fact any such graph contains a collection of at least (^k+1₂) disjoint cycles, and note that this holds for k ≤ 3. © 1996 John Wiley & Sons, Inc.     

A polynomial time algorithm for solving a quality control station configuration problem

We study unreliable serial production lines with known failure probabilities for each operation. Such a production line consists of a series of stations; existing machines and optional quality control stations (QCS). Our aim is to simultaneously decide where and if to install the QCSs along the line and to determine the production rate, so as to maximize the steady state expected net profit per time unit from the system.We use dynamic programming to solve the cost minimization auxiliary problem where the aim is to minimize the time unit production cost for a given production rate. Using the above developed O(N²) dynamic programming algorithm as a subroutine, where N stands for the number of machines in the line, we present an O(N⁴) algorithm to solve the Profit Maximization QCS Configuration Problem.     

Analysis of a two-sided production policy with inventory-level-dependent production rates

In this paper we analyse a stochastic production/inventory problem with compound Poisson demand and state (i.e. inventory level) dependent production rates. Customers arrive according to a Poisson process where the amount demanded by each customer is assumed to have a general distribution. When the inventory W(t) falls below a critical level m, production is started at a rate of r[W(t)], i.e. production rate dynamically changes as a function of the inventory level. Production continues until a level M (œ w m) is reached. Excess demand is assumed to be lost. We identify a dam content process X that is a dual for the inventory level W and develop the stationary distribution for the X process. To achieve this we use tools from renewal and level crossing theories. The two-sided (m, M) policy is optimized using the expected cost obtained from the stationary density of W and a conditional (on w) expected cost function for this process. For a special case, we obtain explicit results for all the relevant expressions. Numerical examples are provided for several test problems. © 1996 John Wiley & Sons, Ltd.     

A Baby Steps/Giant Steps Probabilistic Algorithm for Computing Roadmaps in Smooth Bounded Real Hypersurface

We consider the problem of constructing roadmaps of real algebraic sets. This problem was introduced by Canny to answer connectivity questions and solve motion planning problems. Given s polynomial equations with rational coefficients, of degree D in n variables, Canny’s algorithm has a Monte Carlo cost of sⁿlog(s)D^O(n2)s^{n}\log(s)D^{O(n^{2})} operations in ℚ; a deterministic version runs in time sⁿlog(s)D^O(n4)s^{n}\log(s)D^{O(n^{4})} . A subsequent improvement was due to Basu, Pollack, and Roy, with an algorithm of deterministic cost s^d+1D^O(n2)s^{d+1}D^{O(n^{2})} for the more general problem of computing roadmaps of a semi-algebraic set (d≤n is the dimension of an associated object).     

Visibility with Multiple Reflections

We show that the region lit by a point light source inside a simple n -gon after at most k reflections off the boundary has combinatorial complexity O(n ^2k ) , for any k≥ 1 . A lower bound of Ω ((n/k-Θ(1)) ^2k ) is also established which matches the upper bound for any fixed k . A simple near-optimal algorithm for computing the illuminated region is presented, which runs in O(n ^2k log n) time and O(n ^2k ) space for k>1 , and in O(n ² log ² n) time and O(n ² ) space for k=1 . Received March 14, 1996, and in revised form December 22, 1997, and January 5, 1998.     

A Stochastic Petri Net Approach for Inventory Rationing in Multi-Echelon Supply Chains

Manufacturing supply chains are considered as discrete event dynamical systems (DEDS) where coordination of material and information flows is essential to satisfy customer orders and to improve the bottomline of the constituent organizations. A critical problem that is often faced by distribution centres that hold finished good inventory is that of inventory rationing. Inventory rationing is a useful strategy to tackle the problem of conflicting objectives i.e., minimizing inventory costs (holding and backorder) on the one hand and achieving the desired customer service levels (CSLs) on the other. The focus of this paper is to formulate Generalized Stochastic Petri net models to address the inventory rationing problem in the context of multi-echelon make-to-stock distribution chains, where the goods flow through multiple echelons, typically from product manufacturers all the way up-to the retail outlets. The statistical inventory control (SIC) policies modeled by the GSPN are (R, s, S) and a variant that we propose, (R^∗, s, S). We compare the performance of the model under two rationing settings. The first setting considers a case without cooperation, where the individual local stockpoints maximize their own performance. The second setting considers a case with cooperation, where the local stockpoints cooperate with each other to maximize the overall system performance. We provide a methodology to approximately determine the optimal rational fractions with different weights assigned to expected backorder and holding cost components (b/h). We present some interesting results obtained after rigorous numerical experimentation on the model.     

Inverse median location problems with variable coordinates

Given n points in \mathbbR^d{\mathbb{R}^d} with nonnegative weights, the inverse 1-median problem with variable coordinates consists in changing the coordinates of the given points at minimum cost such that a prespecified point in \mathbbR^d{\mathbb{R}^d} becomes the 1-median. The cost is proportional to the increase or decrease of the corresponding point coordinate. If the distances between points are measured by the rectilinear norm, the inverse 1-median problem is NP{\mathcal{NP}}-hard, but it can be solved in pseudo-polynomial time. Moreover, a fully polynomial time approximation scheme exists in this case. If the point weights are assumed to be equal, the corresponding inverse problem can be reduced to d continuous knapsack problems and is therefore solvable in O(nd) time. In case that the squared Euclidean norm is used, we derive another efficient combinatorial algorithm which solves the problem in O(nd) time. It is also shown that the inverse 1-median problem endowed with the Chebyshev norm in the plane is NP{\mathcal{NP}}-hard. Another pseudo-polynomial algorithm is developed for this case, but it is shown that no fully polynomial time approximation scheme does exist.     

The scheduling of deliveries in a production-distribution system with multiple buyers

In a real production and distribution business environment with one supplier and multiple heterogeneous buyers, the differences in buyers’ ordering cycles have influence on production arrangements. Consequently, the average inventory level (AIL) at the supplier’s end is affected by both the production policy and the ordering policy, typically by the scheduling of deliveries. Consequently, the average inventory holding cost is most deeply affected. In this paper, it is proposed that the scheduling of deliveries be formulated as a decision problem to determine the time point at which deliveries are made to buyers in order to minimize the supplier’s average inventory. A formulation of the average inventory level (AIL) in a production cycle at the supplier’s end using a lot-for-lot policy is developed. Under the lot-for-lot policy, the scheduling of deliveries (SP) is formulated as a nonlinear programming model used to determine the first delivery point for each buyer with an objective to minimize the sum of the product of the individual demand quantity and the first delivery time for each buyer. Thus, the SP model determines not only the sequence of the first deliveries to individual buyers, but also the time when the deliveries are made. An iterative heuristic procedure (IHP) is developed to solve the SP model assuming a given sequence of buyers. Six sequence rules are considered and evaluated via simulation.     

On Fast Computations with the Inverse to Harmonic Potential Operators via Domain Decomposition

In this paper a method for fast computations with the inverse to weakly singular, hypersingular and double layer potential boundary integral operators associated with the Laplacian on Lipschitz domains is proposed and analyzed. It is based on the representation formulae suggested for above-mentioned boundary operations in terms of the Poincare-Steklov interface mappings generated by the special decompositions of the interior and exterior domains. Computations with the discrete counterparts of these formulae can be efficiently performed by iterative substructuring algorithms provided some asymptotically optimal techniques for treatment of interface operators on subdomain boundaries. For both two- and three-dimensional cases the computation cost and memory needs are of the order O(N log^p N) and O(N log² N), respectively, with 1 ≤ p ≤ 3, where N is the number of degrees of freedom on the boundary under consideration (some kinds of polygons and polyhedra). The proposed algorithms are well suited for serial and parallel computations.     

Extremal point queries with lines and line segments and related problems

We address a number of extremal point query problems when P is a set of n points in , d3 a constant, including the computation of the farthest point from a query line and the computation of the farthest point from each of the lines spanned by the points in P. In , we give a data structure of size O(n¹⁺), that can be constructed in O(n¹⁺) time and can report the farthest point of P from a query line segment in O(n^2/3+) time, where >0 is an arbitrarily small constant. Applications of our results also include: (1) Sub-cubic time algorithms for fitting a polygonal chain through an indexed set of points in , d3 a constant, and (2) A sub-quadratic time and space algorithm that, given P and an anchor point q, computes the minimum (maximum) area triangle defined by q with P{q}.     

Scheduling unit time jobs with integer release dates to minimize the weighted number of tardy jobs

Consider a set of n unit time jobs, each one having a release date, a due date, both nonnegative integers, and a weight, a positive real number. Given a set of m parallel machines, we describe an algorithm for finding schedules with minimum weighted number of tardy jobs. The complexity of the proposed algorithm is O(n²\frac(1+logm)m)O(n^{2}\frac{(1+\log m)}{m}) . The best previous algorithm for this problem has complexity O(mn ³) and employs network flow techniques. Our method is based on a characterization for schedules of this type and employs graph theoretic tools.     

Controllability of the wave equation with moving point control

This paper deals with approximate and exact controllability of the wave equation in finite time with interior point control acting along a curve specified in advance in the system's spatial domain. The structure of the control input is dual to the structure of the observations which describe the measurements of velocity and gradient of the solution of the dual system, obtained from the moving point sensor. A relevant formalization of such a control problem is discussed, based on transposition. For any given timeinterval [0,T] the existence of the curves providing approximate controllability inH _D ^–[n/2]–1 ()×H _D ^–[n/2]–1 () (wheren stands for the space dimension) is established with controls fromL ²(0,T; R ⁿ +1). The same curves ensure exact controllability inL ²() × H^–1() if controls are allowed to be selected in [L (0,T; R ⁿ+1)]. Required curves can be constructed to be continuous on [0,T).This work was supported in part by NSF Grant ECS 89-13773 and NASA Grant NAG-1-1081.