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

- 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.

In this paper, we analyse the makespan minimization problem in the two-processor flowshop environment, where the processing time of each job depends on its position in a sequence (a position dependent job processing time) that is equivalent to the number of previously processed jobs. Namely, if processing times of jobs increase with the number of processed jobs, then the aging (fatigue/deterioration) effect is modelled, whereas the non-increasing dependency describes the learning effect. We prove that the considered problem becomes strongly NP-hard if the processing time of each job is described by a piecewise linear function dependent on its position in a sequence; we analyse two types of functions: non-decreasing (aging) and non-increasing (learning). Furthermore, we describe the strong NP-hardness proof supporting method and elucidate correctness of our other strong NP-hardness proofs. Additionally, we provide a modification of the Johnson's algorithm and prove that it optimally solves the considered problem in the two-processor flowshop environment if job processing times are characterized by a common linear (non-increasing or non-decreasing) dependency on a job position.