Abstract
In the Routing Open Shop problem n jobs are located in the nodes of an edge-weighted graph \(G=(V,E)\) and m machines must process all jobs in such a way that each machine processes only one job at a time and each job is processed by only one machine at a time. The goal is to minimize the makespan, i. e. the time when the last machine comes back to the initial node called a depot (at the beginning all machines are in the depot). This problem is NP-hard even when the graph contains only two nodes. In this paper we consider the case of \(G=K_2\) when all processing times and travel times are unit. We pose the conjecture that the problem is polynomially solvable in this case, i. e. that the makespan depends only on the number of machines and the loads of the nodes and can be calculated in time \(O(\log mn)\). We provide some bounds on the makespan for the case of \(m=n\) depending on the loads distribution.
The research was supported by the program of fundamental scientific researches of the SB RAS, project 0314-2019-0014 and by the Russian Foundation for Basic Research, project 17-01-00170.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Averbakh, I., Berman, O., Chernykh, I.: A 6/5-approximation algorithm for the two-machine routing open shop problem on a 2-node network. Eur. J. Oper. Res. 166, 3–24 (2005). https://doi.org/10.1016/j.ejor.2003.06.050
Averbakh, I., Berman, O., Chernykh, I.: The routing open-shop problem on a network: complexity and approximation. Eur. J. Oper. Res. 173, 531–539 (2006). https://doi.org/10.1016/j.ejor.2005.01.034
van Bevern, R., Pyatkin, A.V.: Completing partial schedules for open shop with unit processing times and routing. In: Kulikov, A.S., Woeginger, G.J. (eds.) CSR 2016. LNCS, vol. 9691, pp. 73–87. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-34171-2_6
van Bevern, R., Pyatkin, A.V., Sevastyanov, S.V.: An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times. Siberian Electron. Math. Rep. 16, 42–84 (2019). https://doi.org/10.33048/semi.2019.16.003
Bräsel, H., Kluge, D., Werner, F.: A polynomial algorithm for the \([n/m/0, t_{ij} =1, tree/cmax]\) open shop problem. Eur. J. Oper. Res. 72, 125–134 (1994). https://doi.org/10.1016/0377-2217(94)90335-2
Brucker, P., Knust, S., Cheng, T.C.E., Shakhlevich, N.V.: Complexity results for flow-shop and open-shop scheduling problems with transportation delays. Ann. Oper. Res. 129, 81–106 (2004). https://doi.org/10.1023/b:anor.0000030683.64615.c8
Cole, R., Ost, K., Schirra, S.: Edge-coloring bipartite multigraphs in \(O(E \log D)\) time. Combinatorica 21, 5–12 (2001). https://doi.org/10.1007/s004930170002
Gonzalez, T., Sahni, S.: Open shop scheduling to minimize finish time. J. ACM 23, 665–679 (1976). https://doi.org/10.1145/321978.321985
Kononov, A.V.: On the routing open shop problem with two machines on a two-vertex network. J. Appl. Ind. Math. 6, 318–331 (2012). https://doi.org/10.1134/s1990478912030064
Leung, J.Y. (ed.): Handbook of Scheduling - Algorithms, Models, and Performance Analysis. Chapman and Hall/CRC (2004). http://www.crcnetbase.com/isbn/978-1-58488-397-5
Lushchakova, I., Soper, A., Strusevich, V.: Transporting jobs through a two-machine open shop. Naval Res. Logist. 56, 1–18 (2009). https://doi.org/10.1002/nav.20323
Pyatkin, A.V., Chernykh, I.D.: The open shop problem with routing at a two-node network and allowed preemption. J. Appl. Indust. Math. 6, 346–354 (2012). https://doi.org/10.1134/s199047891203009x
Strusevich, V.: A heuristic for the two-machine open-shop scheduling problem with transportation times. Discrete Appl. Math. 93(2), 287–304 (1999). https://doi.org/10.1016/S0166-218X(99)00115-8
Williamson, D.P., et al.: Short shop schedules. Oper. Res. 45, 288–294 (1997). https://doi.org/10.1287/opre.45.2.288
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Golovachev, M., Pyatkin, A.V. (2019). Routing Open Shop with Two Nodes, Unit Processing Times and Equal Number of Jobs and Machines. In: Khachay, M., Kochetov, Y., Pardalos, P. (eds) Mathematical Optimization Theory and Operations Research. MOTOR 2019. Lecture Notes in Computer Science(), vol 11548. Springer, Cham. https://doi.org/10.1007/978-3-030-22629-9_19
Download citation
DOI: https://doi.org/10.1007/978-3-030-22629-9_19
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-22628-2
Online ISBN: 978-3-030-22629-9
eBook Packages: Computer ScienceComputer Science (R0)