lagrangean relaxation

Approximating the Pareto frontier for bi-objective preventive maintenance and workshop scheduling. A Lagrangean lower bounding methodology for evaluating contracting forms

  • Gabrijela Obradović
  • Ann-Brith Strömberg
  • Felix Held
    • Categories (Mixed) Integer Linear Programming, Scheduling Tags , , ,

    Effective planning of preventive maintenance plays an important role in maximizing the operational readiness of any industrial system. We consider an operating system and a maintenance workshop governed by two stakeholders who collaborate based on a mutual contract: components of the operating system that need maintenance are sent to the maintenance workshop, where necessary maintenance … Read more

    A hybrid Lagrangean metaheuristic for single machine scheduling problem with sequence-dependent setup times and due dates

  • Carlos Roberto Venâncio de Carvalho
  • Thiago Henrique Nogueira
  • Martín Gómez Ravetti
  • Gabriel Pinheiro Alves Santos
    • Categories Meta Heuristics, Scheduling Tags , , , ,

    In this article, a hybrid Lagrangean metaheuristic is proposed for single machine scheduling problems with sequence-dependent setup times and due dates. The objective function considered throughout this work, is to minimize the total tardiness. Related works and taxonomies for hybrid metaheuristics are analyzed, through a thorough historical overview. The proposed hybrid Lagrangean metaheuristic is a … Read more

    A hybrid Lagrangean heuristic with GRASP and path-relinking for set K-covering

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

    The set multicovering or set K-covering problem is an extension of the classical set covering problem, in which each object is required to be covered at least K times. The problem finds applications in the design of communication networks and in computational biology. We describe a GRASP with path-relinking heuristic for the set K-covering problem, … Read more

    An Improved Algorithm for the Generalized Quadratic Assignment Problem

  • Monique Guignard
  • Peter M. Hahn
  • Artur Alves Pessoa
  • Yi-Rong Zhu
    • Categories 0-1 Programming, Combinatorial Optimization Tags , ,

    In the Generalized Quadratic Assignment Problem (GQAP), given M facilities and N locations, one must assign each facility to one location so as to satisfy the given facility space requirements, minimizing the sum of installation and facility interaction costs. In this paper, we propose a new Lagrangean relaxation and a lower bounding procedure for the … Read more

    A Lagrangean Relaxation and Decomposition Algorithm for the Video Placement and Routing Problem

  • Tolga Bektas
  • Osman Oguz
  • Iradj Ouveysi
    • Categories Telecommunications Tags , , , , ,

    Video on Demand (VoD) is a technology used to provide a number of programs to a number of users on request. In developing a VoD system, a fundamental problem is load balancing, which is further characterized by optimally placing videos to a number of predefined servers and routing the user program requests to available resources. … Read more

    The Integration of an Interior-Point Cutting-Plane Method within a Branch-and-Price Algorithm

  • Samir Elhedhli
  • Jean-Louis Goffin
    • Categories Applications - OR and Management Sciences, Integer Programming Tags , , , ,

    This paper presents a novel integration of interior point cutting plane methods within branch-and-price algorithms. Unlike the classical method, columns are generated at a “central” dual solution by applying the analytic centre cutting plane method (ACCPM) on the dual of the full master problem. First, we introduce improvements to ACCPM. We propose a new procedure … Read more