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

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


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.

Original languageEnglish
Pages (from-to)1124-1137
Number of pages14
JournalNaval Research Logistics
Issue number8
StatePublished - Dec 2022


  • distributed flow-shop
  • dynamic programming
  • early work
  • integer linear programming
  • scheduling
  • two-machine flow-shop


Dive into the research topics of 'Maximizing total early work in a distributed two-machine flow-shop'. Together they form a unique fingerprint.

Cite this