Volume 19, No 3, 2012, P. 65-78
A. V. Pyatkin, I. D. Chernykh
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.
Keywords: routing open shop, preemption, NP-completeness.
Pyatkin Artem Valer’evich 1
Chernykh Il’ia Dmitrievich 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
e-mail: firstname.lastname@example.org, email@example.com