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

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(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
Volume69
Issue number8
DOIs
StatePublished - Dec 2022

Keywords

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

Fingerprint

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