Constraint-Based Job Shop Scheduling with IILOG SCHEDULER

We introduce constraint-based scheduling and discuss its main principles. An approximation algorithm based on tree search is developed for the job shop scheduling problem using ILOG SCHEDULER. A new way of calculating lower bounds on the makespan of the job shop scheduling problem is presented and we show how such results can be used within a constraint-based approach. An empirical performance analysis shows that the algorithm we developed performs well. Finally, taking the job shop scheduling problem as a start point, we discuss how constraint-based scheduling can be used to solve more general scheduling problems.     

Modelling the dynamics of stochastic local search on <Emphasis Type="Italic">k</Emphasis>-<Emphasis Type="SmallCaps">sat</Emphasis>

A new analytical tool is presented to provide a better understanding of the search space of k-sat. This tool, termed the local value distribution , describes the probability of finding assignments of any value q′ in the neighbourhood of assignments of value q. The local value distribution is then used to define a Markov model to model the dynamics of a corresponding stochastic local search algorithm for k-sat. The model is evaluated by comparing the predicted algorithm dynamics to experimental results. In most cases the fit of the model to the experimental results is very good, but limitations are also recognised.     

The chebop system for automatic solution of differential equations

In Matlab, it would be good to be able to solve a linear differential equation by typing u = L\f, where f, u, and L are representations of the right-hand side, the solution, and the differential operator with boundary conditions. Similarly it would be good to be able to exponentiate an operator with expm(L) or determine eigenvalues and eigenfunctions with eigs(L). A system is described in which such calculations are indeed possible, at least in one space dimension, based on the previously developed chebfun system in object-oriented Matlab. The algorithms involved amount to spectral collocation methods on Chebyshev grids of automatically determined resolution. AMS subject classification (2000)  65L10, 65M70, 65N35     

Properties of Distortion Risk Measures

The current literature does not reach a consensus on which risk measures should be used in practice. Our objective is to give at least a partial solution to this problem. We study properties that a risk measure must satisfy to avoid inadequate portfolio selections. The properties that we propose for risk measures can help avoid the problems observed with popular measures, like Value at Risk (VaR _α ) or Conditional VaR _α (CVaR _α ). This leads to the definition of two new families: complete and adapted risk measures. Our focus is on risk measures generated by distortion functions. Two new properties are put forward for these: completeness, ensuring that the distortion risk measure uses all the information of the loss distribution, and adaptability, forcing the measure to use this information adequately. This research was partially funded by ^1,3 Welzia Management, SGIIC SA, RD Sistemas SA, Comunidad Autónoma de Madrid Grant s-0505/tic/000230, and MEyC Grant BEC2000-1388-C04-03 and by ² the Natural Sciences and Engineering Research Council of Canada (NSERC) Grant 36860-06.     

Spectral invariance,ellipticity, and the Fredholm property for pseudodifferential operators on weighted Sobolev spaces

The pseudodifferential operators with symbols in the Grushin classes \~S _inf0 ^sup, , 0 < 1, of slowly varying symbols are shown to form spectrally invariant unital Frécher-*-algebras (*-algebras) in L(L ²(R ⁿ )) and in L(H ^st ) for weighted Sobolev spaces H _inf ^supst defined via a weight d function . In all cases, the Fredholm property of an operator can be characterized by uniform ellipticity of the symbol. This gives a converse to theorems of Grushin and Kumano-Ta-Taniguchi. Both, the spectrum and the Fredholm spectrum of an operator turn out to be independent of the choices of s, t and .The characterization of the Fredholm property by uniform ellipticity leads to an index theorem for the Fredholm operators in these classes, extending results of Fedosov and Hörmander.     

Approximation in the mean by bounded analytic functions

Let 1<p< and . LetC _q denote the Bessel capacity in the plane. Let be the set of homomorphisms ofH (G) such that (z)= and letNP denote the set of points in G for which is not a peak set forH (G). In this note, we show that ifC _q (NP)=0, thenH (G) is dense inL _a ^p (G), the Bergman space overG.Partially supported by NSF DMS-9401234     

An index theorem for open manifolds whose ends are warped products

We give an index formula for the Dirac operator acting onL2-sections of the spinor bundle of an open spin manifold with a co-compact cylindrical end over which the metric is a warped product.     

Carl Friedrich Gauß zwischen reiner und angewandter Mathematik

Zusammenfassung  Durch geeignete Wahl von Zitaten und Interpretationen l?sst sich Carl Friedrich Gau? sowohl als „reiner“ als auch als „angewandter“ Mathematiker pr?sentieren. Der vorliegende Artikel versucht, durch einen m?glichst weiten Blick auf das wissenschaftliche Werk und das Heranziehen von Selbstzeugnissen Gau? in dieser Polarit?t zu verorten. Mathematics subject classification (2000)  01A55, 01A70, 00A30     

A simple cost minimization procedure for the (Q, r) inventory system with a specified fixed cost per stockout occasion

For fast-moving A items, Silver et al. [E.A. Silver, D.F. Pyke, R. Peterson, Inventory Management and Production Planning and Scheduling, third ed., John Wiley & Sons, New York, NY, 1998] explore the (Q, r) inventory system with a specified cost per stockout occasion. However, a number of difficulties have impeded the implement of their solution procedure. That is, the total relevant cost function is not convex in general, so the convergence of the Silver et al.’s solution procedure to the optimal solution of the total relevant cost function is not necessarily true. An easier and more accurate solution procedure is proposed to overcome the shortcoming of the Silver et al.’s solution procedure.     

On the Darling-Mandelbrot probability density and the zeros of some incomplete gamma functions

Recently, Mandelbrot has encountered and numerically investigated a probability densityp _d (t) on the nonnegative reals, where, 0D<1. this=" density=" has=" fourier=" transform=">f _d (-is), wheref _d (z)=–Dz ^d (–D, z) and (·.·) is an incomplete gamma function. Previously, Darling had met this density, but had not studied its form. We expressf _d (z) as a confluent hypergeometric function, then locate and approximate its zeros, thereby improving some results of Buchholz. Via properties of Laplace transforms, we approximatep _d (t) asymptotically ast0+ and +, then note some implications asD0+ and 1–.Communicated by Mourad Ismail.     

On the unique finite (SI) decomposition of the Jordan operator ⊕ i=1 n S(θ) for certain inner function θ

In this paper, we have proven that for the Jordan blockS() withS() (SI), _i=1 ⁿ S() =S() ⁽ⁿ⁾ (n 1) has unique finite (SI) decomposition up to a similarity. As result, we obtain that ifV is a Volterra operator onH=L ²([0, 1]), thenV ⁽ⁿ⁾ has unique finite (SI) decomposition.This project was supported by National Natural Science Foundation of China.     

Ermittlung der Wurzeln einer Gleichung 4. Grades durch Aufspalten in quadratische Faktoren

Summary In order to determine the roots of an algebraic equation of the fourth degree with real coefficients and removed cubic term a method of splitting up in two quadratic factors is used. The method follows in principle a procedure used, e. g. byZurmühl andBuckingham to determine the coefficients of the quadratic factors, but permits the use ofNewton-Raphson's method instead of linear or quadratic interpolation.     

Positive functionals on BP*-algebras

A new class of locally convex algebras, called BP^*-algebras, is introduced. It is shown that this class properly includes MQ^*-algebras which were introduced and studied by the first author andR. Rigelhof [10]. Among other results, it is proved that each positive functional on a BP^*-algebraA is admissible but not necessarily continuous as shown by an example. However, ifA, in addition, is either (i) a Q-algebra, or (ii) has an identity and is barrelled, or (iii)A is endowed with the inductive limit topology, then each positive functional onA is continuous.This work was supported by an N.R.C. Grant.     

Reverse Approximation of Energetic Solutions to Rate-Independent Processes

Energetic solutions to rate-independent processes are usually constructed via time-incremental minimization problems. In this work we show that all energetic solutions can be approximated by such incremental problems if we allow for approximate minimizers, where the error in minimization has to be of the order of the time step. Moreover, we study sequences of problems where the energy functionals have a Γ-limit. Research partially supported by Deutsche Forschungsgemeinschaft via the MATHEON project C18.     

The method of layer potentials for non-smooth domains with arbitrary topology

In this paper we discuss the solvability of boundary value problems for the Laplace operator on Lipschitz domains with arbitrary topology via boundary layers. An application to hydrodynamics is included.Partially supported by a UMC Research Board grant and UMC Summer Research Fellowship     

The numerical solution of a periodic parabolic problem subject to a nonlinear boundary condition. II

Approximating the differential equation by the standard fully implicit finite difference approximation reduces the problem to that of solving a set of non-linear algebraic equations. In the first part of this paper it was shown that Newton's method provided a satisfactory technique for the solution of this set of equations. In this paper the implementation of Newton's method is discussed, and it is shown that a device due toBickley andMacNamee can be used very successfully. A more accurate difference formula is also considered and a summary of numerical results presented.     

Machine learning for global optimization

In this paper we introduce the LeGO (Learning for Global Optimization) approach for global optimization in which machine learning is used to predict the outcome of a computationally expensive global optimization run, based upon a suitable training performed by standard runs of the same global optimization method. We propose to use a Support Vector Machine (although different machine learning tools might be employed) to learn the relationship between the starting point of an algorithm and the final outcome (which is usually related to the function value at the point returned by the procedure). Numerical experiments performed both on classical test functions and on difficult space trajectory planning problems show that the proposed approach can be very effective in identifying good starting points for global optimization.     

A robust and efficient algorithm for planar competitive location problems

In this paper we empirically analyze several algorithms for solving a Huff-like competitive location and design model for profit maximization in the plane. In particular, an exact interval branch-and-bound method and a multistart heuristic already proposed in the literature are compared with uego (Universal Evolutionary Global Optimizer), a recent evolutionary algorithm. Both the multistart heuristic and uego use a Weiszfeld-like algorithm as local search procedure. The computational study shows that uego is superior to the multistart heuristic, and that by properly fine-tuning its parameters it usually (in the computational study, always) find the global optimal solution, and this in much less time than the interval branch-and-bound method. Furthermore, uego can solve much larger problems than the interval method.     

Minimizing the natural fuel requirement for nuclear reactor power systems: A nonstandard optimal control problem

A class of model problems in nuclear reactor economics is defined and shown to be equivalent to a linear optimal control problem to which present versions of the maximum principle apparently cannot be applied. It is shown that the search for an optimal control can be restricted tocontrols of maximum fuel utilization (Comfu), and that theComfu's are in a one-to-one correspondence with the functions which satisfy certain inequalities and are solutions of a nonlinear Volterra integral equation containing the value of the cost functional as a parameter. In the general case, one can establish an iterative procedure, involving solution of the integral equation at each iteration, for approximating the optimalComfu. For some important special cases, a point on the solution corresponding to the optimalComfu is knowna priori, and thus the optimalComfu can be obtained by solving the integral equation only once. Some possible generalizations of the original economic model are also discussed.This research was sponsored by the US Atomic Energy Commission under contract with the Union Carbide Corporation.     

Extension ofUV n -valued mappings

A new method for extending upper semicontinuousUV ⁿ -valued mappings is introduced. Any upper semicontinuousUV ⁿ -valued mapping Ψ:A→Y of a closed subsetA of a separable metric spaceX into ann-connected, locallyn-connected complete metric spaceY satisfying the property of disjoint (n+1)-disks is proved to be extendable to an upper semicontinuousUV ⁿ -valued mapping Ψ′:X→Y such that Ψ′|a=Ψ. As an application, some results aboutn-soft mappings are obtained. Translated fromMatematicheskie Zametki, Vol. 66, No. 3, pp. 351–363, September, 1999.