{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T02:11:00Z","timestamp":1740103860855,"version":"3.37.3"},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,4,30]],"date-time":"2023-04-30T00:00:00Z","timestamp":1682812800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,4,30]],"date-time":"2023-04-30T00:00:00Z","timestamp":1682812800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100002261","name":"sps","doi-asserted-by":"publisher","award":["20-07-00458","20-07-00458","20-07-00458"],"award-info":[{"award-number":["20-07-00458","20-07-00458","20-07-00458"]}],"id":[{"id":"10.13039\/501100002261","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2024,8]]},"DOI":"10.1007\/s10951-023-00784-8","type":"journal-article","created":{"date-parts":[[2023,4,30]],"date-time":"2023-04-30T13:01:57Z","timestamp":1682859717000},"page":"329-340","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An exact solution with an improved running time for the routing flow shop problem with two machines"],"prefix":"10.1007","volume":"27","author":[{"given":"Ilya","family":"Chernykh","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6144-0251","authenticated-orcid":false,"given":"Alexander","family":"Kononov","sequence":"additional","affiliation":[]},{"given":"Sergey","family":"Sevastyanov","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,4,30]]},"reference":[{"issue":"4","key":"784_CR1","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1287\/trsc.30.4.303","volume":"30","author":"I Averbakh","year":"1996","unstructured":"Averbakh, I., & Berman, O. (1996). Routing two-machine flowshop problems on networks with special structure. Transportation Science, 30(4), 303\u2013314. https:\/\/doi.org\/10.1287\/trsc.30.4.303","journal-title":"Transportation Science"},{"issue":"1","key":"784_CR2","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1287\/opre.47.1.165","volume":"47","author":"I Averbakh","year":"1999","unstructured":"Averbakh, I., & Berman, O. (1999). A simple heuristic for $$m$$-machine flow-shop and its applications in routing-scheduling problems. Operations Research, 47(1), 165\u2013170. https:\/\/doi.org\/10.1287\/opre.47.1.165","journal-title":"Operations Research"},{"issue":"2","key":"784_CR3","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1016\/j.ejor.2005.01.034","volume":"173","author":"I Averbakh","year":"2006","unstructured":"Averbakh, I., Berman, O., & Chernykh, I. (2006). The routing open-shop problem on a network: complexity and approximation. European Journal of Operational Research, 173(2), 531\u2013539. https:\/\/doi.org\/10.1016\/j.ejor.2005.01.034","journal-title":"European Journal of Operational Research"},{"key":"784_CR4","doi-asserted-by":"publisher","unstructured":"Chernykh, I., Kononov, A., & Sevastyanov, S. (2020). A polynomial-time algorithm for the routing flow shop problem with two machines: an asymmetric network with a fixed number of nodes. In: Kononov, A. et al. (eds.) Mathematical optimization theory and operations research. MOTOR 2020. Lecture Notes in Computer Science, vol. 12095, pp. 301\u2013312. Springer. https:\/\/doi.org\/10.1007\/978-3-030-49988-4_21","DOI":"10.1007\/978-3-030-49988-4_21"},{"key":"784_CR5","first-page":"37","volume-title":"Optimization Problems and Their Applications (OPTA-2018), Abstracts of the VII International Conference (Omsk, Russia, July 8\u201314, 2018)","author":"I Chernykh","year":"2018","unstructured":"Chernykh, I., Kononov, A., & Sevastyanov, S. (2018). Exact polynomial-time algorithm for the two-machine routing flow shop problem with a restricted transportation network. Optimization Problems and Their Applications (OPTA-2018), Abstracts of the VII International Conference (Omsk, Russia, July 8\u201314, 2018) (pp. 37\u201337). Omsk State University."},{"issue":"2","key":"784_CR6","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1287\/moor.1.2.117","volume":"1","author":"MR Garey","year":"1976","unstructured":"Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1(2), 117\u2013129. https:\/\/doi.org\/10.1287\/moor.1.2.117","journal-title":"Mathematics of Operations Research"},{"key":"784_CR7","unstructured":"Johnson, S.M. (1953). Optimal Two- and Three-stage Production Schedules with Setup Times Included. P-402, the RAND Corporation, Santa Monica, California. https:\/\/www.rand.org\/pubs\/papers\/P402.html"},{"key":"784_CR8","doi-asserted-by":"publisher","unstructured":"J\u00f3zefczyk, J., & Markowski, M. (2014). Heuristic solution algorithm for routing flow shop with buffers and ready times. In: Swiatek, J. et al. (eds.) Advances in intelligent systems and computing, vol. 240, pp. 531\u2013541. Springer. https:\/\/doi.org\/10.1007\/978-3-319-01857-7_52","DOI":"10.1007\/978-3-319-01857-7_52"},{"key":"784_CR9","doi-asserted-by":"publisher","unstructured":"Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., & Shmoys, D.B. (1993). Chapter 9. Sequencing and scheduling: Algorithms and complexity. In: Logistics of production and inventory. Handbooks in operations research and management science, vol. 4, pp. 445\u2013522. Elsevier. https:\/\/doi.org\/10.1016\/S0927-0507(05)80189-6","DOI":"10.1016\/S0927-0507(05)80189-6"},{"key":"784_CR10","doi-asserted-by":"publisher","unstructured":"Yu, W., & Zhang, G. (2011). Improved approximation algorithms for routing shop scheduling. In: Asano, T. et al. (eds.) Algorithms and computation. ISAAC 2011. Lecture notes in computer science, vol. 7074, pp. 30\u201339. Springer. https:\/\/doi.org\/10.1007\/978-3-642-25591-5_5","DOI":"10.1007\/978-3-642-25591-5_5"},{"issue":"1","key":"784_CR11","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1016\/j.ejor.2011.02.028","volume":"213","author":"W Yu","year":"2011","unstructured":"Yu, W., Liu, Z., Wang, L., & Fan, T. (2011). Routing open shop and flow shop scheduling problems. European Journal of Operational Research, 213(1), 24\u201336. https:\/\/doi.org\/10.1016\/j.ejor.2011.02.028","journal-title":"European Journal of Operational Research"},{"issue":"3","key":"784_CR12","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1016\/j.amc.2010.01.066","volume":"216","author":"VF Yu","year":"2010","unstructured":"Yu, V. F., Lin, S., & Chou, S. (2010). The museum visitor routing problem. Applied Mathematics and Computation, 216(3), 719\u2013729. https:\/\/doi.org\/10.1016\/j.amc.2010.01.066","journal-title":"Applied Mathematics and Computation"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-023-00784-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-023-00784-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-023-00784-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,9]],"date-time":"2024-08-09T13:35:17Z","timestamp":1723210517000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-023-00784-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,30]]},"references-count":12,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["784"],"URL":"https:\/\/doi.org\/10.1007\/s10951-023-00784-8","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"type":"print","value":"1094-6136"},{"type":"electronic","value":"1099-1425"}],"subject":[],"published":{"date-parts":[[2023,4,30]]},"assertion":[{"value":"5 April 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 April 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Preliminary versions of this paper appeared in the proceedings of the International conference MOTOR-2020 Chernykh et al. () and on a pre-print server which can be accessed at . It should be noted that the main result of the current paper (Theorem 3) is new and improves the result presented in previous versions in the part of its efficiency. (Their comparison is discussed in Conclusion.) Additionally, we have significantly improved the presentation of the algorithm and of the proofs of all three theorems.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}