An exact solution with an improved running time for the routing flow shop problem with two machines

Ilya Chernykh (), Alexander Kononov () and Sergey Sevastyanov ()
Additional contact information
Ilya Chernykh: Sobolev Institute of Mathematics
Alexander Kononov: Sobolev Institute of Mathematics
Sergey Sevastyanov: Sobolev Institute of Mathematics

Journal of Scheduling, 2024, vol. 27, issue 4, No 2, 329-340

Abstract: Abstract We present an improved analysis of the running time of a dynamic program for the routing flow shop problem with two machines on an asymmetric network. Our analysis is based on structural properties of optimal schedules and significantly improves the bound on the running time of the algorithm obtained in the conference version of our paper (Chernykh, Kononov, and Sevastyanov, in: Kononov, A. et al. (eds) Mathematical optimization theory and operations research. MOTOR 2020. Lecture notes in computer science, Springer, Switzerland, 2020). To the best of our knowledge, our polynomial-time algorithm (under the assumption that the number of network nodes is bounded by any constant) is the first positive result on the complexity of the routing flow shop problem with an arbitrary structure of the transportation network, even in the case of a symmetric network. This result contrasts with the complexity of the two-machine routing open shop problem, which is NP-hard even on the two-node network.

Keywords: Scheduling; Routing flow shop; Polynomially solvable case; Dynamic programming (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-023-00784-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:27:y:2024:i:4:d:10.1007_s10951-023-00784-8

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-023-00784-8

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().