Geodesic
On a two-machine routing open shop problem on a~two-node network
Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 2, pp. 54-74.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider the two-machine routing open shop problem on a two-node network. The problem is ordinary NP-hard. We present an exact pseudo-polynomial algorithm and a fully polynomial time approximation scheme for the considered problem. We also point out new polynomially solvable subproblems. Ill. 6, tab. 1, bibliogr. 8.
Keywords: open shop, routing, fully-polynomial time approximation scheme. 
@article{DA_2012_19_2_a3,
     author = {A. V. Kononov},
     title = {On a two-machine routing open shop problem on a~two-node network},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {54--74},
     publisher = {mathdoc},
     volume = {19},
     number = {2},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2012_19_2_a3/}
}
TY  - JOUR
AU  - A. V. Kononov
TI  - On a two-machine routing open shop problem on a~two-node network
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2012
SP  - 54
EP  - 74
VL  - 19
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2012_19_2_a3/
LA  - ru
ID  - DA_2012_19_2_a3
ER  - 
%0 Journal Article
%A A. V. Kononov
%T On a two-machine routing open shop problem on a~two-node network
%J Diskretnyj analiz i issledovanie operacij
%D 2012
%P 54-74
%V 19
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2012_19_2_a3/
%G ru
%F DA_2012_19_2_a3
A. V. Kononov. On a two-machine routing open shop problem on a~two-node network. Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 2, pp. 54-74. http://geodesic.mathdoc.fr/item/DA_2012_19_2_a3/

[1] Tanaev V. S., Sotskov Yu. N., Strusevich V. A., Teoriya raspisanii. Mnogostadiinye sistemy, Nauka, M., 1989, 329 pp. | MR | Zbl

[2] Averbakh I., Berman O., Chernykh I., “A $\frac 65$-approximation algorithm for the two-machine routing open shop problem on a 2-node network”, Eur. J. Oper. Res., 166:1 (2005), 3–24 | DOI | MR | Zbl

[3] Averbakh I., Berman O., Chernykh I., “The routing open-shop problem on a network: complexity and approximation”, Eur. J. Oper. Res., 173:2 (2006), 521–539 | DOI | MR

[4] Chernykh I., Dryuck N., Kononov A., Sevastyanov S., “The routing open shop problem: new approximation algorithms”, Approximation and Online algorithms, 7th Int. Workshop WAOA 2009 (Copenhagen, Denmark, September 10–11, 2009), Revised Papers, Lect. Notes Comp. Sci., 5893, Springer-Verl., Heidelberg, 2010, 75–85 | DOI | MR | Zbl

[5] Gonzalez T., Sahni S., “Open shop scheduling to minimize finish time”, J. ACM, 23 (1976), 665–679 | DOI | MR | Zbl

[6] Ibarra O., Kim C. E., “Fast approximation algorithms for the knapsack and sum of subset problems”, J. ACM, 22 (1975), 463–468 | DOI | MR | Zbl

[7] Johnson S. M., “Optimal two- and three stage production schedules with set-up times included”, Naval Res. Logistic Quaterly, 1 (1954), 61–68 | DOI

[8] Schuurman P., Woeginger G., Approximation schemes – a tutorial http://www.win.tue.nl/~gwoegi/papers/ptas.pdf