Abstract: The paper is concerned with the two-machine scheduling problem where each job is to be processed on the first-stage machine and after that on the second-stage machine. In order to be processed, each job requires storage space that it seizes at the start of its processing on the first-stage machine and releases only at the completion of processing on the second-stage machine. The storage space is limited and its consumption varies from job to job. The goal is to minimise the time needed for the completion of all jobs. All instances of the considered scheduling problem are classified by means of five parameters. This leads to the sixty four families of instances. For each family, the paper establishes its computational complexity and, in the case of polynomial-time solvability, presents a polynomial-time algorithm, constructing an optimal schedule. © 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC part of Springer Nature.

Cite: Zinder Y. , Kononov A. , Fung J.
A 5-parameter complexity classification of the two-stage flow shop scheduling problem with job dependent storage requirements
Journal of Combinatorial Optimization. 2021. V.42. N2. P.276-309. DOI: 10.1007/s10878-021-00706-4 WOS Scopus OpenAlex

Dates:

Accepted:

Jan 19, 2021

Identifiers:

Web of science:	WOS:000615551600002
Scopus:	2-s2.0-85100551629
OpenAlex:	W3127761927

Citing:

DB	Citing
Scopus	3
OpenAlex	4
Web of science	3

Altmetrics: