Two-machine routing open shop on a tree: instance reduction and efficiently solvable subclass

References

• I. Averbakh and O. Berman, Routing two-machine flowshop problems on networks with special structure, Transport. Sci. 30 (1996), pp. 303–314. doi: 10.1287/trsc.30.4.303
   Web of Science ®Google Scholar
• I. Averbakh and O. Berman, A simple heuristic for m-machine flow-shop and its applications in routing-scheduling problems, Oper. Res. 47 (1999), pp. 165–170. doi: 10.1287/opre.47.1.165
   Web of Science ®Google Scholar
• I. Averbakh, O. Berman, and I. Chernykh, A 6/5-approximation algorithm for the two-machine routing open-shop problem on a two-node network, Eur. J. Oper. Res. 166 (2005), pp. 3–24. doi: 10.1016/j.ejor.2003.06.050
   Web of Science ®Google Scholar
• I. Averbakh, O. Berman, and I. Chernykh, The routing open-shop problem on a network: Complexity and approximation, Eur. J. Oper. Res. 173 (2006), pp. 531–539. doi: 10.1016/j.ejor.2005.01.034
   Web of Science ®Google Scholar
• P. Brucker, S. Knust, T. Edwin Cheng and N. Shakhlevich, Complexity results for flow-Shop and open-shop scheduling problems with transportation delays, Ann. Oper. Res. 129 (2004), pp. 81–106. doi: 10.1023/B:ANOR.0000030683.64615.c8
   Web of Science ®Google Scholar
• I. Chernykh, Routing open shop with unrelated travel times, in Discrete Optimization and Operations Research – 9th International Conference, DOOR 2016, Vladivostok, Russia, September 19–23, 2016, Proceedings. 2016, pp. 272–283.
   Google Scholar
• I. Chernykh and E. Lgotina, The 2-machine routing open shop on a triangular transportation network, in Discrete Optimization and Operations Research – 9th International Conference, DOOR 2016, Vladivostok, Russia, September 19–23, 2016, Proceedings. 2016, pp. 284–297.
   Google Scholar
• I. Chernykh and A. Pyatkin, Refinement of the optima localization for the two-machine routing open shop, in Proceedings of the 8th International Conference on Optimization and Applications (OPTIMA17). Vol. 1987. CEUR Workshop Proceedings (1987). 2017, pp. 131–138.
   Google Scholar
• S. Chou and S. Lin, Museum visitor routing problem with the ballancing of concurrent visitors, Complex Syst. Concurr. Eng. 6 (2007), pp. 345–353. doi: 10.1007/978-1-84628-976-7_39
   Google Scholar
• D. de Werra, Graph-theoretical models for preemptive scheduling, in R. Slowinski and J. Weglarz, eds., Advances in Project Scheduling, Elsevier, Amsterdam, 1989, pp. 171–185. doi: 10.1016/B978-0-444-87358-3.50012-2
   Google Scholar
• M. Golovachev and A.V. Pyatkin, Routing open shop with two nodes, unit processing times and equal number of jobs and machines, in Mathematical Optimization Theory and Operations Research, MOTOR 2019, Ekaterinburg, Russia, July 8–12, 2019, Proceedings, M. Khachay, Y. Kochetov, and P. Pardalos, eds., Lecture Notes in Computer Science Vol. 11548. 2019, pp. 264–276.
   Google Scholar
• T.F. Gonzalez and S. Sahni, Open shop scheduling to minimize finish time, J. ACM 23 (1976), pp. 665–679. doi: 10.1145/321978.321985
   Web of Science ®Google Scholar
• U. Kleinau, Two-machine shop scheduling problems with batch processing, Math. Comput. Model. 17 (1993), pp. 55–66. doi: 10.1016/0895-7177(93)90196-6
   Google Scholar
• A. Kononov, On the routing open shop problem with two machines on a two-vertex network, J. Appl. Ind. Math. 6 (2012), pp. 318–331. doi: 10.1134/S1990478912030064
   Google Scholar
• A. Kononov, O(log m)-approximation for the routing open shop problem, RAIRO – Oper. Res. 49 (2015), pp. 383–391. doi: 10.1051/ro/2014051
   Web of Science ®Google Scholar
• A. Kononov, S. Sevastianov, and I. Tchernykh, When difference in machine loads leads to efficient scheduling in open shops, Ann. Oper. Res. 92 (1999), pp. 211–239. doi: 10.1023/A:1018986731638
   Web of Science ®Google Scholar
• E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, and G.B. Shmoys, Sequencing and Scheduling: Algorithms and Complexity. Logistics of Production and Inventory, Elsevier, Amsterdam, 1993.
   Google Scholar
• I.N. Lushchakova, A.J. Soper, and V.A. Strusevich, Transporting jobs through a two-machine open shop, Naval Res. Logist. 56 (2009), pp. 1–18. doi: 10.1002/nav.20323
   Web of Science ®Google Scholar
• M. Pinedo and L. Schrage, Stochastic shop scheduling: A survey, in Deterministic and stochastic scheduling, M.A.H. Dempster, J.K. Lenstra, and A.H.G. Rinnooy Kan, eds., NATO Advanced Study Institute Series Vol. 84, Springer, Dordrecht, 1982, pp. 181–196.
   Google Scholar
• V. Strusevich, A heuristic for the two-machine open-shop scheduling problem with transportation times, Discrete Appl. Math. 93 (1999), pp. 287–304. doi: 10.1016/S0166-218X(99)00115-8
   Web of Science ®Google Scholar
• R. van Bevern and A.V. Pyatkin, Completing partial schedules for open shop with unit processing times and routing, in Proceedings of the 11th International Computer Science Symposium in Russia (CSR16). Lecture Notes in Computer Science, Vol. 9691. 2016, pp. 73–87.
   Google Scholar
• R. van Bevern, A.V. Pyatkin, and S.V. Sevastyanov, 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 (2019), pp. 42–84.
   Google Scholar
• D.P. Williamson, L.A. Hall, J.A. Hoogeveen, C.A.J. Hurkens, J.K. Lenstra, S.V. Sevast'janov, and D.B. Shmoys, Short shop schedules, Oper. Res. 45 (1997), pp. 288–294. doi: 10.1287/opre.45.2.288
   Web of Science ®Google Scholar
• V.F. Yu, S. Lin, and S. Chou, The museum visitor routing problem, Appl. Math. Comput. 216 (2010), pp. 719–729.
   Web of Science ®Google Scholar