Standard

Two-machine flow shop with dynamic storage space. / Berlińska, Joanna; Kononov, Alexander; Zinder, Yakov.

In: Optimization Letters, Vol. 15, No. 7, 10.2021, p. 2433-2454.

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

Harvard

Berlińska, J, Kononov, A & Zinder, Y 2021, 'Two-machine flow shop with dynamic storage space', Optimization Letters, vol. 15, no. 7, pp. 2433-2454. https://doi.org/10.1007/s11590-020-01645-5

APA

Berlińska, J., Kononov, A., & Zinder, Y. (2021). Two-machine flow shop with dynamic storage space. Optimization Letters, 15(7), 2433-2454. https://doi.org/10.1007/s11590-020-01645-5

Vancouver

Berlińska J, Kononov A, Zinder Y. Two-machine flow shop with dynamic storage space. Optimization Letters. 2021 Oct;15(7):2433-2454. doi: 10.1007/s11590-020-01645-5

Author

Berlińska, Joanna ; Kononov, Alexander ; Zinder, Yakov. / Two-machine flow shop with dynamic storage space. In: Optimization Letters. 2021 ; Vol. 15, No. 7. pp. 2433-2454.

BibTeX

@article{816370aeeb06449cbed19f24b24b6286,
title = "Two-machine flow shop with dynamic storage space",
abstract = "The publications on two-machine flow shop scheduling problems with job dependent storage requirements, where a job seizes a portion of the storage space for the entire duration of its processing, were motivated by various applications ranging from supply chains of mineral resources to multimedia systems. In contrast to the previous publications that assumed that the availability of the storage space remains unchanged, this paper is concerned with a more general case when the availability is a function of time. It strengthens the previously published result concerning the existence of an optimal permutation schedule, shows that the variable storage space availability leads to the NP-hardness in the strong sense even for unit processing times, and presents a polynomial-time approximation scheme together with several heuristic algorithms. The heuristics are evaluated by means of computational experiments.",
keywords = "Computational complexity, Dynamic storage, Makespan, Polynomial-time approximation scheme, Two-machine flow shop, CONSTRAINTS",
author = "Joanna Berli{\'n}ska and Alexander Kononov and Yakov Zinder",
year = "2021",
month = oct,
doi = "10.1007/s11590-020-01645-5",
language = "English",
volume = "15",
pages = "2433--2454",
journal = "Optimization Letters",
issn = "1862-4472",
publisher = "Springer-Verlag GmbH and Co. KG",
number = "7",

}

RIS

TY - JOUR

T1 - Two-machine flow shop with dynamic storage space

AU - Berlińska, Joanna

AU - Kononov, Alexander

AU - Zinder, Yakov

PY - 2021/10

Y1 - 2021/10

N2 - The publications on two-machine flow shop scheduling problems with job dependent storage requirements, where a job seizes a portion of the storage space for the entire duration of its processing, were motivated by various applications ranging from supply chains of mineral resources to multimedia systems. In contrast to the previous publications that assumed that the availability of the storage space remains unchanged, this paper is concerned with a more general case when the availability is a function of time. It strengthens the previously published result concerning the existence of an optimal permutation schedule, shows that the variable storage space availability leads to the NP-hardness in the strong sense even for unit processing times, and presents a polynomial-time approximation scheme together with several heuristic algorithms. The heuristics are evaluated by means of computational experiments.

AB - The publications on two-machine flow shop scheduling problems with job dependent storage requirements, where a job seizes a portion of the storage space for the entire duration of its processing, were motivated by various applications ranging from supply chains of mineral resources to multimedia systems. In contrast to the previous publications that assumed that the availability of the storage space remains unchanged, this paper is concerned with a more general case when the availability is a function of time. It strengthens the previously published result concerning the existence of an optimal permutation schedule, shows that the variable storage space availability leads to the NP-hardness in the strong sense even for unit processing times, and presents a polynomial-time approximation scheme together with several heuristic algorithms. The heuristics are evaluated by means of computational experiments.

KW - Computational complexity

KW - Dynamic storage

KW - Makespan

KW - Polynomial-time approximation scheme

KW - Two-machine flow shop

KW - CONSTRAINTS

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

U2 - 10.1007/s11590-020-01645-5

DO - 10.1007/s11590-020-01645-5

M3 - Article

AN - SCOPUS:85091142590

VL - 15

SP - 2433

EP - 2454

JO - Optimization Letters

JF - Optimization Letters

SN - 1862-4472

IS - 7

ER -

ID: 25676966