旅行生产线问题  

Problem Concerning the Most Economical Production Line

作　　者：陈克林[1] 

机构地区：[1]云南民族大学数学与计算机科学学院,云南昆明650031

出　　处：《云南民族大学学报（自然科学版）》2011年第6期473-475,共3页Journal of Yunnan Minzu University:Natural Sciences Edition

摘　　要：考虑生产商的最经济的旅行路线问题,把这一问题定义为旅行生产线问题并分析了它的NP-完全性,最后为满足三角不等式的对称网络上的旅行生产线问题设计了一个8-近似算法.In order to economize the time and costs of the producers, the paper defines and discusses the problem of the most economical production line and analyze its NP - completeness and designs a 8 - approximation algorithm for it on the symmetric networks which can satisfy triangle inequality.

关 键 词：旅行生产线问题 近似算法 NP-完全性 

分 类 号：O15[理学—数学]