论文标题
两台机器的路由流店问题的多项式时间算法：一个不对称网络，具有固定数量的节点
A polynomial-time algorithm for the routing flow shop problem with two machines: an asymmetric network with a fixed number of nodes
论文作者
论文摘要
我们考虑了不对称网络上两台机器的路由流店问题。对于此问题，我们讨论最佳时间表的属性，并提出一个多项式时间算法，假设网络的节点数量由常数界定。据我们所知，即使在对称网络的情况下，这是对路由流店问题的复杂性的第一个积极结果。该结果与两机式路由开放式商店问题的复杂性形成鲜明对比，即使在两个节点网络上，该问题也被证明是NP-HARD。
We consider the routing flow shop problem with two machines on an asymmetric network. For this problem we discuss properties of an optimal schedule and present a polynomial time algorithm assuming the number of nodes of the network to be bounded by a constant. To the best of our knowledge, this is the first positive result on the complexity of the routing flow shop problem with an arbitrary structure of the transportation network, even in the case of a symmetric network. This result stands in contrast with the complexity of the two-machine routing open shop problem, which was shown to be NP-hard even on the two-node network.
