The open shop problem with routing at a two-node network and allowed preemption

摘要

The open shop problem with routing and allowed preemption is a generalization of the two classical discrete optimization problems: the NP-hard metrical traveling salesman problem and the polynomially solvable scheduling problem, i. e., the open shop with allowed preemption. In the paper, a partial case of this problem is considered when the transportation network consists of two nodes. It is proved that the problem with two machines is polynomially solvable, while the problem is NP-hard in the strong sense in the case of not fixed number of machines.