Production strategies for a stochastic lot-sizing problem with constant capacity

This paper presents a single item capacitated stochastic lot-sizing problem motibated by a Dutch company operating in a Make-To-Order environment. Due to a highly fluctuating and unpredictable demand, it is not possible to keep any finished goods inventory. In response to a customer's order, a fixed delivery date is quoted by the company. The objective is to determine in each period of the planning horizon the optimal size of production lots so that delivery dates are met as closely as possible at the expense of minimal average costs. These include set-up costs, holding costs for orders that are finished before their promised delivery date and penalty costs for orders that are not satisfied on time and are therefore backordered. Given that the optimal production policy is likely to be too complex in this situation, attention is focused on the development of heuristic procedures. In this paper two heuristics are proposed. The first one is an extension of a simple production strategy derived by Dellaert [5] for the uncapacitated version of the problem. The second heuristic is based on the well-known Silver-Meal algorithm for the case of deterministic time-varying demand. Experimental results suggest that the first heuristic gives low average costs especially when the demand variability is low and there are large differences in the cost parameters. The Silver-Meal approach is usually outperformed by the first heuristic in situations where the available production capacity is tight and the demand variability is low.     

Interval vortex methods

By means of the integral version of vortex equation, the technique of Green's function, and the vorticity‐to‐velocity map, a new kind of interval methods for solving the initial‐periodic boundary value problem of two‐dimensional incompressible Navier–Stokes equation is introduced, which consists of both an approximate scheme and a set of pointwise intervals covering the exact solution. The convergence theorem corresponding to the scheme is proved, and the order of error width for the two‐sided bounds is also considered. Finally, a simple numerical example illustrates our corroboration. © 2014 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 30: 1368–1396, 2014     

A simplified loop-free algorithm for generating permutations

A simple loop-free algorithm for generation of all permutations of a set of elements is presented and its validity is proved. It is a simplification of Ehrlich's loop-free version of Johnson and Trotter's algorithm. Each permutation is generated by exchanging two adjacent elements of the preceding permutation. A very simple data structure obviates the need for looping during the generation of each successive permutation.     

Pareto memetic algorithm with path relinking for bi-objective traveling salesperson problem

The paper presents an effective version of the Pareto memetic algorithm with path relinking and efficient local search for multiple objective traveling salesperson problem. In multiple objective Traveling salesperson problem (TSP), multiple costs are associated with each arc (link). The multiple costs may for example correspond to the financial cost of travel along a link, time of travel, or risk in the case of hazardous materials. The algorithm searches for new good solutions along paths in the decision space linking two other good solutions selected for recombination. Instead of a simple local search it uses short runs of tabu search based on the steepest version of the Lin–Kernighan algorithm. The efficiency of local search is further improved by the techniques of candidate moves and locked arcs. In the final step of the algorithm the neighborhood of each potentially Pareto-optimal solution is searched for new solutions that could be added to this set. The algorithm is compared experimentally to the state-of-the-art algorithms for multiple objective TSP.     

An exact algorithm for the fuzzy p-median problem

In this paper we propose a fuzzy version of the classical p-median problem. We consider a fuzzy set of constraints so that the decision-maker will be able to take into account solutions which provide significantly lower costs by leaving a part of the demand uncovered. We propose an algorithm for solving the problem which is based on Hakimi's works and we compare the crisp and the fuzzy approach by means of an example.     

A Novel Time‐Domain BIEM for Wave Propagation Analysis in Anisotropic Solids With Cracks

Analysis of elastic wave propagation in anisotropic solids with cracks is of particular interest to quantitative non‐destructive testing and fracture mechanics. For this purpose, a novel time‐domain boundary integral equation method (BIEM) is presented in this paper. A finite crack in an unbounded elastic solid of general anisotropy subjected to transient elastic wave loading is considered. Two‐dimensional plane strain or plane stress condition is assumed. The initial‐boundary value problem is formulated as a set of hypersingular time‐domain traction boundary integral equations (BIEs) with the crack‐opening‐displacements (CODs) as unknown quantities. A time‐stepping scheme is developed for solving the hypersingular time‐domain BIEs. The scheme uses the convolution quadrature formula of Lubich [1] for temporal convolution and a Galerkin method for spatial discretization of the BIEs. An important feature of the present time‐domain BIEM is that it uses the Laplace‐domain instead of the more complicated time‐domain Green's functions. Fourier integral representations of Laplace‐domain Green's functions are applied. No special technique is needed in the present time‐domain BIEM for evaluating hypersingular integrals.     

A Neville-like method via continued fractions

As we know, the classical Neville's algorithm is an effective method used to solve the interpolation problem by polynomials. In this paper, we adopt the idea of the Neville's algorithm to construct a kind of blending rational interpolants via continued fractions. For a given set of support points, there are many ways to build up the interpolation schemes, by which we mean that there are many choices to make to determine the initial interpolants on subsets of support points and then update them step by step to form a solution to the full interpolation problem. Numerical examples are given to show the advantage of our method and a multivariate analogy is also discussed.     

Multilevel Scheduling of Multistage Production with Limited In-Process Inventory

A multistage, multiproduct production scheduling with limited in-process buffers between the successive stages is considered. Each stage is made up of identical parallel machines. The problem objective is to determine an assignment of products to machines over a scheduling horizon, which minimizes the completion time of the production order, with the in-process inventory holding costs as low as possible. The problem is modelled by multilevel integer programmes, each of which is concerned with scheduling a different stage of production. The interactions among the stages are modelled by additional constraints, which take into account the semi-finished product's availability and the limited storage capacity of the intermediate buffers. An hierarchical scheduling algorithm is presented, and an illustrative example for a three-stage production is included.     

Focus quantities with applications to some finite‐dimensional systems

In studying small limit cycles of finite‐dimensional systems, one of the central problem is the computation of focus quantities. In practice, the computation is a challenging problem even for some simple low‐dimensional systems. This paper is devoted to the computation of focus quantities of all orders and to the study of Hopf bifurcations in some chaotic systems. A recursive formula for computing focus quantities is presented for a K + 2‐dimensional system. The formula is a generalization of previous results on low‐dimensional systems with K = 0 and K = 1. For a four‐dimensional hyper‐chaotic system, according to the sign of the first focus quantity, we prove that the simple Hopf bifurcation of the system is supercritical. For a five‐dimensional chaotic system with four equilibria of Hopf type, according to the signs of the first focus quantities, we prove that the simple Hopf bifurcations of the system are subcritical.     

The unit commitment model with concave emissions costs: a hybrid Benders’ Decomposition with nonconvex master problems

We present a unit commitment model which determines generator schedules, associated production and storage quantities, and spinning reserve requirements. Our model minimizes fixed costs, fuel costs, shortage costs, and emissions costs. A constraint set balances the load, imposes requirements on the way in which generators and storage devices operate, and tracks reserve requirements. We capture cost functions with piecewise-linear and (concave) nonlinear constructs. We strengthen the formulation via cut addition. We then describe an underestimation approach to obtain an initial feasible solution to our model. Finally, we constitute a Benders’ master problem from the scheduling variables and a subset of those variables associated with the nonlinear constructs; the subproblem contains the storage and reserve requirement quantities, and power from generators with convex (linear) emissions curves. We demonstrate that our strengthening techniques and Benders’ Decomposition approach solve our mixed integer, nonlinear version of the unit commitment model more quickly than standard global optimization algorithms. We present numerical results based on a subset of the Colorado power system that provide insights regarding storage, renewable generators, and emissions.     

An extension of Sharpe's single-index model: portfolio selection with expert betas

This paper presents an approach to the portfolio selection problem based on Sharpe's single-index model and on Fuzzy Sets Theory. In this sense, expert estimations about future Betas of each financial asset have been included in the portfolio selection model denoted as ‘Expert Betas’ and modelled as trapezoidal fuzzy numbers. Value, ambiguity and fuzziness are three basic concepts involved in the model which provide enough information about fuzzy numbers representing ‘Expert Betas’ and that are simple to handle. In order to select an optimal portfolio, a Goal Programming model has been proposed including imprecise investor's aspirations concerning asset's proportions of both, high-and low-risk assets. Semantics of these goals are based on the fuzzy membership of a goal satisfaction set. To illustrate the proposed model a real portfolio selection problem is presented.     

The elastic generalized assignment problem

The generalized assignment problem (GAP) has been studied by numerous researchers over the past 30 years or so. Simply stated, one must find a minimum-cost assignment of tasks to agents such that each task is assigned to exactly one agent and such that each agent's resource capacity is honoured. The problem is known to be NP-hard. In this paper, we study the elastic generalized assignment problem (EGAP). The elastic version of GAP allows agent resource capacity to be violated at additional cost. Another version allows undertime costs to be assessed as well if an agent's resource capacity is not used to its full extent. The EGAP is also NP-hard. We describe a special-purpose branch-and-bound algorithm that utilizes linear programming cuts, feasible solution generators, Lagrangean relaxation and subgradient optimization. We present computational results on a large collection of randomly generated ‘hard’ problems with up to 4000 binary variables.     

Discrete stochastic location models

In this paper, we study how the two classical location models, the simple plant location problem and thep-median problem, are transformed in a two-stage stochastic program with recourse when uncertainty on demands, variable production and transportation costs, and selling prices is introduced. We also discuss the relation between the stochastic version of the SPLP and the stochastic version of thep-median.     

The two-group heuristic to solve the multi-product,economic lot sizing and scheduling problem in flow shops

This paper presents a new and efficient heuristic to solve the multi-product, economic lot sizing and scheduling problem in flow shops. The problem addressed is that of making sequencing, lot sizing and scheduling decisions for a number of products so as to minimize the sum of setup costs, work-in-process inventory holding costs and final-products inventory holding costs while a given demand is fulfilled without backlogging. The proposed heuristic, called the two-group method (TG), assumes that the cycle time of each product is an integer multiple of a basic period and restricts these multiples to take either the value 1 or K where K is a positive integer. The products to be produced once each K basic period are then partitioned into K sub-groups and each sub-group is assigned to one and only one of the K basic periods of the global cycle. This method first determines a value for K and a feasible partition. Then, a production sequence is determined for each sub-group of products and a non-linear program is solved to determine lot sizes and a feasible schedule. We also show how to adapt our method to the case of batch streaming (transportation of sub-batches from one machine to the next). To evaluate its performance, the TG method was compared to both the common cycle method and a reinforced version of El-Najdawi’s job-splitting heuristic. Numerical results show that the TG method outperforms both of these methods.     

On the random 2‐stage minimum spanning tree

It is known [A. M. Frieze, Discrete Appl Math 10 (1985), 47–56] that if the edge costs of the complete graph K_n are independent random variables, uniformly distributed between 0 and 1, then the expected cost of the minimum spanning tree is asymptotically equal to . Here we consider the following stochastic two‐stage version of this optimization problem. There are two sets of edge costs c_M: E → ? and c_T: E → ?, called Monday's prices and Tuesday's prices, respectively. For each edge e, both costs c_M(e) and c_T(e) are independent random variables, uniformly distributed in [0, 1]. The Monday costs are revealed first. The algorithm has to decide on Monday for each edge e whether to buy it at Monday's price c_M(e), or to wait until its Tuesday price c_T(e) appears. The set of edges X_M bought on Monday is then completed by the set of edges X_T bought on Tuesday to form a spanning tree. If both Monday's and Tuesday's prices were revealed simultaneously, then the optimal solution would have expected cost ζ(3)/2 + o(1). We show that, in the case of two‐stage optimization, the expected value of the optimal cost exceeds ζ(3)/2 by an absolute constant ε > 0. We also consider a threshold heuristic, where the algorithm buys on Monday only edges of cost less than α and completes them on Tuesday in an optimal way, and show that the optimal choice for α is α = 1/n with the expected cost ζ(3) ? 1/2 + o(1). The threshold heuristic is shown to be sub‐optimal. Finally we discuss the directed version of the problem, where the task is to construct a spanning out‐arborescence rooted at a fixed vertex r, and show, somewhat surprisingly, that in this case a simple variant of the threshold heuristic gives the asymptotically optimal value 1 ? 1/e + o(1). © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

The Adaptive Projected Subgradient Method over the Fixed Point Set of Strongly Attracting Nonexpansive Mappings

This paper presents an algorithmic solution, the adaptive projected subgradient method, to the problem of asymptotically minimizing a certain sequence of non-negative continuous convex functions over the fixed point set of a strongly attracting nonexpansive mapping in a real Hilbert space. The method generalizes Polyak's subgradient algorithm for the convexly constrained minimization of a fixed nonsmooth function. By generating a strongly convergent and asymptotically optimal point sequence, the proposed method not only offers unifying principles for many projection-based adaptive filtering algorithms but also enhances the adaptive filtering methods with the set theoretic estimation's armory by allowing a variety of a priori information on the estimandum in the form, for example, of multiple intersecting closed convex sets.     

An impulse control problem of a production model with interruptions to follow stochastic demand

The paper deals with the stochastic optimal intervention problem which arises in a production & storage system involving identical items. The requests for items arrive at random and the production of an item can be interrupted during production to meet the corresponding demand. The operational costs considered are due to the stock/backlog, running costs and set up costs associated to interruptions and re-initializations. The process presents distinct behaviour on each of two disjoint identical subsets of the state space, and the state process can only be transferred from one subset to the other by interventions associated to interruptions/re-initializations. A characterization is given in terms of piecewise deterministic Markov process, which explores the aforementioned structure, and a method of solution with assured convergence, that does not require any special initialization, is provided.Additionally, we demonstrate that under conditions on the data, the optimal policy is to produce the item completely in a certain region of the state space of low stock level.     

Multiproduct,Three-Stage Production Inventory Systems

This paper deals with production systems with three stages in series and producing multiple products. A method of determining a near optimal production plan taking into consideration the demands, the production rates, the set-up costs and all the relevant inventory carrying costs is discussed. This heuristic approach gives the method of determining the production batch quantities and the sequence in which the different products are to be taken up in a production cycle. A numerical example is also included. The results obtained for 21 test problems by the use of the heuristic are compared with the exact optimum values, and the power of the heuristic is demonstrated.     

Preference disaggregation for measuring and analysing customer satisfaction: The MUSA method

The MUlticriteria Satisfaction Analysis (MUSA) method for measuring and analysing customer satisfaction is presented in this paper. The MUSA method is a preference disaggregation model following the principles of ordinal regression analysis (inference procedure). The integrated methodology evaluates the satisfaction level of a set of individuals (customers, employees, etc.) based on their values and expressed preferences. Using satisfaction survey's data, the MUSA method aggregates the different preferences in unique satisfaction functions. This aggregation–disaggregation process is achieved with the minimum possible errors. The main advantage of the MUSA method is that it fully considers the qualitative form of customers' judgements and preferences. The development of a set of quantitative indices and perceptual maps makes possible the provision of an effective support for the satisfaction evaluation problem. This paper also presents the reliability analysis of the provided results, along with a simple numerical example that demonstrates the implementation process of the MUSA method. Finally, several extensions and future research in the context of the presented method are discussed.