Complexity results on a paint shop problem

被引:32
作者
Epping, T [1 ]
Hochstättler, W
Oertel, P
机构
[1] BTU Cottbus, Dept Math, Cottbus, Germany
[2] Ford Werke AG, Cologne, Germany
关键词
dynamic programming; NP-completeness; paint shop; sequencing;
D O I
10.1016/S0166-218X(03)00442-6
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
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. (C) 2003 Elsevier B.V. All rights reserved.
引用
收藏
页码:217 / 226
页数:10
相关论文
共 5 条
[1]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[2]  
EPPING T, 2001, ZAIK2001418 CTR APPL
[3]  
EPPING T, 2002, BTUISGDI00102 BTU
[4]   Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming [J].
Goemans, MX ;
Williamson, DP .
JOURNAL OF THE ACM, 1995, 42 (06) :1115-1145
[5]  
SPIECKERMANN S, 1996, ASIM MITTEILUNGEN, V54, P367