Maximizing total early work in a distributed two-machine flow-shop

The problem of maximizing total early work in a two-machine flow-shop, in which n jobs are to be scheduled subject to a common due date d, has been recently studied in the scheduling literature. An O(n²d⁴) time dynamic programming algorithm was presented first for the weighted case, and then for the unweighted case another O(n²d²) running time dynamic programming algorithm was proposed and converted into an (Formula presented.) time fully polynomial time approximation scheme (FPTAS). By establishing new problem properties, we present an O(nd²) time dynamic programming algorithm and an (Formula presented.) time FPTAS for the unweighted problem. We generalize the problem to a distributed setting of m parallel two-machine flow-shops, develop an O(nd^3m) time dynamic programming algorithm, an (Formula presented.) time FPTAS, and three integer linear programming (ILP) formulations for it. Computational experiments are conducted to appraise the proposed ILP models.