Complexity results on a paint shop problem.

DOI10.1016/S0166-218X(03)00442-6zbMath1036.90035OpenAlexW2037461057MaRDI QIDQ1427181

Winfried Hochstättler, Th. Epping, Peter Oertel

Publication date: 14 March 2004

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(03)00442-6

zbMATH Keywords

Dynamic programmingNP-completenessSequencingPaint shop

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Production models (90B30) Dynamic programming (90C39)

Related Items (12)

Minimizing sequence-dependent setup costs in feeding batch processes under due date restrictions ⋮ Fair Division and Generalizations of Sperner- and KKM-type Results ⋮ Greedy colorings of words ⋮ Greedy versus recursive greedy: uncorrelated heuristics for the binary paint shop problem ⋮ Complexity issues in vertex-colored graph pattern matching ⋮ Computing solutions of the paintshop-necklace problem ⋮ Some heuristics for the binary paint shop problem and their expected number of colour changes ⋮ Complexity results on restricted instances of a paint shop problem for words ⋮ Greedy colorings for the binary paintshop problem ⋮ Accelerated dynamic programming algorithms for a car resequencing problem in automotive paint shops ⋮ Paintshop, odd cycles and necklace splitting ⋮ Unnamed Item

Cites Work

• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Unnamed Item

This page was built for publication: Complexity results on a paint shop problem.