Travelling Production Line Problem on Digraphs with Parameterized Triangle Inequality
Tongquan Zhang, Ying Yin · 2010
For a lot of producers have never saved materials of their products for aims of economizing their time and saving costs, but when they have received orders, they will start from their locations with their production lines travel first to the material supply regions, second to the ordered regions, and product their products on the travelling time. Here, we consider their minimum travelling time routing problem, we define the problem as asymmetric travelling production line problem, analyze its NP-Completeness, and design a (4γ2+2γ3-4γ4)/(1-γ2)-approximation algorithm for it on networks with parameterized γ-triangle inequality, γ ∈ (1/2, 1).