Two new approximation schemes for maximizing the weighted number of just-in-time jobs in a multi-machine proportionate flow shop

We propose two new fully polynomial-time approximation schemes for maximizing the weighted number of just-in-time jobs in a multi-machine proportionate flow shop. Both are set up using recently proposed frameworks for the construction of this type of approximation schemes for monotone dynamic programming formulations, and are faster by a linear factor with respect to the number of jobs, up to log terms, compared to the state-of-the-art fully polynomial-time approximation scheme for the problem.