The computational complexity analysis of the two-processor flowshop problems with position dependent job processing times

作者：

Highlights：

• The two-processor flowshop makespan scheduling with piecewise linear position learning/aging effects is strongly NP-hard.

• The two-processor flowshop makespan scheduling with common linear position learning/aging effects is polynomially solvable.

• The boundary between polynomially solvable and NP-hard has been is compressed.

• The strong NP-hardness proof supporting method is described.

摘要

•The two-processor flowshop makespan scheduling with piecewise linear position learning/aging effects is strongly NP-hard.•The two-processor flowshop makespan scheduling with common linear position learning/aging effects is polynomially solvable.•The boundary between polynomially solvable and NP-hard has been is compressed.•The strong NP-hardness proof supporting method is described.

论文关键词：Scheduling,Learning,Aging,Deteriorating,Flowshop,Computational complexity

论文评审过程：Available online 3 August 2013.

论文官网地址：https://doi.org/10.1016/j.amc.2013.06.086