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.
| Institutes: | Mathematik |
|---|---|
| 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 |
| URN: | urn:nbn:de:bvb:703-opus-7369 |
| Document Type: | Article |
| Language: | English |
| Date of Publication (online): | 05.10.2010 |





