Volume 19, No 3, 2012, P. 65-78

UDC 519.8
A. V. Pyatkin, I. D. Chernykh
Preemptive routing open shop on a link

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

Keywords: routing open shop, preemption, NP-completeness.

Pyatkin Artem Valer’evich ¹
Chernykh Il’ia Dmitrievich ^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: artem@math.nsc.ru, idchern@math.nsc.ru