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

Alexandre Dolgui; Mikhail Y. Kovalyov; Bertrand M.T. Lin

doi:10.1002/nav.22076

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

Institute of Information Management

Research output: Contribution to journal › Article › peer-review

5 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(n²d⁴) time dynamic programming algorithm was presented first for the weighted case, and then for the unweighted case another O(n²d²) 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(nd²) 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(nd^3m) 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 language	English
Pages (from-to)	1124-1137
Number of pages	14
Journal	Naval Research Logistics
Volume	69
Issue number	8
DOIs	https://doi.org/10.1002/nav.22076
State	Published - Dec 2022

Keywords

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

Access to Document

10.1002/nav.22076

Cite this

@article{bfa683c02cf64d5a9d34800c6d024f18,

title = "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(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.",

keywords = "FPTAS, distributed flow-shop, dynamic programming, early work, integer linear programming, scheduling, two-machine flow-shop",

author = "Alexandre Dolgui and Kovalyov, {Mikhail Y.} and Lin, {Bertrand M.T.}",

note = "Publisher Copyright: {\textcopyright} 2022 Wiley Periodicals LLC.",

year = "2022",

month = dec,

doi = "10.1002/nav.22076",

language = "English",

volume = "69",

pages = "1124--1137",

journal = "Naval Research Logistics",

issn = "0894-069X",

publisher = "John Wiley & Sons Inc.",

number = "8",

}

TY - JOUR

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

AU - Dolgui, Alexandre

AU - Kovalyov, Mikhail Y.

AU - Lin, Bertrand M.T.

PY - 2022/12

Y1 - 2022/12

N2 - 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.

AB - 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.

KW - FPTAS

KW - distributed flow-shop

KW - dynamic programming

KW - early work

KW - integer linear programming

KW - scheduling

KW - two-machine flow-shop

UR - http://www.scopus.com/inward/record.url?scp=85136847376&partnerID=8YFLogxK

U2 - 10.1002/nav.22076

DO - 10.1002/nav.22076

M3 - Article

AN - SCOPUS:85136847376

SN - 0894-069X

VL - 69

SP - 1124

EP - 1137

JO - Naval Research Logistics

JF - Naval Research Logistics

IS - 8

ER -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this