A method for determining cost-efficient inspection strategies in multistage production systems

This is a summary of the author’s PhD thesis. The thesis, written in English, was defended on 6 March 2006, and was supervised by Rik Van Landeghem and Claude Van Mechelen. A copy is available from the author upon request. This PhD thesis focuses on (cost-)efficient quality control for multistage production processes, a major issue to manufacturers. Subjecting a larger product fraction to inspection, or tightening the acceptance limits, will normally lead to a higher product quality, but will also result in higher costs of inspection, scrap and rework. Quantifying this trade-off and thus establishing ways of finding an economic optimum is at the heart of this research. Thereto, a metaheuristic solution approach, consisting of an evolutionary algorithm combined with simulation, is presented and validated.      

Triangles in space or building (and analyzing) castles in the air

We show that the total combinatorial complexity of all non-convex cells in an arrangement ofn (possibly intersecting) triangles in 3-space isO(n ^7/3 logn) and that this bound is almost tight in the worst case. Our bound significantly improves a previous nearly cubic bound of Pach and Sharir. We also present a (nearly) worst-case optimal randomized algorithm for calculating a single cell of the arrangement and an alternative less efficient, but still subcubic algorithm for calculating all non-convex cells, analyze some special cases of the problem where improved bounds (and faster algorithms) can be obtained, and describe applications of our results to translational motion planning for polyhedra in 3-space.Work on this paper by the first author has been supported by an AT&T Bell Laboratories PhD Scholarship. Work on this paper by the second author has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant No. NSF-DCR-83-20085, by grants from the Digital Equipment Corporation, the IBM Corporation, and by a research grant from the NCRD — the Israeli National Council for Research and Development. A preliminary version of this paper has appeared inProc. 4th ACM Symp. on Computational Geometry, Urbana, Illinois, 1988.     

On the sensitivity of the LU factorization

This paper gives sensitivity analyses by two approaches forL andU in the factorizationA=LU for general perturbations inA which are sufficiently small in norm. By the matrix-vector equation approach, we derive the condition numbers for theL andU factors. By the matrix equation approach we derive corresponding condition estimates. We show how partial pivoting and complete pivoting affect the sensitivity of the LU factorization. The material presented here is a part of the first author's PhD thesis under the supervision of the second author. This research was supported by NSERC of Canada Grant OGP0009236.     

Scheduling with earliness–tardiness penalties and parallel machines

This is a summary of the author’s PhD thesis supervised by Francis Sourd and Philippe Chrétienne and defended on 30 January 2007 at the Université Pierre et Marie Curie, Paris. The thesis is written in French and is available from the author upon request. This work is about scheduling on parallel machines in order to minimize the total sum of earliness and tardiness costs. To solve some variants of this problem we propose: an exact method based on continuous relaxations of convex reformulations derived from a 0–1 quadratic program; a heuristic algorithm that relies on a new exponential size neighborhood search; finally, a lower bound method based on a polynomial time solution of a preemptive scheduling problem for which the cost functions of the jobs have been changed into so called position costs functions. Partial funding provided by CONACyT (Mexican Council for Science&Technology).     

A strong variational algorithm for delay systems

In this paper, we present a convergent extension of the first-order strong-variational algorithm by Mayne and Polak (Ref. 1) for solving optimal control problems with control constraints to delay systems. Although the algorithm is similar to the one presented in Ref. 1, the proof of convergence is different, since the differential dynamic techniques used by Mayne and Polak are not applicable.This work forms part of the author's PhD Dissertation and was conducted at the Imperial College of Science and Technology under a studentship awarded by the UK Science and Engineering Research Council. This assistance is gratefully acknowledged. The author also wishes to thank Dr. R. B. Vinter for his encouragement and help.     

A general Farkas lemma and characterization of optimality for a nonsmooth program involving convex processes

In this paper, a generalization of the Farkas lemma is presented for nonlinear mappings which involve a convex process and a generalized convex function. Using this result, a complete characterization of optimality is obtained for the following nonsmooth programming problem: minimizef(x), subject to – H(x) wheref is a locally Lipschitz function satisfying a generalized convexity hypothesis andH is a closed convex process.This work was partially written while the author was a PhD Student under the supervision of Dr. B. D. Craven, University of Melbourne, whose helpful guidance is much appreciated.     

Models and algorithms for the reconfiguration of distributed wireless switching systems

This paper is a summary of the author’s PhD thesis entitled “Models and algorithms for the reconfiguration of wireless switching systems”. The thesis deals with the study of a strongly NP-hard resource-constrained scheduling problem arising from the telecommunication industry. This work was supervised by Jacques Carlier and Dritan Nace, both from Université de Technologie de Compiègne, and carried out while the author was a System Architect within Nortel GSM Access R&D organization. The thesis, which is written in both French and English, has been defended on 29 March 2007 and is available by email request to the author. This research was supported in part by Association Nationale de la Recherche Technique grant CIFRE-121/2004.     

Concentrator location in telecommunications

We survey the main results in the authors PhD Thesis presented in December 2002 at the Université Libre de Bruxelles and supervised by Prof. Martine Labbé. The dissertation is written in English and is available at smg.ulb.ac.be. Several versions of concentrator location problems in telecommunication networks are studied. The thesis presents a list of polyhedral results for these problems and a branch and cut algorithm for the most general problem introduced.Received: October 2003, AMS classification: 90B80, 90B18, 90C57     

Twisted Semigroup Crossed Products and Twisted Toeplitz Algebras of Ordered Groups

Let г^＋ be the positive cone of a totally ordered abelian group г, and σa cocycle in г. We study the twisted crossed products by actions of г＋ as endomorphisms of C^＊-algebras, and use this to generalize the theorem of Ji.     

On the elation structure of specific designs

Consider symmetric 2-designs D which have an automorphism group G containing sufficiently many elations. This paper proves that all elations in G have the same order and classifies the elation structure (i.e. centre-axis pairs) of a well-defined subgroup of G. For one class, D is necessarily a projective space.The results in this paper form part of a PhD thesis submitted by the author to the University of London. The author gratefully acknowledges the support of the Commonwealth Scholarship Commission.     

A framework for robust and flexible optimisation using metaheuristics

This is a summary of the most important results presented in the authors PhD thesis. This thesis, written in English, was defended on 13 June 2003 and supervised by Johan Springael and Gerrit K. Janssens. A copy is available from the author upon request. This PhD thesis focuses on stochastic problems and develops a framework to find robust and flexible solutions of such problems. The framework is applied to several well-known problems in the realm of supply chain design. Besides this framework, the thesis contains several other important contributions. A new type of robustness and flexibility is proposed, that expresses the need for solutions to remain approximately the same when changes occur in the problem data. Several distance measures are developed to calculate the distance (or similarity) between solutions of different permutation type problems. A new type of genetic algorithm is also proposed, that uses a distance measure to maintain a diverse population of high-quality solutions.Received: June 2003     

Group algebras with almost maximal lie nilpotency index

LetK G be a non-commutative Lie nilpotent group algebra of a groupG over a fieldK. It is known that the Lie nilpotency index ofKG is at most |G′|+1, where |G′| is the order of the commutator subgroup ofG. In [4] the groupsG for which this index is maximal were determined. Here we list theG’s for which it assumes the next highest possible value. The present paper is a part of the PhD dissertation of the author.     

The Vertex Coloring Problem and its generalizations

This is a summary of the author’s PhD thesis supervised by Paolo Toth and defended on 29 May 2007 at the Università di Bologna. The thesis is written in English and is available from the author upon request. The first part of this work deals with the Vertex Coloring Problem and its generalizations, for which models, bounds and algorithms are proposed. The Second Part is dedicated to a different problem on graphs, namely a Routing Problem in telecommunication networks where not only the efficiency, but also the fairness of the solution is considered.      

The mathematics of F. J. Almgren, Jr.

Frederick Justin Almgren, Jr, one of the world’s leading geometric analysts and a pioneer in the geometric calculus of variations, died on February 5, 1997 at the age of 63 as a result of myelodysplasia. Throughout his career, Almgren brought great geometric insight, technical power, and relentless determination to bear on a series of the most important and difficult problems in his field. He solved many of them and, in the process, discovered ideas which turned out to be useful for many other problems. This article is a more-or-less chronological survey of Almgren’s mathematical research. (Excerpts from this article appeared in the December 1997 issue of theNotices of the American Mathematical Society.) Almgren was also an outstanding educator, and he supervised the thesis work of nineteen PhD students; the 1997 volume 6 issue of the journalExperimental Mathematics is dedicated to Almgren and contains reminiscences by two of his PhD students and by various colleagues. A general article about Almgren’s life appeared in the October 1997Notices of the American Mathematical Society [MD]. See [T3]for a brief biography.     

Generating the Acyclic Orientations of a Graph

The acyclic orientations of a graph are related to its chromatic polynomial, to its reliability, and to certain hyperplane arrangements. In this paper, an algorithm for listing the acyclic orientations of a graph is presented. The algorithm is shown to requireO(n) time per acyclic orientation generated. This is the most efficient algorithm known for generating acyclic orientations.     

On the generation of circuits and minimal forbidden sets

We present several complexity results related to generation and counting of all circuits of an independence system. Our motivation to study these problems is their relevance in the solution of resource constrained scheduling problems, where an independence system arises as the subsets of jobs that may be scheduled simultaneously. We are interested in the circuits of this system, the so-called minimal forbidden sets, which are minimal subsets of jobs that must not be scheduled simultaneously. As a consequence of the complexity results for general independence systems, we obtain several complexity results in the context of resource constrained scheduling. On that account, we propose and analyze a simple backtracking algorithm that generates all minimal forbidden sets for such problems. The performance of this algorithm, in comparison to a previously suggested divide-and-conquer approach, is evaluated empirically using instances from the project scheduling library PSPLIB.Acknowledgement We appreciate the input of two anonymous referees. Particularly the deep remarks of one of them greatly improved our understanding of several issues; he also suggested the simplified Example 1. We thank Marc Pfetsch and Alexander Grigoriev for several enlightening discussions. Marc Pfetsch also pointed us to the paper [15]. Parts of this work were done while the authors were PhD students at the Technische Universität Berlin, Germany, where Frederik Stork was supported by DFG grant Mo 446/3-3, and Marc Uetz was supported by bmb+f grant 03-MO7TU1-3 and GIF grant I 246-304.02/97.     

A method of estimating computational complexity based on input conditions for N-vehicle problem

This paper proposes a method of estimating computational complexity of problem through analyzing its input condition for N-vehicle exploration problem. The N-vehicle problem is firstly formulated to determine the optimal replacement in the set of permutations of 1 to N. The complexity of the problem is factorial of N （input scale of problem）. To balance accuracy and efficiency of general algorithms, this paper mentions a new systematic algorithm design and discusses correspondence between complexity of problem and its input condition, other than just putting forward a uniform approximation algorithm as usual. This is a new technique for analyzing computation of NP problems. The method of corresponding is then presented. We finally carry out a simulation to verify the advantages of the method： 1） to decrease computation in enumeration; 2） to efficiently obtain computational complexity for any N-vehicle case; 3） to guide an algorithm design for any N-vehicle case according to its complexity estimated by the method.     

On automorphisms of the degrees that preserve jumps

IfF is an automorphism of the degrees of unsolvability that preserves the jump operator, thenF leaves fixed all the degreesc that satisfyc≧0 ⁽³⁾. The results of this paper were part of the author’s PhD thesis (Illinois 1977), supervised by Carl G. Jockusch, Jr.     

Constantin integral inequalities on time scales

We establish an integral inequality, on a so called time scale, related to those appearing in Constantin (J. Math. Anal. Appl. 197 (1996), 855–863) and Yang and Tan (JIPAM J. Inequal. Pure Appl. Math. 8 (2007), No. 2, Art 57). Our result can be used to obtain estimates for solutions of certain dynamic equations. Moreover, the bounds obtained in this paper are sharper than those known previously in the literature. This work was completed with the support of the Portuguese Foundation for Science and Technology (FCT) through the PhD fellowship SFRH/BD/39816/2007.     

Edge-Coloring Partialk-Trees

Many combinatorial problems can be efficiently solved for partialk-trees (graphs of treewidth bounded byk). The edge-coloring problem is one of the well-known combinatorial problems for which no efficient algorithms were previously known, except a polynomial-time algorithm of very high complexity. This paper gives a linear-time sequential algorithm and an optimal parallel algorithm which find an edge-coloring of a given partialk-tree with the minimum number of colors for fixedk.