Preemptive routing open shop on a link

Preemptive routing open shop problem is a generalization of two classic discrete optimization problems: NP-hard metric TSP and polynomially solvable open shop scheduling problem. We show that the problem with two machines is polynomially solvable while in case when the number of machines is a part of an input the problem is strongly NP-hard. Ill. 6, bibliogr. 6.