Just-in-time scheduling in two-stage flexible flow shops

A flow shop is a scheduling model in which each job must follow the same fixed order of processing stages, with each stage typically consisting of a single machine. We focus on the objective of maximizing the weighted number of just-in-time (JIT) jobs, jobs that are completed exactly at their due dates. It is known that the classical two-stage flow shop is NP-hard even when all jobs have unit processing times on the second machine. We extend this setting to the two-stage flexible (or hybrid) flow shop, where the second stage consists of m identical parallel machines. We investigate the computational complexity of this problem, presenting both hardness and algorithmic results. In particular, we show that the unweighted version is NP-hard, while the weighted version admits a pseudo-polynomial time algorithm when m = O(1). Additionally, we provide results for natural special cases, and demonstrate that the problem admits a fully polynomial-time approximation scheme (FPTAS) when m = O(1), or when one of two other structural parameters is small.