Volume 19, No 2, 2012, P. 55-75

UDC 519.95
A. V. Kononov
On a two-machine routing open shop problem on a two-node network

Abstract:
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.

Kononov Alexandr Veniaminovich ^1,2
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: alvenko@math.nsc.ru