Two-Machine Flow Shop with a Dynamic Storage Space and UET Operations | Sciact - Система учета научной деятельности ИМ СО РАН

Two-Machine Flow Shop with a Dynamic Storage Space and UET Operations Научная публикация

Конференция

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

Журнал

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

Вых. Данные

Год: 2019, Том: 991, Номер: 2, Страницы: 1139-1148 Страниц : 10 DOI: 10.1007/978-3-030-21803-4_112

Ключевые слова

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

Авторы

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

Организации

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

Опубликована online:

15 июн. 2019 г.

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

БД	Цитирований
OpenAlex	1
Scopus	2