Volume 19, No 2, 2012, P. 55-75
A. V. Kononov
On a two-machine routing open shop problem on a two-node network
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
Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia