On a borderline between the NP-hard and polynomial-time solvable cases of the flow shop with job-dependent storage requirements Научная публикация
| Журнал |
Journal of Global Optimization
ISSN: 0925-5001 , E-ISSN: 1573-2916 |
||||
|---|---|---|---|---|---|
| Вых. Данные | Год: 2022, Том: 83, Номер: 3, Страницы: 445-456 Страниц : 12 DOI: 10.1007/s10898-021-01097-w | ||||
| Ключевые слова | Computational complexity; Flow shop; Job-dependent storage requirements; Makespan | ||||
| Авторы |
|
||||
| Организации |
|
Информация о финансировании (1)
| 1 | Институт математики им. С.Л. Соболева СО РАН | 0314-2019-0014 |
Реферат:
The paper is concerned with the two-machine flow shop, where each job requires an additional resource (referred to as storage space) from the start of its first operation till the end of its second operation. The storage requirement of a job is determined by the processing time of its first operation. At any point in time, the total consumption of this additional resource cannot exceed a given limit (referred to as the storage capacity). The goal is to minimise the makespan, i.e. to minimise the time needed for the completion of all jobs. This problem is NP-hard in the strong sense. The paper analyses how the parameter - a lower bound on the storage capacity specified in terms of the processing times, affects the computational complexity.
Библиографическая ссылка:
Kononov A.
, Memar J.
, Zinder Y.
On a borderline between the NP-hard and polynomial-time solvable cases of the flow shop with job-dependent storage requirements
Journal of Global Optimization. 2022. V.83. N3. P.445-456. DOI: 10.1007/s10898-021-01097-w WOS Scopus РИНЦ OpenAlex
On a borderline between the NP-hard and polynomial-time solvable cases of the flow shop with job-dependent storage requirements
Journal of Global Optimization. 2022. V.83. N3. P.445-456. DOI: 10.1007/s10898-021-01097-w WOS Scopus РИНЦ OpenAlex
Даты:
| Поступила в редакцию: | 15 янв. 2020 г. |
| Принята к публикации: | 17 сент. 2021 г. |
| Опубликована online: | 13 окт. 2021 г. |
| Опубликована в печати: | 5 июл. 2022 г. |
Идентификаторы БД:
| Web of science: | WOS:000706608000002 |
| Scopus: | 2-s2.0-85117012596 |
| РИНЦ: | 47514546 |
| OpenAlex: | W3205093017 |