A. V. Kononov, “On a two-machine routing open shop problem on a two-node network”, Diskretn. Anal. Issled. Oper., 2012, Volume 19, Issue 2,Pages <nobr>54

This article is cited in 15 papers

On a two-machine routing open shop problem on a two-node network

A. V. Kononov^ab

^a S. L. Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Russia
^b Novosibirsk State University, Novosibirsk, Russia

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.

UDC: 519.2+621.391

Received: 09.06.2011
Revised: 24.11.2011