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

Alexandre Dolgui, Mikhail Y. Kovalyov, Bertrand M.T. Lin*


研究成果: Article同行評審

3 引文 斯高帕斯(Scopus)


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(n2d4) time dynamic programming algorithm was presented first for the weighted case, and then for the unweighted case another O(n2d2) 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(nd2) 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(nd3m) 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.

頁(從 - 到)1124-1137
期刊Naval Research Logistics
出版狀態Published - 12月 2022


深入研究「Maximizing total early work in a distributed two-machine flow-shop」主題。共同形成了獨特的指紋。