Simultaneous siting and sizing of distribution centers on a plane

The benefits of simultaneous consideration of siting and sizing of distribution centers have been well acknowledged in supply chain design. Most formulations assume that the potential DC sites are known and the decision on location is to select sites from the finite potential DC sites. However, the quality of this discrete version problem depends on the selection of potential DC sites. In this paper we present a planar version of the problem, which assumes that there is no a priori knowledge of DC sites and DCs can be located anywhere in the plane. The goal of the problem is to simultaneously find locations and sizing of DC sites. The solution of the planar problem provides a lower bound for the discrete problem. The objective of the problem is to minimize the total of inbound and outbound transportation costs and distribution center construction costs—which include its fixed charge cost and concave sizing cost. The problem is initially formulated as a nonlinear programming model. We then reformulate it as a set covering problem after establishing certain key properties. A greedy drop heuristic and a column generation heuristic are developed to solve the problem. Computational experiments are provided.     

Efficient preprocessing for VLSI optimization problems

Advances in technology for the manufacturing of integrated circuits have resulted in extremely large, and time consuming, problems on how to lay out components for optimal circuit performance. These problems can be written as mixed integer programs which are easily relaxed to linear programs with a very high number of variables and constraints. The relaxed programs can often be solved by applying state-of-the-art linear programming software, however these solutions come at the expense of long solution time. In this paper we show that, by considering the structure inherent in VLSI problems, one can specialize classical preprocessing algorithms to take into account the standard form of the constraint matrix for VLSI problems, thereby achieving improved preprocessing results with relatively little effort. We provide analysis showing our preprocessing techniques are accurate and provide some numerical testing demonstrating the increased efficiency. The numerical tests also demonstrate that using our preprocessing in conjunction with internal preprocessing methods that come with many linear program solvers, can improve the overall performance of the linear program solver and its preprocessor.     

Minimizing the number of pickups on a multi-head placement machine

Multi-head gantry machines are becoming increasingly popular in surface mount technology (SMT), because they combine high printing speed with a moderate price. The optimization of their operation seems, however, to be very difficult. We formalize here a small subproblem of the scheduling problem of multi-headed SMT machines, namely the selection of nozzles which pick up and place components on printed circuit boards (PCB). The aim in this selection is to minimize the number of component pickups when manufacturing some PCB type. Given a sequence of component placement commands, a greedy nozzle usage policy picks, at each pickup, as many components next in the sequence as possible. If the nozzles are ‘universal’, that is, they can pick up any component, it is obvious that this policy is optimal. The situation gets more complicated once certain component types can be picked up only with certain nozzle types. We show that the greedy policy is optimal in this case, too. Finally, we do some experiments aimed at a better understanding of this subproblem.     

Capacitated dynamic lot sizing problems in closed-loop supply chain

In this paper, we address the capacitated dynamic lot sizing problem arising in closed-loop supply chain where returned products are collected from customers. These returned products can either be disposed or be remanufactured to be sold as new ones again; hence the market demands can be satisfied by either newly produced products or remanufactured ones. The capacities of production, disposal and remanufacturing are limited, and backlogging is not allowed. A general model of this problem is formulated, and several useful properties of the problem are characterized when cost functions are concave. Moreover, this problem is analyzed and solved to optimality using dynamic programming algorithms under different scenarios. It is shown that the problem with only disposal or remanufacturing can be converted into a traditional capacitated lot sizing problem and be solved by a polynomial algorithm if the capacities are constant. A pseudo-polynomial algorithm is proposed for the problem with both capacitated disposal and remanufacturing. The problem with capacitated production and remanufacturing and the problem with uncapacitated production and capacitated remanufacturing are also analyzed and solved. Through numerical experiments we show that the proposed algorithms perform well when solving problems of practical sizes. From the experimental results also indicates that it is worthwhile to expand the remanufacturing capacity only when returned products exist in a relatively long planning horizon, and production capacities have little effect on the remanufacturing plan when the demand is mainly satisfied by the production.     

Symmetric tensor decomposition by alternating gradient descent

The symmetric tensor decomposition problem is a fundamental problem in many fields, which appealing for investigation. In general, greedy algorithm is used for tensor decomposition. That is, we first find the largest singular value and singular vector and subtract the corresponding component from tensor, then repeat the process. In this article, we focus on designing one effective algorithm and giving its convergence analysis. We introduce an exceedingly simple and fast algorithm for rank-one approximation of symmetric tensor decomposition. Throughout variable splitting, we solve symmetric tensor decomposition problem by minimizing a multiconvex optimization problem. We use alternating gradient descent algorithm to solve. Although we focus on symmetric tensors in this article, the method can be extended to nonsymmetric tensors in some cases. Additionally, we also give some theoretical analysis about our alternating gradient descent algorithm. We prove that alternating gradient descent algorithm converges linearly to global minimizer. We also provide numerical results to show the effectiveness of the algorithm.     

A constant-time channel-assignment algorithm on reconfigurable meshes

The channel-assignment problem is central to the integrated circuit fabrication process. Given a two-sided printed circuit board, we wish to maken pairs of components electrically equivalent. The connections are made using two vertical runs along with a horizontal one. Each horizontal run lies in a channel. The channel-assignment problem involves minimizing the total number of channels used.Recent advances in VLSI have made it possible to build massively parallel machines. To overcome the inefficiency of long distance communications among processors, some parallel architectures have been augmented by bus systems. If such a bus system can be dynamically changed to suit communication needs among processors, it is referred to asreconfigurable. The reconfigurable mesh is one of the practical models featuring a reconfigurable bus system. In this paper, we propose a constant-time algorithm to solve the channel-assignment problem of sizen on a reconfigurable mesh of sizen×n.This work was supported by NASA under grant NCC1-99.Additional support by the National Science Foundation under grant CCR-8909996 is gratefully acknowledged.     

Meta-heuristics for dynamic lot sizing: A review and comparison of solution approaches

Proofs from complexity theory as well as computational experiments indicate that most lot sizing problems are hard to solve. Because these problems are so difficult, various solution techniques have been proposed to solve them. In the past decade, meta-heuristics such as tabu search, genetic algorithms and simulated annealing, have become popular and efficient tools for solving hard combinatorial optimization problems. We review the various meta-heuristics that have been specifically developed to solve lot sizing problems, discussing their main components such as representation, evaluation, neighborhood definition and genetic operators. Further, we briefly review other solution approaches, such as dynamic programming, cutting planes, Dantzig–Wolfe decomposition, Lagrange relaxation and dedicated heuristics. This allows us to compare these techniques. Understanding their respective advantages and disadvantages gives insight into how we can integrate elements from several solution approaches into more powerful hybrid algorithms. Finally, we discuss general guidelines for computational experiments and illustrate these with several examples.     

A Tight Analysis of the Greedy Algorithm for Set Cover

We establish significantly improved bounds on the performance of the greedy algorithm for approximatingset cover. In particular, we provide the first substantial improvement of the 20-year-old classical harmonic upper bound,H(m), of Johnson, Lovász, and Chvátal, by showing that the performance ratio of the greedy algorithm is, in fact,exactlyln m − ln ln m + Θ(1), wheremis the size of the ground set. The difference between the upper and lower bounds turns out to be less than 1.1. This provides the first tight analysis of the greedy algorithm, as well as the first upper bound that lies belowH(m) by a function going to infinity withm. We also show that the approximation guarantee for the greedy algorithm is better than the guarantee recently established by Srinivasan for the randomized rounding technique, thus improving the bounds on theintegrality gap. Our improvements result from a new approach which might be generally useful for attacking other similar problems.     

Optimal placement and sizing of capacitor using Limaçon inspired spider monkey optimization algorithm

The power system is a complex interconnected network which can be subdivided into three components: generation, distribution, and transmission. Capacitors of specific sizes are placed in the distribution network so that losses in transmission and distribution is minimum. But the decision of size and position of capacitors in this network is a complex optimization problem. In this paper, Limaçon curve inspired local search strategy (LLS) is proposed and incorporated into spider monkey optimization (SMO) algorithm to deal optimal placement and the sizing problem of capacitors. The proposed strategy is named as Limaçon inspired SMO (LSMO) algorithm. In the proposed local search strategy, the Limaçon curve equation is modified by incorporating the persistence and social learning components of SMO algorithm. The performance of LSMO is tested over 25 benchmark functions. Further, it is applied to solve optimal capacitor placement and sizing problem in IEEE-14, 30 and 33 test bus systems with the proper allocation of 3 and 5-capacitors. The reported results are compared with a network without a capacitor (un-capacitor) and other existing methods.     

The single item uncapacitated lot-sizing problem with time-dependent batch sizes: NP-hard and polynomial cases

This paper considers the uncapacitated lot sizing problem with batch delivery, focusing on the general case of time-dependent batch sizes. We study the complexity of the problem, depending on the other cost parameters, namely the setup cost, the fixed cost per batch, the unit procurement cost and the unit holding cost. We establish that if any one of the cost parameters is allowed to be time-dependent, the problem is NP-hard. On the contrary, if all the cost parameters are stationary, and assuming no unit holding cost, we show that the problem is polynomially solvable in time O(T³), where T denotes the number of periods of the horizon. We also show that, in the case of divisible batch sizes, the problem with time varying setup costs, a stationary fixed cost per batch and no unit procurement nor holding cost can be solved in time O(T³ logT).     

An algebraic multigrid-based algorithm for circuit clustering

Digital circuits have grown exponentially in their sizes over the past decades. To be able to automate the design of these circuits, efficient algorithms are needed. One of the challenging stages of circuit design is the physical design where the physical locations of the components of a circuit are determined. Coarsening or clustering algorithms have become popular with physical designers due to their ability to reduce circuit sizes in the intermediate design steps such that the design can be performed faster and with higher quality. In this paper, a new clustering algorithm based on the algebraic multigrid (AMG) technique is presented. In the proposed algorithm, AMG is used to assign weights to connections between cells of a circuit and find cells that are best suited to become the initial cells for clusters, seed cells. The seed cells and the weights between them and the other cells are then used to cluster the cells of a circuit. The analysis of the proposed algorithm proves linear-time complexity, O(N), where N is the number of pins in a circuit. The numerical experiments demonstrate that AMG-based clustering can achieve high quality clusters and improve circuit placement designs with low computational cost.     

A dynamic lot sizing model with exponential machine breakdowns

This paper addresses the dynamic lot sizing model with the assumption that the equipment is subject to stochastic breakdowns. We consider two different situations. First we assume that after a machine breakdown the setup is totally lost and new setup cost is incurred. Second we consider the situation in which the cost of resuming the production run after a failure might be substantially lower than the production setup cost. We show that under the first assumption the cost penalty for ignoring machine failures will be noticeably higher than in the classical lot sizing case with static demand. For the second case, two lot sizes per period are required, an ordinary lot size and a specific second (or resumption) lot size. If during the production of a future period demand the production quantity exceeds the second lot size, the production run will be resumed after a breakdown and terminated if the amount produced is less than this lot size. Considering the results of the static lot sizing case, one would expect a different policy. To find an optimum lot sizing decision for both cases a stochastic dynamic programming model is suggested.     

An Extended Model for the Optimal Sizing of Records

In previous work, Erickson and Luss examined the problem of optimally sizing computer records so as to minimize wasted space. They assumed that a fixed number of record sizes can be used to store messages of various lengths. If a message cannot be stored in any single record, it is stored in multiple records of the same size. However, the record size used to accommodate divided messages is not used to store any message that fits into any of the other record sizes. Here, we relax the latter constraint and allow the record size designated to store divided messages to store also other messages. A dynamic programming algorithm that finds the optimal record sizes is presented. However, since the computational effort needed to find the optimal record sizes is large, we also derive bounds for the optimal solution and give a heuristic algorithm that provides near optimal solutions.     

Cycle Double Covers in Cubic Graphs having Special Structures

In the first part of this article, we employ Thomason's Lollipop Lemma 25 to prove that bridgeless cubic graphs containing a spanning lollipop admit a cycle double cover (CDC) containing the circuit in the lollipop; this implies, in particular, that bridgeless cubic graphs with a 2‐factor F having two components admit CDCs containing any of the components in the 2‐factor, although it need not have a CDC containing all of F. As another example consider a cubic bridgeless graph containing a 2‐factor with three components, all induced circuits. In this case, two of the components may separately be used to start a CDC although it is uncertain whether the third component may be part of some CDC. Numerous other corollaries shall be given as well. In the second part of the article, we consider special types of bridgeless cubic graphs for which a prominent circuit can be shown to be included in a CDC. The interest here is the proof technique and therefore we only give the simplest case of the theorem. Notably, we show that a cubic graph that consists of an induced 2k‐circuit C together with an induced 4k‐circuit T and an independent set of 2k vertices, each joined by one edge to C and two edges to T, has a CDC starting with T.     

Buffer sizing in multi-product multi-reactor batch processes: Impact of allocation and campaign sizing policies

This paper studies the impact of management policies, such as product allocation and campaign sizing, on the required size of the finished goods inventories in a multi-product multi-reactor batch process. Demand, setup and batch processing times for these products are assumed to be stochastic, and the inventory buffer for every product type needs to be such that target customer service levels are met. To perform this analysis, we develop a queueing model that allows us to explicitly estimate service levels as a function of the buffer size, and the allocation/campaign sizing policies. This model can be used to evaluate the service level given an existing buffer configuration, as well as to determine the buffer sizes required across products to meet a pre-specified service level. It also allows us to formulate a number of insights into how product allocation decisions and campaign planning policies affect buffer sizing decisions in symmetric production systems.     

Quasi-Greedy Triangulations Approximating the Minimum Weight Triangulation

This article settles the following two longstanding open problems:

• What is the worst case approximation ratio between the greedy triangulation and the minimum weight triangulation?

• Is there a polynomial time algorithm that always produces a triangulation whose length is within a constant factor from the minimum?

The answer to the first question is that the known lower bound is tight. The second question is answered in the affirmative by using a slight modification of anO(n log n) algorithm for the greedy triangulation. We also derive some other interesting results. For example, we show that a constant-factor approximation of the minimum weight convex partition can be obtained within the same time bounds.     

Valid inequalities for the single-item capacitated lot sizing problem with step-wise costs

This paper presents a new class of valid inequalities for the single-item capacitated lot sizing problem with step-wise production costs (LS-SW). Constant sized batch production is carried out with a limited production capacity in order to satisfy the customer demand over a finite horizon. A new class of valid inequalities we call mixed flow cover, is derived from the existing integer flow cover inequalities by a lifting procedure. The lifting coefficients are sequence independent when the batch sizes (V) and the production capacities (P) are constant and when V divides P. When the restriction of the divisibility is removed, the lifting coefficients are shown to be sequence independent. We identify some cases where the mixed flow cover inequalities are facet defining. We propose a cutting plane algorithm for different classes of valid inequalities introduced in the paper. The exact separation algorithm proposed for the constant capacitated case runs in polynomial time. Computational results show the efficiency of the new class mixed flow cover compared to the existing methods.     

Two‐dimensional adaptive Fourier decomposition

One‐dimensional adaptive Fourier decomposition, abbreviated as 1‐D AFD, or AFD, is an adaptive representation of a physically realizable signal into a linear combination of parameterized Szegö and higher‐order Szegö kernels of the context. In the present paper, we study multi‐dimensional AFDs based on multivariate complex Hardy spaces theory. We proceed with two approaches of which one uses Product‐TM Systems; and the other uses Product‐Szegö Dictionaries. With the Product‐TM Systems approach, we prove that at each selection of a pair of parameters, the maximal energy may be attained, and, accordingly, we prove the convergence. With the Product‐Szegö dictionary approach, we show that pure greedy algorithm is applicable. We next introduce a new type of greedy algorithm, called Pre‐orthogonal Greedy Algorithm (P‐OGA). We prove its convergence and convergence rate estimation, allowing a weak‐type version of P‐OGA as well. The convergence rate estimation of the proposed P‐OGA evidences its advantage over orthogonal greedy algorithm (OGA). In the last part, we analyze P‐OGA in depth and introduce the concept P‐OGA‐Induced Complete Dictionary, abbreviated as Complete Dictionary. We show that with the Complete Dictionary P‐OGA is applicable to the Hardy H² space on 2‐torus. Copyright © 2016 John Wiley & Sons, Ltd.     

Greedy algorithm for functions with low mixed smoothness

In this note, we investigate the efficiency of the greedy algorithm for the classes of multivariate periodic functions with low mixed smoothness in L_q with regard to the wavelet-type basis. We find that the order of greedy approximation in the case of low smoothness is different for some range of parameters.     

The finite multiple lot sizing problem with interrupted geometric yield and holding costs

We consider the multiple lot sizing problem in production systems with random process yield losses governed by the interrupted geometric (IG) distribution. Our model differs from those of previous researchers which focused on the IG yield in that we consider a finite number of setups and inventory holding costs. This model particularly arises in systems with large demand sizes. The resulting dynamic programming model contains a stage variable (remaining time till due) and a state variable (remaining demand to be filled) and therefore gives considerable difficulty in the derivation of the optimal policy structure and in numerical computation to solve real application problems. We shall investigate the properties of the optimal lot sizes. In particular, we shall show that the optimal lot size is bounded. Furthermore, a dynamic upper bound on the optimal lot size is derived. An O(nD) algorithm for solving the proposed model is provided, where n and D are the two-state variables. Numerical results show that the optimal lot size, as a function of the demand, is not necessarily monotone.