A stochastic production planning model with a dynamic chance constraint

This paper deals with the optimal production planning for a single product over a finite horizon. The holding and production costs are assumed quadratic as in Holt, Modigliani, Muth and Simon (HMMS) [7] model. The cumulative demand is compound Poisson and a chance constraint is included to guarantee that the inventory level is positive with a probability of at least α at each time point. The resulting stochastic optimization problem is transformed into a deterministic optimal control problem with control variable and of the optimal solution is presented. The form of state variable inequality constraints. A discussion the optimal control (production rate) is obtained as follows: if there exists a time t₁ such that t₁?[O, T]where T is the end of the planning period, then (i) produce nothing until t₁ and (ii) produce at a rate equal to the expected demand plus a ‘correction factor’ between t₁ and T. If t₁ is found to be greater than T, then the optimal decision is to produce nothing and always meet the demand from the inventory.     

Dynamic setup reduction in production lot sizing with nonconstant deterministic demand

We examine three production policies under nonconstant, deterministic demand and dynamic setup cost reduction, where a decision to invest in setup reduction is made at the beginning of each period of a planning horizon. The three production policies are the reorder point, order quantity (s, Q) policy; the fixed production cycle, variable order quantity (t, Q_i) policy; and the variable production cycle, variable order quantity (t_i, Q_i). We study the behavior of the total relevant cost and develop a lot sizing and an investment solution procedure. Numerical examples are provided and dynamic setup cost reduction is compared with static setup cost reduction, where the decision to invest in setup reduction is made only at the initial setup.     

On the order of convergence of a semigroup to the identity operator

We describe classes of vectors f from a Hilbert space H for which the quantity ‖T(t)f?f‖, where T(t)=e ^?tA , t≥0, and A is a self-adjoint nonnegative operator in H, has a certain order of convergence to zero as t→+0.     

A branch-and-bound algorithm to solve the linear ordering problem for weighted tournaments

The linear ordering problem consists in finding a linear order at minimum remoteness from a weighted tournament T, the remoteness being the sum of the weights of the arcs that we must reverse in T to transform it into a linear order. This problem, also known as the search of a median order, or of a maximum acyclic subdigraph, or of a maximum consistent set, or of a minimum feedback arc set, is NP-hard; when all the weights of T are equal to 1, the linear ordering problem is the same as Slater's problem. In this paper, we describe the principles and the results of an exact method designed to solve the linear ordering problem for any weighted tournament. This method, of which the corresponding software is freely available at the URL address http://www.enst.fr/~charon/tournament/median.html, is based upon a branch-and-bound search with a Lagrangean relaxation as the evaluation function and a noising method for computing the initial bound. Other components are designed to reduce the BB-search-tree.     

Total domination subdivision numbers of trees

A set S of vertices in a graph G is a total dominating set of G if every vertex is adjacent to a vertex in S. The total domination number γ_t(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sd_γt(G) of a graph G is the minimum number of edges that must be subdivided (where each edge in G can be subdivided at most once) in order to increase the total domination number. Haynes et al. (J. Combin. Math. Combin. Comput. 44 (2003) 115) showed that for any tree T of order at least 3, 1?sd_γt(T)?3. In this paper, we give a constructive characterization of trees whose total domination subdivision number is 3.     

An O(T) algorithm for the capacitated lot sizing problem with minimum order quantities

This paper explores a single-item capacitated lot sizing problem with minimum order quantity, which plays the role of minor set-up cost. We work out the necessary and sufficient solvability conditions and apply the general dynamic programming technique to develop an O(T³) exact algorithm that is based on the concept of minimal sub-problems. An investigation of the properties of the optimal solution structure allows us to construct explicit solutions to the obtained sub-problems and prove their optimality. In this way, we reduce the complexity of the algorithm considerably and confirm its efficiency in an extensive computational study.     

Global classical large solutions to 1D compressible Navier-Stokes equations with density-dependent viscosity and vacuum

In this paper, we investigate an initial boundary value problem for 1D compressible isentropic Navier-Stokes equations with large initial data, density-dependent viscosity, external force, and vacuum. Making full use of the local estimates of the solutions in Cho and Kim (2006) [3] and the one-dimensional properties of the equations and the Sobolev inequalities, we get a unique global classical solution (ρ,u) where ρ∈C¹([0,T];H¹([0,1])) and u∈H¹([0,T];H²([0,1])) for any T>0. As it is pointed out in Xin (1998) [31] that the smooth solution (ρ,u)∈C¹([0,T];H³(R¹)) (T is large enough) of the Cauchy problem must blow up in finite time when the initial density is of nontrivial compact support. It seems that the regularities of the solutions we obtained can be improved, which motivates us to obtain some new estimates with the help of a new test function ρ²utt, such as Lemmas 3.2-3.6. This leads to further regularities of (ρ,u) where ρ∈C¹([0,T];H³([0,1])), u∈H¹([0,T];H³([0,1])). It is still open whether the regularity of u could be improved to C¹([0,T];H³([0,1])) with the appearance of vacuum, since it is not obvious that the solutions in C¹([0,T];H³([0,1])) to the initial boundary value problem must blow up in finite time.     

Analysis of optimal opportunistic replenishment policies for inventory systems by using a (s,S) model with a maximum issue quantity restriction

The analysis of optimal inventory replenishment policies for items having lumpy demand patterns is difficult, and has not been studied extensively although these items constitute an appreciable portion of inventory populations in parts and supplies types of stockholdings. This paper studies the control of an inventory item when the demand is lumpy. A continuous review (s,S) policy with a maximum issue quantity restriction and with the possibility of opportunistic replenishment is proposed to avoid the stock of these items being depleted unduly when all the customer orders are satisfied from the available inventory and to reduce ordering cost by coordinating inventory replenishments. The nature of the customer demands is approximated by a compound Poisson distribution. When a customer order arrives, if the order size is greater than the maximum issue quantity w, the order is satisfied by placing a special replenishment order rather than from the available stock directly. In addition, if the current inventory position is equal to or below a critical level A when such an order arrives, an opportunistic replenishment order which combines the special replenishment order and the regular replenishment order will be placed, in order to satisfy the customer's demand and to bring the inventory position to S. In this paper, the properties of the cost function of such an inventory system with respect to the control parameters s, S and A are analysed in detail. An algorithm is developed to determine the global optimal values of the control parameters. Indeed, the incorporation of the maximum issue quantity and opportunistic replenishment into the (s,S) policy reduces the total operating cost of the inventory system.     

Supremum principles for the higher-order derivatives of solutions to the Dirichlet problem for parabolic equations without compatibility conditions between the data

The Dirichlet problem is considered for the heat equation ut=auxx, a>0 a constant, for (x,t)∈[0,1]×[0,T], without assuming any compatibility condition between initial and boundary data at the corner points (0,0) and (1,0). Under some smoothness restrictions on the data (stricter than those required by the classical maximum principle), weak and strong supremum and infimum principles are established for the higher-order derivatives, ut and uxx, of the bounded classical solutions. When compatibility conditions of zero order are satisfied (i.e., initial and boundary data coincide at the corner points), these principles allow to estimate the higher-order derivatives of classical solutions uniformly from below and above on the entire domain, except that at the two corner points. When compatibility conditions of the second order are satisfied (i.e., classical solutions belong to on the closed domain), the results of the paper are a direct consequence of the classical maximum and minimum principles applied to the higher-order derivatives. The classical principles for the solutions to the Dirichlet problem with compatibility conditions are generalized to the case of the same problem without any compatibility condition. The Dirichlet problem without compatibility conditions is then considered for general linear one-dimensional parabolic equations. The previous results as well as some new properties of the corresponding Green functions derived here allow to establish uniformL¹-estimates for the higher-order derivatives of the bounded classical solutions to the general problem.     

Periodic solutions for a nonautonomous ordinary differential equation

We consider the nonautonomous differential equation of second order x^″+a(t)x−b(t)x²+c(t)x³=0, where a(t),b(t),c(t) are T-periodic functions. This is a biomathematical model of an aneurysm in the circle of Willis. We prove the existence of at least two positive T-periodic solutions for this equation, using coincidence degree theories.     

Singular Volterra integral equations

Existence results are presented for the singular Volterra integral equation y(t) = h(t) + ∫₀^t k(t, s) f(s, y(s)) ds, for t ∈ [0,T]. Here f may be singular at y = 0. As a consequence new results are presented for the n^th order singular initial value problem.     

Optimal policies for inventory models with some specified markets and finite time horizon

The paper presents the deterministic finite time horizon inventory lot size model, without backlogs and with no lead time, for a single commodity, with some specified markets. The specified markets are represented by the family b(t)=kt^r of demand functions where k>0, r>?2 are known parameters and t stands for time, 0<t₀?t?T. The strict positivity of t₀. compared to the restrictive condition t₀=0 which has been already solved, is crucial and implies entirely different analytical techniques. An important special case is the affine function (r = 1) partly treated already by Donaldson [3]. The problem is to find the optimal schedule of replenishments, i.e., the number and timings of orders.The problem is completely resolved (compared to a recent heuristic by Silver [8]) and the solution is given in a closed form and is proven to be unique. Numerical examples are provided.     

A branch-and-cut algorithm for solving the Non-Preemptive Capacitated Swapping Problem

This paper models and solves a capacitated version of the Non-Preemptive Swapping Problem. This problem is defined on a complete digraph G=(V,A), at every vertex of which there may be one unit of supply of an item, one unit of demand, or both. The objective is to determine a minimum cost capacitated vehicle route for transporting the items in such a way that all demands are satisfied. The vehicle can carry more than one item at a time. Three mathematical programming formulations of the problem are provided. Several classes of valid inequalities are derived and incorporated within a branch-and-cut algorithm, and extensive computational experiments are performed on instances adapted from TSPLIB.     

On the complexity of Slater’s problems

Given a tournament T, Slater’s problem consists in determining a linear order (i.e. a complete directed graph without directed cycles) at minimum distance from T, the distance between T and a linear order O being the number of directed edges with different orientations in T and in O. This paper studies the complexity of this problem and of several variants of it: computing a Slater order, computing a Slater winner, checking that a given vertex is a Slater winner and so on.     

Managing stochastic inventory systems with free shipping option

In many industries, customers are offered free shipping whenever an order placed exceeds a minimum quantity specified by suppliers. This allows the suppliers to achieve economies of scale in terms of production and distribution by encouraging customers to place large orders. In this paper, we consider the optimal policy of a retailer who operates a single-product inventory system under periodic review. The ordering cost of the retailer is a linear function of the ordering quantity, and the shipping cost is a fixed constant K whenever the order size is less than a given quantity – the free shipping quantity (FSQ), and it is zero whenever the order size is at least as much as the FSQ. Demands in different time periods are i.i.d. random variables. We provide the optimal inventory control policy and characterize its structural properties for the single-period model. For multi-period inventory systems, we propose and analyze a heuristic policy that has a simple structure, the (s, t, S) policy. Optimal parameters of the proposed heuristic policy are then computed. Through an extensive numerical study, we demonstrate that the heuristic policy is sufficiently accurate and close to optimal.     

Most balanced minimum cuts

We consider the problem of finding most balanced cuts among minimum st-edge cuts and minimum st-vertex cuts, for given vertices s and t, according to different balance criteria. For edge cuts we seek to maximize . For vertex cuts C of G we consider the objectives of (i) maximizing min{|S|,|T|}, where {S,T} is a partition of V(G)?C with s∈S, t∈T and [S,T]=0?, (ii) minimizing the order of the largest component of G−C, and (iii) maximizing the order of the smallest component of G−C.All of these problems are NP-hard. We give a PTAS for the edge cut variant and for (i). These results also hold for directed graphs. We give a 2-approximation for (ii), and show that no non-trivial approximation exists for (iii) unless P=NP.To prove these results we show that we can partition the vertices of G, and define a partial order on the subsets of this partition, such that ideals of the partial order correspond bijectively to minimum st-cuts of G. This shows that the problems are closely related to Uniform Partially Ordered Knapsack (UPOK), a variant of POK where element utilities are equal to element weights. Our algorithm is also a PTAS for special types of UPOK instances.     

On Semi-Finite Hexagons of Order (2, <Emphasis Type="Italic">t</Emphasis>) Containing a Subhexagon

The research in this paper was motivated by one of the most important open problems in the theory of generalized polygons, namely the existence problem for semi–finite thick generalized polygons. We show here that no semi–finite generalized hexagon of order (2, t) can have a subhexagon H of order 2. Such a subhexagon is necessarily isomorphic to the split Cayley generalized hexagon H(2) or its point–line dual H ^D (2). In fact, the employed techniques allow us to prove a stronger result. We show that every near hexagon \({\mathcal{S}}\) of order (2, t) which contains a generalized hexagon H of order 2 as an isometrically embedded subgeometry must be finite. Moreover, if \({H \cong H^{D}}\)(2) then \({\mathcal{S}}\) must also be a generalized hexagon, and consequently isomorphic to either H ^D (2) or the dual twisted triality hexagon T(2, 8).     

Modified quasilinearization algorithm for optimal control problems with nondifferential constraints

This paper considers the numerical solution of optimal control problems involving a functionalI subject to differential constraints, nondifferential constraints, and terminal constraints. The problem is to find the statex(t), the controlu(t), and the parameter π so that the functional is minimized, while the constraints are satisfied to a predetermined accuracy. A modified quasilinearization algorithm is developed. Its main property is the descent property in the performance indexR, the cumulative error in the constraints and the optimality conditions. Modified quasilinearization differs from ordinary quasilinearization because of the inclusion of the scaling factor (or stepsize) α in the system of variations. The stepsize is determined by a one-dimensional search on the performance indexR. Since the first variation δR is negative, the decrease inR is guaranteed if α is sufficiently small. Convergence to the solution is achieved whenR becomes smaller than some preselected value. In order to start the algorithm, some nominal functionsx(t),u(t), π and nominal multipliers λ(t), ρ(t), μ must be chosen. In a real problem, the selection of the nominal functions can be made on the basis of physical considerations. Concerning the nominal multipliers, no useful guidelines have been available thus far. In this paper, an auxiliary minimization algorithm for selecting the multipliers optimally is presented: the performance indexR is minimized with respect to λ(t), ρ(t), μ. Since the functionalR is quadratically dependent on the multipliers, the resulting variational problem is governed by optimality conditions which are linear and, therefore, can be solved without difficulty. To facilitate the numerical solution on digital computers, the actual time θ is replaced by the normalized timet, defined in such a way that the extremal arc has a normalized time length Δt=1. In this way, variable-time terminal conditions are transformed into fixed-time terminal conditions. The actual time τ at which the terminal boundary is reached is regarded to be a component of the parameter π being optimized. The present general formulation differs from that of Ref. 3 because of the inclusion of the nondifferential constraints to be satisfied everywhere over the interval 0?t?1. Its importance lies in that (i) many optimization problems arise directly in the form considered here, (ii) there are problems involving state equality constraints which can be reduced to the present scheme through suitable transformations, and (iii) there are some problems involving inequality constraints which can be reduced to the present scheme through the introduction of auxiliary variables. Numerical examples are presented for the free-final-time case. These examples demonstrate the feasibility as well as the rapidity of convergence of the technique developed in this paper.     

Time-varying minimum cost flow problems

In this paper, we study a minimum cost flow problem on a time-varying network. Let N(V,A,l,b,c_r,c_w) be a network with an arc set A and a vertex set V. Each a∈A is associated with three integer parameters: a positive transit time b(a,t), an arbitrary transit cost c_r(a,t), and a positive capacity limit l(a,t). Each x∈V is associated with two integer parameters: a waiting cost c_w(x,t) and a vertex capacity l(x,t). All these parameters are functions of the discrete time t=0,1,2,… The objective is to find an optimal schedule to send a flow from the origin (the source vertex) to its destination (the sink vertex) with the minimum cost, subject to the constraint that the flow must arrive at the destination before a deadline T. Three versions of the problem are examined, which are classified depending on whether waiting at the intermediate vertices of the network is strictly prohibited, arbitrarily allowed, or bounded. Three algorithms with pseudopolynomial time complexity are proposed, which can find optimal solutions to the three versions of the problem, respectively.