Design,planning, scheduling,and control problems of flexible manufacturing systems

The design and use of flexible manufacturing systems (FMSs) involve some intricate operations research problems.FMS design problems include, for example, determining the appropriate number of machine tools of each type, the capacity of the material handling system, and the size of buffers.FMS planning problems include the determination of which parts should be simultaneously machined, the optimal partition of machine tools into groups, allocations of pallets and fixtures to part types, and the assignment of operations and associated cutting tools among the limited-capacity tool magazines of the machine tools.FMS scheduling problems include determining the optimal input sequence of parts and an optimal sequence at each machine tool given the current part mix.FMS control problems are those concerned with, for example, monitoring the system to be sure that requirements and due dates are being met and that unreliability problems are taken care of. This paper defines and describes these FMS problems in detail for OR/MS researchers to work on.     

Conditional Stability Estimates for Ill-Posed PDE Problems by Using Interpolation

The focus of this article is on conditional stability estimates for ill-posed inverse problems in partial differential equations. Conditional stability estimates have been obtained in related literature by a couple different methods. In this article, we propose a method called interpolation method, which is based on interpolation in variable Hilbert scales. We provide the theoretical background of this method and show that optimal conditional stability estimates are obtained. The capabilities of our method are illustrated by a comprehensive collection of different inverse and ill-posed PDE problems containing elliptic and parabolic problems, one source problem and the problem of analytic continuation.     

Green's theorem from the viewpoint of applications

Making use of a line integral defined without use of the partition of unity, Green's theorem is proved in the case of two-dimensional domains with a Lipschitz-continuous boundary for functions belonging to the Sobolev spaces W^1,p () H^1,p () (1 p < ).     

The fresh-salt water interface in a semi-pervious aquifer

The paper determines the location of the steady state interface between fresh and saltwater in a plane coastal aquifer. The lower boundary is totally impervious while the upper one is impervious below land and semi-pervious below the sea allowing an outflow through this part of the upper boundary. The model equations reduce to two boundary value problems, one valid in x < 0 and the other in x > 0 here x is measured along the aquifer with the origin at the coast. In each region unknown boundaries have to be determined as part of the solution using boundary and continuity conditions. Two cases are presented using the Dupuit approximation. One where the solution can be written down in terms of elementary functions and the other in which we have to use a phase space analysis.     

Contributions to zero-sum problems

A prototype of zero-sum theorems, the well-known theorem of Erd?s, Ginzburg and Ziv says that for any positive integer n, any sequence a₁,a₂,…,a_2n-1 of 2n-1 integers has a subsequence of n elements whose sum is 0 modulo n. Appropriate generalizations of the question, especially that for (Z/pZ)^d, generated a lot of research and still have challenging open questions. Here we propose a new generalization of the Erd?s-Ginzburg-Ziv theorem and prove it in some basic cases.     

A generalization of a classical zero-sum problem

In this note, we supply the details of the proof of the fact that if a₁,…,a_n+Ω(n) are integers, then there exists a subset M⊂{1,…,n+Ω(n)} of cardinality n such that the equation

     

One class of separable optimization problems: solution method,application

Convexity and generalized convexity play a central role in mathematical economics and optimization theory. So, the research on criteria for convexity or generalized convexity is one of the most important aspects in mathematical programming, in order to characterize the solutions set. Many efforts have been made in the few last years to weaken the convexity notions. In this article, taking in mind Craven's notion of K-invexity function (when K is a cone in ? ⁿ ) and Martin's notion of Karush–Kuhn–Tucker invexity (hereafter KKT-invexity), we define a new notion of generalized convexity that is both necessary and sufficient to ensure every KKT point is a global optimum for programming problems with conic constraints. This new definition is a generalization of KKT-invexity concept given by Martin and K-invexity function given by Craven. Moreover, it is the weakest to characterize the set of optimal solutions. The notions and results that exist in the literature up to now are particular instances of the ones presented here.     

The inverse conductivity problem via the calculus of functions of bounded variation

In this work, a novel approach for the solution of the inverse conductivity problem from one and multiple boundary measurements has been developed on the basis of the implication of the framework of $BV$ functions. The space of the functions of bounded variation is recommended here as the most appropriate functional space hosting the conductivity profile under reconstruction. For the numerical investigation of the inversion of the inclusion problem, we propose and implement a suitable minimization scheme of an enriched—constructed herein—functional, by exploiting the inner structure of $BV$ space. Finally, we validate and illustrate our theoretical results with numerical experiments.     

Sensitivity analysis for generalized linear-quadratic problems

In this paper, we study simple necessary and sufficient conditions for the stability of generalized linear-quadratic programs under perturbations of the data. The concept of generalized linear-quadratic problem was introduced by Rockafellar and Wets and consists of solving saddle points of a linear-quadratic convex concave functionJ onU×V, whereU andV are polyhedral convex sets in ⁿ and ^m . This paper also establishes results on the closedness and the uniform boundedness of the saddle-point solution sets. These properties are then used to obtain results on the continuity and the directional derivative of the perturbed saddle value.The research of the first author was supported by the CEE, Grant No. CI1-CT92-0046.     

The newton method for C1αmaps In anach Spaceis$fr1;∗$f:∗

On the basis of a work by B.Döring for ?¹→ ?¹maps we give a thourough proof of the convergence and on the convergence speed of the Newton Method for C ¹αmaps in Banach spaces. We describe the application of this classical method for the existence (and local uniqueness and approximation) of nonlinear eigenvalue problems - abstractly - and for the concrete case of nonlinear Dirichlet problem which was for- merly attacked by variational methods     

An Inverse Problem for the Matrix Schrödinger Equation

By modifying and generalizing some old techniques of N. Levinson, a uniqueness theorem is established for an inverse problem related to periodic and Sturm-Liouville boundary value problems for the matrix Schrödinger equation.     

Lower semicontinuity in domain optimization problems

In the present paper, the lower semicontinuity of certain classes of functionals is studied when the domain of integration, which defines the functionals, is not fixed. For this purpose, a certain class of domains introduced by Chenais is employed. For this class of domains, a basic lemma is proved that plays an essential role in the derivations of the lower-semicontinuity theorems. These theorems are applied to the study of the existence of the optimal domain in domain optimization problems; a boundary-value problem of Neumann type or Dirichlet type is the main constraint in these optimization problems.The author wishes to express his sincere thanks to the reviewer for his valuable comments, which made the paper more readable; the reviewer also pointed out that Lemma 2.1 in the text is a direct corollary to a lemma by Chenais (Ref. 9). He thanks Prof. Y. Sakawa of Osaka University for encouragement.     

Convex regularization of multi-channel images based on variants of the TV-model

Abstract

We discuss existence and regularity results for multi-channel images in the setting of isotropic and anisotropic variants of the TV-model.     

A new transform method for evolution partial differential equations

We introduce a new transform method for solving initial-boundary-valueproblems for linear evolution partial differential equationswith spatial derivatives of arbitrary order. This method isillustrated by solving several such problems on the half-line{t > 0, 0 < x < }, and on the quarter-plane {t >0, 0 < x_j < , j = 1, 2}. For equations in one space dimensionthis method constructs q(x, t) as an integral in the complexk-plane involving an x-transform of the initial condition anda t-transform of the boundary conditions. For equations in twospace dimensions it constructs q(x₁, x₂, t) as an integral inthe complex (k₁, k₂)-planes involving an (x₁, x₂)-transformof the initial condition, an (x₂, t)-transform of the boundaryconditions at x₁ = 0, and an (x₁, t)-transform of the boundaryconditions at x₂ = 0. This method is simple to implement andyet it yields integral representations which are particularlyconvenient for computing the long time asymptotics of the solution.     

Complexity issues for the sandwich homogeneous set problem

Graph sandwich problems were introduced by Golumbic et al. (1994) in [12] for DNA physical mapping problems and can be described as follows. Given a property Π of graphs and two disjoint sets of edges E₁, E₂ with E₁⊆E₂ on a vertex set V, the problem is to find a graph G on V with edge set E_s having property Π and such that E₁⊆E_s⊆E₂.In this paper, we exhibit a quasi-linear reduction between the problem of finding an independent set of size k≥2 in a graph and the problem of finding a sandwich homogeneous set of the same size k. Using this reduction, we prove that a number of natural (decision and counting) problems related to sandwich homogeneous sets are hard in general. We then exploit a little further the reduction and show that finding efficient algorithms to compute small sandwich homogeneous sets would imply substantial improvement for computing triangles in graphs.     

Searching for an edge in a graph with restricted test sets

Consider the (2,n) group testing problem with test sets of cardinality at most 2. We determine the worst case number c₂ of tests for this restricted group testing problem.Furthermore, using a game theory approach we solve the generalization of this group testing problem to the following search problem, which was suggested by Aigner in [M. Aigner, Combinatorial Search, Wiley-Teubner, 1988]: Suppose a graph G(V,E) contains one defective edge e. We search for the endpoints of e by asking questions of the form “Is at least one of the vertices of X an endpoint of e?”, where X is a subset of V with |X|≤2. What is the minimum number c₂(G) of questions, which are needed in the worst case to identify e?We derive sharp upper and lower bounds for c₂(G). We also show that the determination of c₂(G) is an NP-complete problem. Moreover, we establish some results on c₂ for random graphs.     

Nonautonomous regulator problem in Hilbert spaces

In this paper, we study the quadratic optimal control problem on the half linett _o, for nonautonomous control processes in Hilbert spaces. We prove that the quadratic optimal control problem has a solution if, and only if, an associated Riccati equation has a positive solution fortt _o. The optimal control is given in feedback form. If a detectability assumption holds, then we prove that the optimal control is a stabilizing feedback control when the associated Riccati equation has a positive solution which is bounded fortt _o.This work was performed under the auspices of the National Research Council of Italy (CNR).     

A local monotonicity formula for an inhomogenous singular perturbation problem and applications

In this paper we prove a local monotonicity formula for solutions to an inhomogeneous singularly perturbed diffusion problem of interest in combustion. This type of monotonicity formula has proved to be very useful for the study of the regularity of limits u of solutions of the singular perturbation problem and of ∂{u > 0}, in the global homogeneous case. As a consequence of this formula we prove that u has an asymptotic development at every point in ∂{u > 0} where there is a nonhorizontal tangent ball. These kind of developments have been essential for the proof of the regularity of ∂{u > 0} for Bernoulli and Stefan free boundary problems. We also present applications of our results to the study of the regularity of ∂{u > 0} in the stationary case including, in particular, its regularity in the case of energy minimizers. We present as well a regularity result for traveling waves of a combustion model that relies on our monotonicity formula and its consequences.The fact that our results hold for the inhomogeneous problem allows a very wide applicability. Indeed, they may be applied to problems with nonlocal diffusion and/or transport. The research of the authors was partially supported by Fundación Antorchas Project 13900-5, Universidad de Buenos Aires grant X052, ANPCyT PICT No 03-13719, CONICET PIP 5478. The authors are members of CONICET.