An improved FPTAS for maximizing the weighted number of just‐in‐time jobs in a two‐machine flow shop problem

Recently, Shabtay and Bensoussan (2012) developed an original exact pseudo‐polynomial algorithm and an efficient $ϵ$ ‐approximation algorithm (FPTAS) for maximizing the weighted number of just‐in‐time jobs in a two‐machine flow shop problem. The complexity of the FPTAS is $O$ (( $n^4/ϵ$ )log( $n$ / $ϵ$ )), where $n$ is the number of jobs. In this note we suggest another pseudo‐polynomial algorithm that can be converted to a new FPTAS which improves Shabtay–Bensoussan’s complexity result and runs in $O(n^3/ϵ)$ time.