ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
  • Articles  (11)
  • heuristics  (11)
  • 1995-1999  (8)
  • 1980-1984  (3)
  • 1975-1979
  • 1996  (8)
  • 1984  (3)
  • 1978
  • 1976
  • Economics  (11)
  • Architecture, Civil Engineering, Surveying
Collection
  • Articles  (11)
Source
Keywords
Publisher
Years
  • 1995-1999  (8)
  • 1980-1984  (3)
  • 1975-1979
Year
Topic
  • 1
    Electronic Resource
    Electronic Resource
    Heuristics for permutation flow shop scheduling with batch setup times (1996)
    Springer
    OR spectrum 18 (1996), S. 67-80 
    Details
    ISSN: 1436-6304
    Keywords: Flow shop scheduling ; batch setup times ; group technology ; manufactoring cells ; heuristics ; Flow Shop Probleme ; Setup Zeiten ; Gruppentechnologie ; Heuristiken
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung In dieser Arbeit werden Permutationsflußprobleme mit Batch Setup Zeiten betrachtet. Jeder Job hat die gleiche technologische Reihenfolge. Die Jobs sind in Gruppen eingeteilt. Gegeben sind Bearbeitungszeient ij für Jobi auf Maschinej sowie Setup Zeitens rj auf Maschinej, wenn ein Job derr-ten Gruppe nach einem Job einer anderen Gruppe bearbeitet wird. Es wird vorausgesetzt, daß auf allen Maschinen die gleiche Reihenfolge der Jobs gewählt wird. In der Arbeit werden sowohl das Problem der Minimierung der Gesamtbearbeitungszeit als auch das Problem der Minimierung der Summe der Bearbeitungsendtermine mit Item oder Batch Verfügbarkeit betrachtet. Für diese Probleme werden konstruktive und iterative Algorithmen entwickelt. Die konstruktiven Algorithmen basieren auf Einfügungstechniken mit Beamsuche. Es werden geeignete Nachbarschaftsstrukturen eingeführt und auf lokaler Suche und Wiedereinfügungstechniken basierende iterative Algorithmen entwickelt. Die Algorithmen wurden an Beispielen mit bis zu 80 Jobs getestet.
    Notes: Abstract In this paper we consider permutation flow shop scheduling problems with batch setup times. Each job has to be processed on each machine once and the technological routes are identical for all jobs. The set of jobs is divided into groups. There are given processing timest ij of jobi on machinej and setup timess rj on machinej when a job of ther-th group is processed after a job of another group. It is assumed that the same job order has to be chosen on each machine. We consider both the problems of minimizing the makespan and of minimizing the sum of completion times, where batch or item availability of the jobs is assumed. For these problems we give various constructive and iterative algorithms. The constructive algorithms are based on insertion techniques combined with beam search. We introduce suitable neighbourhood structures for such problems with batch setup times and describe iterative algorithms that are based on local search and reinsertion techniques. The developed algorithms have been tested on a large collection of problems with up to 80 jobs.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01539731
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Heuristics for the integer one-dimensional cutting stock problem: A computational study (1996)
    Springer
    OR spectrum 18 (1996), S. 131-144 
    Details
    ISSN: 1436-6304
    Keywords: Cutting stock ; integer solutions ; heuristics ; linear programming ; column generation ; numerical experiments ; Zuschneideprobleme ; Ganzzahligkeit ; Heuristiken ; Lineare Optimierung ; Spaltengenerierung ; Numerische Experimente
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung In der vorliegenden Arbeit betrachten wir das Problem der Bestimmung ganzzahliger Lösungen für das Standardproblem der eindimensionalen Zuschnittplanung. Insbesondere werden eine spezielle Klasse heuristischer Lösungsverfahren, die in der Literatur beschrieben sind, sowie einige naheliegende Varianten dieser Verfahren vorgestellt. Auf der Grundlage eines numerischen Experiments, bei dem 4.000 Probleme zufällig erzeugt und gelöst wurden, werden die Verfahren miteinander verglichen und im Hinblick auf die Kriterien „Lösungsqualität“ und „Rechenzeitbedarf“ beurteilt. Dabei zeigt sich nicht nur, daß zwei Verfahren deutlich besser als die übrigen einzustufen sind, sondern auch, daß mit ihrer Hilfe nahezu jede Problemausprägung des klassischen eindimensionalen Zuschneideproblems optimal gelöst werden kann.
    Notes: Abstract In this paper the problem of generating integer solutions to the standard one-dimensional cutting stock problem is treated. In particular, we study a specific class of heuristic approaches that have been proposed in the literature, and some straightforward variants. These methods are compared with respect to solution quality and computing time. Our evaluation is based on having solved 4,000 randomly generated test problems. Not only will it be shown that two methods are clearly superior to the others but also that they solve almost any instance of the standard one-dimensional cutting stock problem to an optimum.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01539705
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Exact and approximate algorithms for the multi-period procurement problem where dedicated supplier capacity can be reserved (1996)
    Springer
    OR spectrum 18 (1996), S. 197-207 
    Details
    ISSN: 1436-6304
    Keywords: Multi-period inventory problem ; capacity reservation ; dynamic programming ; heuristics ; Mehrperiodiges Lagerhaltungsproblem ; zu reservierende Rohstoffmenge ; dynamische Programmierung ; Heuristiken
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung Vorliegende Arbeit behandelt ein mehrperiodiges Lagerhaltungsproblem, worin sowohl die Nachfrage als auch die Lieferkapazität eines bestimmten Rohstoffs diskrete Zufallsvariable mit bekannter Verteilungsfunktion sind. Vor Beginn der ersten Periode ist die beim Lieferanten zu reservierende Rohstoffmenge für jede Periode zu bestimmen, darauf anschließend ist zu Beginn jeder Periode die tatsächlich zu bestellende Rohstoffmenge zu bestimmen. Ein exakter, aufbranch and bound und dynamischer Programmierung basierender Algorithmus und verschiedene Heuristiken für dieses Problem werden vorgestellt und miteinander verglichen. Die Heuristiken schneiden dabei sehr gut ab, da sie ausgezeichnete, suboptimale Lösungen mit erheblich weniger Rechenaufwand finden.
    Notes: Abstract This paper is concerned with a multi-period inventory problem where the demand and the supplier capacity of a given key resource are discrete random variables with known probability distribution. The procurement manager has to answer two types of questions: how much supplier quantity to reserve for each period (where all of these reservations have to madeprior to the start of the first period) and how large an order quantity to use at start of each period. An exact procedure, based on branch and bound and dynamic programming, as well as various heuristic methods to solve the problem are presented in this paper. Heuristic methods are shown to perform extremely well in the sense that they provide near optimal strategies while requiring much less computational effort than the exact method.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01540156
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    A probabilistic analysis of the set covering problem (1984)
    Springer
    Annals of operations research 1 (1984), S. 255-271 
    Details
    ISSN: 1572-9338
    Keywords: Probabilistic analysis ; set covering ; heuristics
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract A probabilistic analysis of the minimum cardinality set covering problem (SCP) is developed, considering a stochastic model of the (SCP), withn variables andm constraints, in which the entries of the corresponding (m, n) incidence matrix are independent Bernoulli distributed random variables, each with constant probabilityp of success. The behaviour of the optimal solution of the (SCP) is then investigated as bothm andn grow asymptotically large, assuming either an incremental model for the evolution of the matrix (for each size, the matrixA is obtained bordering a matrix of smaller size by new columns and rows) or an independent one (for each size, an entirely new set of entries forA are considered). Two functions ofm are identified, which represent a lower and an upper bound onn in order the (SCP) to be a.e. feasible and not trivial. Then, forn lying within these bounds, an asymptotic formula for the optimum value of the (SCP) is derived and shown to hold a.e. The performance of two simple randomized algorithms is then analyzed. It is shown that one of them produces a solution value whose ratio to the optimum value asymptotically approaches 1 a.e. in the incremental model, but not in the independent one, in which case the ratio is proved to be tightly bounded by 2 a.e. Thus, in order to improve the above result, a second randomized algorithm is proposed, for which it is proved that the ratio between the approximate solution value and the optimum approaches 1 a.e. also in the independent model.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01874392
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Dynamic tabu search strategies for the traveling purchaser problem (1996)
    Springer
    Annals of operations research 63 (1996), S. 253-275 
    Details
    ISSN: 1572-9338
    Keywords: Traveling purchaser problem ; heuristics ; tabu search
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract Tabu search is a metastrategy for guiding known heuristics to overcome local optimality with a large number of successful applications reported in the literature. In this paper we investigate two dynamic strategies, the reverse elimination method and the cancellation sequence method. The incorporation of strategic oscillation as well as a combination of these methods are developed. The impact of the different methods is shown with respect to the traveling purchaser problem, a generalization of the classical traveling salesman problem. The traveling purchaser problem is the problem of determining a tour of a purchaser buying several items in different shops by minimizing the total amount of travel and purchase costs. A comparison of the tabu search strategies with a simulated annealing approach is presented, too.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02125457
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    A tabu thresholding algorithm for arc crossing minimization in bipartite graphs (1996)
    Springer
    Annals of operations research 63 (1996), S. 233-251 
    Details
    ISSN: 1572-9338
    Keywords: Tabu thresholding ; tabu search ; arc crossing minimization ; automatic graph drawing ; heuristics
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract Acyclic directed graphs are commonly used to model complex systems. The most important criterion to obtain a readable map of an acyclic graph is that of minimizing the number of arc crossings. In this paper, we present a heuristic for solving the problem of minimizing the number of arc crossings in a bipartite graph. It consists of a novel and easier implementation of fundamental tabu search ideas without explicit use of memory structures (a tabu thresholding approach). Computational results are reported on a set of 250 randomly generated test problems. Our algorithm has been compared with the two best heuristics published in the literature and with the optimal solutions for the test problems, size permitting.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02125456
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    The continuous reactive tabu search: Blending combinatorial optimization and stochastic search for global optimization (1996)
    Springer
    Annals of operations research 63 (1996), S. 151-188 
    Details
    ISSN: 1572-9338
    Keywords: Tabu search ; local search ; approximate algorithms ; heuristics ; global optimization ; stochastic minimization ; hybrid algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract A novel algorithm for the global optimization of functions (C-RTS) is presented, in which a combinatorial optimization method cooperates with a stochastic local minimizer. The combinatorial optimization component, based on the Reactive Tabu Search recently proposed by the authors, locates the most promising “boxes”, in which starting points for the local minimizer are generated. In order to cover a wide spectrum of possible applications without user intervention, the method is designed with adaptive mechanisms: the box size is adapted to the local structure of the function to be optimized, the search parameters are adapted to obtain a proper balance of diversification and intensification. The algorithm is compared with some existing algorithms, and the experimental results are presented for a variety of benchmark tasks.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02125453
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    Metaheuristics: A bibliography (1996)
    Springer
    Annals of operations research 63 (1996), S. 511-623 
    Details
    ISSN: 1572-9338
    Keywords: Artificial intelligence ; bibliography ; combinatorial optimization ; constraint logic programming ; evolutionary computation ; genetic algorithms ; greedy random adaptive search procedure ; heuristics ; hybrids ; local search ; metaheuristics ; neural networks ; non-monotonic search strategies ; problem-space method ; simulated annealing ; tabu search ; threshold algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract Metaheuristics are the most exciting development in approximate optimization techniques of the last two decades. They have had widespread successes in attacking a variety of difficult combinatorial optimization problems that arise in many practical areas. This bibliography provides a classification of a comprehensive list of 1380 references on the theory and application of metaheuristics. Metaheuristics include but are not limited to constraint logic programming; greedy random adaptive search procedures; natural evolutionary computation; neural networks; non-monotonic search strategies; space-search methods; simulated annealing; tabu search; threshold algorithms and their hybrids. References are presented in alphabetical order under a number of subheadings.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02125421
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    Probabilistic analysis of geometric location problems (1984)
    Springer
    Annals of operations research 1 (1984), S. 215-238 
    Details
    ISSN: 1572-9338
    Keywords: Geometric location problems ; probabilistic analysis ; heuristics ; k center ; k median
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract We analyze the behaviour of thek center and median problems forn points randomly distributed in an arbitrary regionA ofR d . Under a mild assumption on the regionA, we show that fork≦k(n)=o(n/logn), the objective function values of the discrete and continuous versions of these problems are equal to each otheralmost surely. For the two-dimensional case, both these problems can be solved by placing the centers or medians in an especially simple regular hexagonal pattern (the ‘honeycomb heuristic’ of Papadimitriou). This yields the exact asymptotic values for thek center and median problem, namely, α(|A|/k)1/2 and β(|A|/k)1/2, where |A| denotes the volume ofA, α and β are known constants, and the objective of the median problem is given in terms of the average, rather than the usual total, distance. For the 3- and 4-dimensional case, similar results can be obtained for the center problem to within an accuracy of roughly one percent. As a by-product, we also get asymptotically optimal algorithms for the 2-dimensionalp-normk median problem and for the twin problems of minimizing the maximum number of vertices served by any center and similarly for maximizing the minimum.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01874390
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    When are NP-hard location problems easy? (1984)
    Springer
    Annals of operations research 1 (1984), S. 201-214 
    Details
    ISSN: 1572-9338
    Keywords: Probabilistic analysis ; location problems ; heuristics ; NP-hard problems ; approximation algorithm ; asymptotic optimality
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract We discuss in this paper several location problems for which it is an NP-hard problem to find an approximate solution. Given certain assumptions on the input distributions, we present polynomial algorithms that deliver a solution asymptotically close to the optimum with probability that is asymptotically one (the exact nature of this asymptotic convergence is described in the paper). In that sense the subproblems defined on the specified family of inputs are in fact easy.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01874389
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 11
    Electronic Resource
    Electronic Resource
    New uses of linear arithmetic in automated theorem proving by induction (1996)
    Springer
    Journal of financial services research 16 (1996), S. 39-78 
    Details
    ISSN: 1573-0735
    Keywords: Induction ; automated theorem proving ; heuristics ; linear arithmetic ; Presburger arithmetic ; generalization ; semantic unification
    Source: Springer Online Journal Archives 1860-2000
    Topics: Economics
    Notes: Abstract Zhang, Kapur, and Krishnamoorthy introduced a cover set method for designing induction schemes for automating proofs by induction from specifications expressed as equations and conditional equations. This method has been implemented in the theorem prover Rewrite Rule Laboratory (RRL) and a proof management system Tecton built on top of RRL, and it has been used to prove many nontrivial theorems and reason about sequential as well as parallel programs. The cover set method is based on the assumption that a function symbol is defined by using a finite set of terminating (conditional or unconditional) rewrite rules. The termination ordering employed in orienting the rules is used to perform proofs by well-founded induction. The left sides of the rules are used to design different cases of an induction sheme, and recursive calls to the function made in the right side can be used to design appropriate instantiations for generating induction hypotheses. A weakness of this method is that it relies on syntactic unification for generating an induction scheme for a conjecture. This paper goes a step further by proposing semantic analysis for generating an induction scheme for a conjecture from a cover set. We discuss the use of a decision procedure for Presburger arithmetic (quantifier-free theory of numbers with the addition operation and relational predicates 〉, 〈, ≠, =, ⩾, ⩽) for performing semantic analysis about numbers. The decision procedure is used to generate appropriate induction schemes for a conjecture by using cover sets of function taking numbers as arguments. This extension of the cover set method automates proofs of many theorems that otherwise require human guidance and hints. The effectiveness of the method is demonstrated by using some examples that commonly arise in reasoning about specifications and programs. It is also shown how semantic analysis using a Presburger arithmetic decision procedure can be used for checking the completeness of a cover set of a function defined by using operations such as + and — on numbers. With this check, many function definitions used in a proof of the prime factorization theorem stating that every number can be factored uniquely into prime factors, which had to be checked manually, an now be checked automatically in RRL. The use of the decision procedure for guiding generalization for generating conjectures and merging induction schemes is also illustrated.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00244459
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...