Two-agent scheduling with deteriorating jobs on a single parallel-batching machine: refining computational complexity

摘要

Tang et al. (Eur J Oper Res 263:401-411, 2017) have recently introduced a parallel-batching machine scheduling problem with linearly deteriorating jobs of two agents and presented a computational complexity classification of various special cases of this problem, including a number of NP-hardness proofs. We refine these results by demonstrating strong NP-hardness of several special cases, which are proved NP-hard in the ordinary sense in Tang et al. (Eur J Oper Res 263:401-411, 2017). Our reduction employs the problem studied in the first issue of Journal of Scheduling.