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.

原文English
頁(從 - 到)1124-1137
頁數14
期刊Naval Research Logistics
69
發行號8
DOIs
出版狀態Published - 12月 2022

指紋

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

引用此