The open shop problem with routing at a two-node network and allowed preemption |
| |
Authors: | A V Pyatkin I D Chernykh |
| |
Institution: | 1.Sobolev Institute of Mathematics,Novosibirsk,Russia |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|