Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2020, 14:3, 470-479
Volume 27, No 3, 2020, P. 53-70
UDC 519.854.2
M. O. Golovachev and A. V. Pyatkin
On a routing Open Shop Problem on two nodes with unit processing times
Abstract:
The routing Open Shop Problem deals with $n$ jobs located in the nodes of an edge-weighted graph $G = (V, E)$ and $m$ machines that are initially in a special node called depot. The machines must process all jobs in arbitrary order so that each machine processes at most one job at any one time and each job is processed by at most one machine at any one time. The goal is to minimize the makespan; i. e., the time when the last machine returns to the depot. This problem is known to be NP-hard even for the two machines and the graph containing only two nodes. In this article we consider the particular case of the problem with a 2-node graph, unit processing time of each job, and unit travel time between every two nodes. The conjecture is made that the problem is polynomially solvable in this case; i. e., 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 new bounds on the makespan in the case of $m = n$ depending on the loads distribution.
Tab. 2, bibliogr. 15.
Keywords: routing Open Shop Problem, unit processing time, complexity, scheduling, polynomial time, makespan bound.
DOI: 10.33048/daio.2020.27.681
Mikhail O. Golovachev 1
Artem V. Pyatkin 2,1
1. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
2. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: mik-golovachev2@mail.ru, artem@math.nsc.ru
Received January 10, 2020
Revised April 20, 2020
Accepted May 25, 2020
References
[1] T. Gonzalez and S. Sahni, Open shop scheduling to minimize finish time, J. ACM 23 (4), 665–679 (1976).[2] 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, 288–294 (1997).
[3] R. Cole, K. Ost, and S. Schirra, Edge-coloring bipartite multigraphs in $O$($E$ log $D$) time, Combinatorica 21 (1), 5–12 (2001).
[4] I. Averbakh, O. Berman, and I. Chernykh, A 6/5-approximation algorithm for the two-machine routing open shop problem on a 2-node network, Eur. J. Oper. Res. 166 (1), 3–24 (2005).
[5] I. Averbakh, O. Berman, and I. Chernykh, The routing open-shop problem on a network: Complexity and approximation, Eur. J. Oper. Res. 173 (2), 521–539 (2006).
[6] A. V. Kononov, On the routing open shop problem with two machines on a two-vertex network, Diskretn. Analiz Issled. Oper. 19 (2), 54–74 (2012) [Russian] [J. Appl. Ind. Math. 6 (3), 318–331 (2012)].
[7] A. V. Pyatkin and I. D. Chernykh, The open shop problem with routing at a two-node network and allowed preemption, Diskretn. Analiz Issled. Oper. 19 (3), 65–78 (2012) [Russian] [J. Appl. Ind. Math. 6 (3), 346–354 (2012)].
[8] R. van Bevern and A. V. Pyatkin, Completing partial schedules for open shop with unit processing times and routing, in Computer Science – Theory and Applications (Proc. 11th Int. Computer Science Symp. in Russia, St. Petersburg, Russia, June 9–13, 2016) (Springer, Cham, 2016), pp. 73–87 (Lect. Notes Comput. Sci., Vol. 9691).
[9] 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, Sib. Elektron. Mat. Izv. 16, 42–84 (2019).
[10] P. Brucker, S. Knust, T. C. E. Cheng, and N. V. Shakhlevich, Complexity results for flow-shop and open-shop scheduling problems with transportation delays, Ann. Oper. Res. 129, 81–106 (2004).
[11] I. Lushchakova, A. Soper, and V. Strusevich, Transporting jobs through a two-machine open shop, Naval Res. Logistics 56, 1–18 (2009).
[12] V. Strusevich, A heuristic for the two-machine open-shop scheduling problem with transportation times, Discrete Appl. Math. 93 (2), 287–304 (1999).
[13] M. O. 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 (Proc. 18th Int. Conf., Yekaterinburg, Russia, July 8–12, 2019) (Springer, Cham, 2019), pp. 264–276 (Lect. Notes Comput. Sci., Vol. 11548).
[14] H. Bräsel, D. Kluge, and F. Werner, A polynomial algorithm for the [$n$/$m$/$0$, $t_ij = 1$,tree$/$C_max$] open shop problem, Eur. J. Oper. Res. 72 (1), 125–134 (1994).
[15] R. Diestel, Graph theory (Springer, Heidelberg, 2016).
