首页 | 官方网站   微博 | 高级检索  
     


Complexity of One-Cycle Robotic Flow-Shops
Authors:N Brauner  G Finke  W Kubiak
Affiliation:(1) Université Pierre Mendès France, IUT2, Dep. GEA, France;(2) Laboratoire Leibniz-IMAG, France;(3) Faculty of Business Administration, Memorial University of Newfoundland, St. John's, Canada
Abstract:We study the computational complexity of finding the shortest route the robot should take when moving parts between machines in a flow-shop. Though this complexity has already been addressed in the literature, the existing attempts made crucial assumptions which were not part of the original problem. Therefore, they cannot be deemed satisfactory. We drop these assumptions in this paper and prove that the problem is NP-hard in the strong sense when the travel times between the machines of the cell are symmetric and satisfy the triangle inequality. We also impose no restrictions on the times of robot arrival at and departure from machines as it is the case in the related, but different, hoist scheduling problem. Our results hold for processing times equal on all machines in the cell. However, the equidistant case for equal processing times can be solved in O(1) time.
Keywords:robotic cells  TSP problem
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司    京ICP备09084417号-23

京公网安备 11010802026262号