Maximizing the weighted number of just‐in‐time jobs in several two‐machine scheduling systems

The problem of maximizing the weighted number of just‐in‐time jobs in a two‐machine flow shop scheduling system is known to be $\mathrm{𝒩𝒫}$ ‐hard (Choi and Yoon in J. Shed. 10:237–243, 2007). However, the question of whether this problem is strongly or ordinarily $\mathrm{𝒩𝒫}$ ‐hard remains an open question. We provide a pseudo‐polynomial time algorithm to solve this problem, proving that it is $\mathrm{𝒩𝒫}$ ‐hard in the ordinary sense. Moreover, we show how the pseudo‐polynomial algorithm can be converted to a fully polynomial time approximation scheme (FPTAS). In addition, we prove that the same problem is strongly $\mathrm{𝒩𝒫}$ ‐hard for both a two‐machine job shop scheduling system and a two‐machine open shop scheduling system.