MISC

2011年

5B3 APPROXIMATING CYCLIC ROUTING PROBLEMS OF GRASP-AND-DELIVERY ROBOTS IN PRODUCTION OF PRINTED CIRCUIT BOARDS(Technical session 5B: Routing problems) :

Proceedings of International Symposium on Scheduling
  • KARUNO Yoshiyuki
  • ,
  • NAGAMOCHI Hiroshi
  • ,
  • SHURBEVSKI Aleksandar

2011
開始ページ
247
終了ページ
252
記述言語
英語
掲載種別
出版者・発行元
日本機械学会

In this paper, we consider a routing problem of a single grasp-and-delivery robot with unit capacity, which is working at an assembly line of printed circuit boards. The grasp-and-delivery robot arranges n identical pins from their current configuration to the next required configuration by transferring the pins one by one. A cycle of the assembly contains such a transition from a configuration to an another configuration. The n pins support a printed circuit board from underneath to prevent it from overbending, while an automated manipulator embeds a number of electronic parts onto the printed circuit board from above. Let m be the number of printed circuit boards to be processed. Given an initial configuration of the pins and a permutable set of m required configurations, the routing problem asks to find a processing order of the m printed circuit boards (i.e., a sequence of the m configurations) and a transfer route of the grasp-and-delivery robot which minimize the route length over all m cycles. In this paper, we first design a polynomial time approximation algorithm with factor four to the cyclic routing problem with a non-permutable set of configurations (i.e., with a fixed processing order of printed circuit boards). Then, by employing its procedure, we show that the cyclic routing problem with a permutable set of configurations admits a polynomial time approximation algorithm with factor eight.

リンク情報
CiNii Articles
http://ci.nii.ac.jp/naid/110009663478
CiNii Books
http://ci.nii.ac.jp/ncid/AA11901544
URL
http://dl.ndl.go.jp/info:ndljp/pid/10355878
ID情報
  • CiNii Articles ID : 110009663478
  • CiNii Books ID : AA11901544

エクスポート
BibTeX RIS