A note on the complexity of two supply chain scheduling problems

We consider two supply chain scheduling problems in which s suppliers preprocess different parts of the jobs to be assembled by the manufacturer under the common sequence constraint, with the goal of minimizing the total weighted number of tardy parts and minimizing the total late work of the parts, respectively. Ren et al. (Information Processing Letter 113: 609-601, 2013) showed that both of the above two problems are unary NP-hard. But their proof is invalid. In this paper, we present a new proof of the unary NP-hardness for the same problems.

Automated summary

The study focuses on two supply chain scheduling problems aiming to minimize the total weighted number of tardy parts and the total late work of parts. Previous research claimed that both problems are unary NP-hard, but their proof was found to be invalid. The paper presents a new proof of the unary NP-hardness for the same problems.