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.