Meta Heuristics

GRASP and path-relinking: Recent advances and applications

  • Mauricio G.C. Resende
  • Celso C. Ribeiro
    • Categories Meta Heuristics Tags , , ,

    This paper addresses recent advances and application of hybridizations of greedy randomized adaptive search procedures (GRASP) and path-relinking. We present a template for implementing path-relinking as an intensification procedure for GRASP. Enhancements to the procedure, recently described in the literature, are reviewed. The effectiveness of the procedure is illustrated experimentally. CitationAT&T Labs Research Technical Report, … Read more

    When the greedy algorithm fails

  • Joergen Bang-Jensen
  • Gregory Gutin
  • Anders Yeo
    • Categories Approximation Algorithms, Combinatorial Optimization, Meta Heuristics

    We provide a characterization of the cases when the greedy algorithm may produce the unique worst possible solution for the problem of finding a minimum weight base in a uniform independence system when the weights are taken from a finite range. We apply this theorem to TSP and the minimum bisection problem. The practical message … Read more

    Unit load and material handling considerations in facility layout design

  • Ignacio Castillo
  • Brett A. Peters
    • Categories Facility Planning and Design, Meta Heuristics

    The effectiveness of a layout design cannot be completely measured if the operational characteristics of the manufacturing system are ignored. There is, therefore, a need to develop integrated manufacturing system design models. In this paper, the integration of unit load and material handling considerations in facility layout design is presented. This integration is based on … Read more

    An extended distance-based facility layout problem

  • Ignacio Castillo
  • Brett A. Peters
    • Categories Facility Planning and Design, Meta Heuristics

    The distance-based facility layout problem with unequal-area departments has been studied by many researchers for over 30 years. Still, current approaches require certain assumptions that limit the type of solutions obtained. In this paper, we consider manufacturing systems in which replicates of the same machine type may exist in the facility and propose an extended … Read more

    A hybrid genetic algorithm for manufacturing cell formation

  • José Fernando Gonçalves
  • Mauricio G.C. Resende
    • Categories Meta Heuristics, Production and Logistics

    Cellular manufacturing emerged as a production strategy capable of solving the problems of complexity and long manufacturing lead times in batch production. The fundamental problem in cellular manufacturing is the formation of product families and machine cells. This paper presents a new approach for obtaining machine cells and product families. The approach combines a local … Read more

    Hierarchical Network Design Using Simulated Annealing

  • Jens Clausen
  • Tommy Thomadsen
    • Categories Meta Heuristics, Network Optimization, Telecommunications Tags ,

    The hierarchical network problem is the problem of finding the least cost network, with nodes divided into groups, edges connecting nodes in each groups and groups ordered in a hierarchy. The idea of hierarchical networks comes from telecommunication networks where hierarchies exist. Hierarchical networks are described and a mathematical model is proposed for a two … Read more

    A hybrid genetic algorithm for the job shop scheduling problem

  • José Fernando Gonçalves
  • Jorge José M. Mendes
  • Mauricio G.C. Resende
    • Categories Meta Heuristics, Scheduling Tags , , , ,

    This paper presents a hybrid genetic algorithm for the Job Shop Scheduling problem. The chromosome representation of the problem is based on random keys. The schedules are constructed using a priority rule in which the priorities are defined by the genetic algorithm. Schedules are constructed using a procedure that generates parameterized active schedules. After a … Read more

    A GRASP with path-relinking for the p-median problem

  • Mauricio G.C. Resende
  • Renato F. Werneck
    • Categories Applications - OR and Management Sciences, Meta Heuristics Tags , , , ,

    Given N customers and a set F of M potential facilities, the P-median problem consists in finding a subset of F with P facilities such that the cost of serving all customers is minimized. This is a well-known NP-complete problem with important applications in location science and classification (clustering). We present here a GRASP (Greedy … Read more

    Randomized heuristics for the MAX-CUT problem

  • Paola Festa
  • Panos M. Pardalos
  • Mauricio G.C. Resende
  • Celso C. Ribeiro
    • Categories Meta Heuristics Tags , , , ,

    Given an undirected graph with edge weights, the MAX-CUT problem consists in finding a partition of the nodes into two subsets, such that the sum of the weights of the edges having endpoints in different subsets is maximized. It is a well-known NP-hard problem with applications in several fields, including VLSI design and statistical physics. … Read more

    A hybrid improvement heuristic for the one-dimensional bin packing problem

  • Dario J. Aloise
  • Adriana C. Alvim
  • Fred Glover
  • Celso C. Ribeiro
    • Categories Combinatorial Optimization, Meta Heuristics Tags , , ,

    We propose in this work a hybrid improvement procedure for the bin packing problem. This heuristic has several features: the use of lower bounding strategies; the generation of initial solutions by reference to the dual min-max problem; the use of load redistribution based on dominance, differencing, and unbalancing; and the inclusion of an improvement process … Read more