Exploiting combinatorial relaxations to solve a routing & scheduling problem in car body manufacturing

Motivated by the laser sharing problem (LSP) in car body manufacturing, we define the new general routing and scheduling problem (RSP). In the RSP, multiple servers have to visit and process jobs; renewable resources are shared among them. The goal is to find a makespan-minimal scheduled dispatch. We present complexity results as well as a branch-and-bound algorithm for the RSP. This is the first algorithm that is able to solve the LSP for industrially relevant problem scales.

Download full text files

Export metadata

  • Export Bibtex
  • Export RIS
  • frontdoor_exportcitavi

Additional Services

    Share in Twitter Search Google Scholar
Author: Jörg Rambau, Cornelius Schwarz
Year of Completion:2010
SWD-Keyword:Branch-and-Bound-Methode; Dynamische Optimierung; Industrieroboter; Komplexität; Zusammenstoß
Tag:Gemischt-ganzzahlige Optimierung; Tourenplanung
branch and bound; collisions; mixed integer programming; robot dispatching; routing and scheduling
Dewey Decimal Classification:510 Mathematik
Document Type:Article
Date of Publication (online):05.10.2010