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

Abstract 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 2 d 4 ) time dynamic programming algorithm was presented first for the weighted case, and then for the unweighted case another O ( n 2 d 2 ) running time dynamic programming algorithm was proposed and converted into an time fully polynomial time approximation scheme (FPTAS). By establishing new problem properties, we present an O ( nd 2 ) time dynamic programming algorithm and an 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 3 m ) time dynamic programming algorithm, an time FPTAS, and three integer linear programming (ILP) formulations for it. Computational experiments are conducted to appraise the proposed ILP models.