CS Papers (2005 – 2014)

“A note on the complexity of the concurrent open shop problem” by Thomas A. Roemer (2006 paper) – The paper presents a proof, via a reduction from the 3-Partition Problem, that the concurrent open shop problem is unary NP-hard, even if we only have 2 machines and all jobs have equal weight. The paper also contains a comprehensive literature review of complexity results for concurrent open shop. (2006 paper)