Collision-free Scheduling of Multi-bridge Machining Systems: A Colored Traveling Salesman Problem-based Approach

被引:3
作者
Jun Li [1 ,2 ]
Xianghu Meng [2 ]
Xing Dai [2 ]
机构
[1] IEEE
[2] Ministry of Education Key Laboratory of Measurement and Control, School of Computer Science and Engineering, Southeast University
基金
中国国家自然科学基金;
关键词
Collision resolution; greedy algorithm; modeling; multiple traveling salesman problem; scheduling;
D O I
暂无
中图分类号
TH16 [机械制造工艺];
学科分类号
0802 ;
摘要
Multi-bridge machining systems(MBMS) have gained wide applications in industry due to their high production capacity and efficiency. They contain multiple bridge machines working in parallel within their partially overlapping workspaces.Their scheduling problems can be abstracted into a serial-colored travelling salesman problem in which each salesman has some exclusive cities and some cities shared with its neighbor(s). To solve it, we develop a greedy algorithm that selects a neighboring city satisfying proximity. The algorithm allows a salesman to select randomly its shared cities and runs accordingly many times. It can thus be used to solve job scheduling problems for MBMS. Subsequently, a collision-free scheduling method is proposed to address both job scheduling and collision resolution issues of MBMS. It is an extension of the greedy algorithm by introducing time window constraints and a collision resolution mechanism. Thus, the augmented greedy algorithm can try its best to select stepwise a job for an individual machine such that no time overlaps exist between it and the job sequence of the neighboring machine dealt in the corresponding overlapping workspace; and remove such a time overlap only when it is inevitable. Finally, we conduct a case study of a large triplebridge waterjet cutting system by applying the proposed method.
引用
收藏
页码:139 / 147
页数:9
相关论文
共 8 条
  • [1] An improved genetic algorithm with co-evolutionary strategy for global path planning of multiple mobile robots[J] . Hong Qu,Ke Xing,Takacs Alexander. Neurocomputing . 2013
  • [2] Multi-robot path planning using co-evolutionary genetic programming[J] . Rahul Kala. Expert Systems With Applications . 2011 (3)
  • [3] Collision-free motion planning and scheduling[J] . A.G. Gonzalez-Rodriguez,A. Gonzalez-Rodriguez. Robotics and Computer Integrated Manufacturing . 2010 (3)
  • [4] Scheduling for deadlock avoidance operation in robotic manufacturing cells
    Yoon, H. J.
    [J]. PROCEEDINGS OF THE INSTITUTION OF MECHANICAL ENGINEERS PART B-JOURNAL OF ENGINEERING MANUFACTURE, 2010, 224 (B2) : 329 - 340
  • [5] Multi-robot task allocation through vacancy chain scheduling[J] . Robotics and Autonomous Systems . 2008 (6)
  • [6] The multiple traveling salesman problem: an overview of formulations and solution procedures[J] . Tolga Bektas. Omega . 2004 (3)
  • [7] Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP[J] . Gregory Gutin,Anders Yeo,Alexey Zverovich. Discrete Applied Mathematics . 2002 (1)
  • [8] x Bots:an approach to generating and executing optimal multi-robot plans with cross-schedule dependencies .2 G.A.Korsah,B.Kannan,B.Browning,A.Stentz,M.B.Dias. Proc.IEEE International Conference on Robotics and Automation(ICRA 2012) . 2012