Heuristics and lower bounds for the simple assembly line balancing problem type 1: Overview,computational tests and improvements

Assigning tasks to work stations is an essential problem which needs to be addressed in an assembly line design. The most basic model is called simple assembly line balancing problem type 1 (SALBP-1). We provide a survey on 12 heuristics and 9 lower bounds for this model and test them on a traditional and a lately-published benchmark dataset. The present paper focuses on algorithms published before 2011.     

State-of-the-art exact and heuristic solution procedures for simple assembly line balancing

The assembly line balancing problem arises and has to be solved when an assembly line has to be configured or redesigned. It consists of distributing the total workload for manufacturing any unit of the product to be assembled among the work stations along the line. The so-called simple assembly line balancing problem (SALBP), a basic version of the general problem, has attracted attention of researchers and practitioners of operations research for almost half a century.In this paper, we give an up-to-date and comprehensive survey of SALBP research with a special emphasis on recent outstanding and guiding contributions to the field.     

Stronger upper and lower bounds for a hard batching problem to feed assembly lines

In this paper we present an Integer Programming reformulation for a hard batching problem encountered in feeding assembly lines. The study was motivated by the real process to feed the production flow through the shop floor in a leading automobile industry in Brazil. The problem consists of deciding the assignment of items to containers and the frequency of moves from the storage area to the line in order to meet demands with minimum cost. Better lower and upper bounds were obtained by a branch-and-bound algorithm based on the proposed reformulation. We also present valid inequalities that may improve such algorithm even further.     

An linear programming based lower bound for the simple assembly line balancing problem

The simple assembly line balancing problem is a classical integer programming problem in operations research. A set of tasks, each one being an indivisible amount of work requiring a number of time units, must be assigned to workstations without exceeding the cycle time. We present a new lower bound, namely the LP relaxation of an integer programming formulation based on Dantzig–Wolfe decomposition. We propose a column generation algorithm to solve the formulation. Therefore, we develop a branch-and-bound algorithm to exactly solve the pricing problem. We assess the quality of the lower bound by comparing it with other lower bounds and the best-known solution of the various instances from the literature. Computational results show that the lower bound is equal to the best-known objective function value for the majority of the instances. Moreover, the new LP based lower bound is able to prove optimality for an open problem.     

Some upper and lower bounds on PSD-rank

Positive semidefinite rank (PSD-rank) is a relatively new complexity measure on matrices, with applications to combinatorial optimization and communication complexity. We first study several basic properties of PSD-rank, and then develop new techniques for showing lower bounds on the PSD-rank. All of these bounds are based on viewing a positive semidefinite factorization of a matrix M as a quantum communication protocol. These lower bounds depend on the entries of the matrix and not only on its support (the zero/nonzero pattern), overcoming a limitation of some previous techniques. We compare these new lower bounds with known bounds, and give examples where the new ones are better. As an application we determine the PSD-rank of (approximations of) some common matrices.     

On lower and upper bounds of matrices

Using an approach of Bergh, we give an alternate proof of Bennett's result on lower bounds for non-negative matrices acting on non-increasing non-negative sequences in lp when p?1 and its dual version, the upper bounds when 0<p?1. We also determine such bounds explicitly for some families of matrices.     

Equilibrium problems with lower and upper bounds

In this paper, we obtain some existence results of equilibrium problems with lower and upper bounds by employing a fixed-point theorem due to Ansari and Yao [1] and Ky Fan Lemma [2], respectively. Our results give answers to the open problem raised by Isac, Sehgal and Singh [3].     

Weighted quasi-equilibrium problems with lower and upper bounds

This paper is devoted to studying the solution existence of weighted quasi-equilibrium problems with lower and upper bounds by using maximal element theorems, a fixed point theorem of set-valued mappings and Fan–KKM theorem, respectively. Some new results are obtained.     

Recursive lower and dual upper bounds for Bermudan-style options

Although Bermudan options are routinely priced by simulation and least-squares methods using lower and dual upper bounds, the latter are hardly optimized. In this paper, we optimize recursive upper bounds, which are more tractable than the original/nonrecursive ones, and derive two new results: (1) An upper bound based on (a martingale that depends on) stopping times is independent of the next-stage exercise decision and hence cannot be optimized. Instead, we optimize the recursive lower bound, and use its optimal recursive policy to evaluate the upper bound as well. (2) Less time-intensive upper bounds that are based on a continuation-value function only need this function in the continuation region, where this continuation value is less nonlinear and easier to fit (than in the entire support). In the numerical exercise, both upper bounds improve over state-of-the-art methods (including standard least-squares and pathwise optimization). Specifically, the very small gap between the lower and the upper bounds derived in (1) implies the recursive policy and the associated martingale are near optimal, so that these two specific lower/upper bounds are hard to improve, yet the upper bound is tighter than the lower bound.     

Computing upper and lower bounds in interval decision trees

This article presents algorithms for computing optima in decision trees with imprecise probabilities and utilities. In tree models involving uncertainty expressed as intervals and/or relations, it is necessary for the evaluation to compute the upper and lower bounds of the expected values. Already in its simplest form, computing a maximum of expectancies leads to quadratic programming (QP) problems. Unfortunately, standard optimization methods based on QP (and BLP – bilinear programming) are too slow for the evaluation of decision trees in computer tools with interactive response times. Needless to say, the problems with computational complexity are even more emphasized in multi-linear programming (MLP) problems arising from multi-level decision trees. Since standard techniques are not particularly useful for these purposes, other, non-standard algorithms must be used. The algorithms presented here enable user interaction in decision tools and are equally applicable to all multi-linear programming problems sharing the same structure as a decision tree.     

Systems of quasi-equilibrium problems with lower and upper bounds

In this work, we consider systems of quasi-equilibrium problems with lower and upper bounds and establish the existence of their solutions by using some known maximal element theorems for a family of multivalued maps. Our problems are more general than the one posed in [G. Isac, V.M. Sehgal, S.P. Singh, An alternative version of a variational inequality, Indian J. Math. 41 (1999) 25–31]. As a particular case, we also get the answer to the problem raised in [G. Isac, V.M. Sehgal, S.P. Singh, An alternative version of a variational inequality, Indian J. Math. 41 (1999) 25–31].     

Convex upper and lower bounds for present value functions

In this paper we present an efficient methodology for approximating the distribution function of the net present value of a series of cash‐flows, when discounting is presented by a stochastic differential equation as in the Vasicek model and in the Ho–Lee model. Upper and lower bounds in convexity order are obtained. The high accuracy of the method is illustrated for cash‐flows for which no analytical results are available. Copyright © 2001 John Wiley & Sons, Ltd.     

Some upper and lower bounds on the coupon collector problem

The classical coupon collector problem is closely related to probabilistic-packet-marking (PPM) schemes for IP traceback problem in the Internet. In this paper, we study the classical coupon collector problem, and derive some upper and lower bounds of the complementary cumulative distribution function (ccdf) of the number of objects (coupons) that one has to check in order to detect a set of different objects. The derived bounds require much less computation than the exact formula. We numerically find that the proposed bounds are very close to the actual ccdf when detecting probabilities are set to the values common to the PPM schemes.     

Single source unsplittable flows with arc-wise lower and upper bounds

Mathematical Programming - In a digraph with a source and several destination nodes with associated demands, an unsplittable flow routes each demand along a single path from the common source to...     

A lower and upper bounds version of a variational inequality

Introducing the concept of extremal subset to solve one open problem raised in [1]: find the conditions for a lower and upper bounds version of a variational inequality. A few applications are given.     

Systematic data generation and test design for solution algorithms on the example of SALBPGen for assembly line balancing

Recently, the importance of correctly designed computational experiments for testing algorithms has been a subject of extended discussions. Whenever real-world data is lacking, generated data sets provide a substantive methodological tool for experiments. Focused research questions need to base on specialized, randomized and sufficiently large data sets, which are sampled from the population of interest. We integrate the generation of data sets into the process of scientific testing.     

Simple and U-type assembly line balancing problems with a learning effect

In this paper, we introduced learning effect into assembly line balancing problems. In many realistic settings, the produced worker(s) (or machine(s)) develops continuously by repeated the same or similar activities. Therefore, the production time of product shortens if it is processed later. We show that polynomial solutions can be obtained for both simple assembly line balancing problem (SALBP) and U-type line balancing problem (ULBP) with learning effect.     

A survey on problems and methods in generalized assembly line balancing

Assembly lines are traditional and still attractive means of mass and large-scale series production. Since the early times of Henry Ford several developments took place which changed assembly lines from strictly paced and straight single-model lines to more flexible systems including, among others, lines with parallel work stations or tasks, customer-oriented mixed-model and multi-model lines, U-shaped lines as well as unpaced lines with intermediate buffers.In any case, an important decision problem, called assembly line balancing problem, arises and has to be solved when (re-) configuring an assembly line. It consists of distributing the total workload for manufacturing any unit of the product to be assembled among the work stations along the line.Assembly line balancing research has traditionally focused on the simple assembly line balancing problem (SALBP) which has some restricting assumptions. Recently, a lot of research work has been done in order to describe and solve more realistic generalized problems (GALBP). In this paper, we survey the developments in GALBP research.