Two-Machine Flow Shop with a Dynamic Storage Space and UET Operations

Two-Machine Flow Shop with a Dynamic Storage Space and UET Operations Full article

Conference

World Congress on Global Optimization. Optimization of Complex Systems: Theory, Models, Algorithms and Applications
08-10 Jul 2019 , University of Lorraine, Metz, France.

Journal

Advances in Intelligent Systems and Computing
ISSN: 2194-5357 , E-ISSN: 2194-5365

Output data

Year: 2019, Volume: 991, Number: 2, Pages: 1139-1148 Pages count : 10 DOI: 10.1007/978-3-030-21803-4_112

Tags

Two-machine flow shop Makespan Dynamic storage Computational complexity Polynomial-time approximation scheme

Authors

Berlińska Joanna ¹ , Kononov Alexander ² , Zinder Yakov ³

Affiliations

1	Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Poznań, Poland
2	Sobolev Institute of Mathematics, Novosibirsk, Russia
3	School of Mathematical and Physical Sciences, University of Technology Sydney, Ultimo, Australia

The paper establishes the NP-hardness in the strong sense of a two-machine flow shop scheduling problem with unit execution time (UET) operations, dynamic storage availability, job dependent storage requirements, and the objective to minimise the time required for the completion of all jobs, i.e. to minimise the makespan. Each job seizes the required storage space for the entire period from the start of its processing on the first machine till the completion of its processing on the second machine. The considered scheduling problem has several applications, including star data gathering networks and certain supply chains and manufacturing systems. The NP-hardness result is complemented by a polynomial-time approximation scheme (PTAS) and several heuristics. The presented heuristics are compared by means of computational experiments.

Berlińska J. , Kononov A. , Zinder Y.
Two-Machine Flow Shop with a Dynamic Storage Space and UET Operations
Advances in Intelligent Systems and Computing. 2019. V.991. N2. P.1139-1148. DOI: 10.1007/978-3-030-21803-4_112 Scopus OpenAlex

Published online:

Jun 15, 2019

Scopus:	2-s2.0-85068418716
OpenAlex:	W2950517844

DB	Citing
OpenAlex	1
Scopus	2