Complexity Results on a Paint Shop Problem

Epping, Thomas and Hochstättler, Winfried and Oertel, Peter (2004) Complexity Results on a Paint Shop Problem.
Published in: Discrete Applied Mathematics Vol. 136 (2-3). pp. 217-226.

Abstract

Motivated by an application in the automobile industry, we present results and conjectures on a new combinatorial problem: Given a word w and restricted reservoirs of colored letters, synthesize w with a minimal number of color changes. We present a dynamic program that solves this problem and runs in polynomial time if we bound both, the number of different letters and colors. Otherwise, the problem is shown to be NP-complete. Additionally, we focus on upper bounds on the minimal number of color changes, simultaneously giving results for special instances, and posing open questions.


Actions:
Download: [img] Postscript - Preprinted Version
Download (212kB) | Preview
Download: [img] PDF - Preprinted Version
Download (225kB) | Preview
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Article
Citations: 16 (Google Scholar) | 3 (Web of Science)
Uncontrolled Keywords: dynamic programming NP-completeness Paint Shop sequencing
Subjects:
  • 90-XX Operations research, mathematical programming > 90Bxx Operations research and management science > 90B30 Production models

  • 90-XX Operations research, mathematical programming > 90Bxx Operations research and management science > 90B35 Scheduling theory, deterministic

  • 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C39 Dynamic programming

    		•
    Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Schrader
    Mathematical Institute > Prof. Dr. Faigle
    Related URLs:
    Deposit Information:
    ZAIK Number: zaik2002-434
    Depositing User: Thomas Epping
    Date Deposited: 06 Jun 2002 00:00
    Last Modified: 12 Jan 2012 10:56
    URI: http://e-archive.informatik.uni-koeln.de/id/eprint/434