A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation
Volume 5 Issue 1
Jan.  2018

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 6.171, Top 11% (SCI Q1)
    CiteScore: 11.2, Top 5% (Q1)
    Google Scholar h5-index: 51, TOP 8
Turn off MathJax
Article Contents
Jun Li, Xianghu Meng and Xing Dai, "Collision-free Scheduling of Multi-bridge Machining Systems: A Colored Traveling Salesman Problem-based Approach," IEEE/CAA J. Autom. Sinica, vol. 5, no. 1, pp. 139-147, Jan. 2018. doi: 10.1109/JAS.2017.7510415
Citation: Jun Li, Xianghu Meng and Xing Dai, "Collision-free Scheduling of Multi-bridge Machining Systems: A Colored Traveling Salesman Problem-based Approach," IEEE/CAA J. Autom. Sinica, vol. 5, no. 1, pp. 139-147, Jan. 2018. doi: 10.1109/JAS.2017.7510415

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

doi: 10.1109/JAS.2017.7510415

the National Natural Science Foundation of China 61773115

the National Natural Science Foundation of China 61374069

the National Natural Science Foundation of China 61374148

the Natural Science Foundation of Jiangsu Province BK20161427

More Information
  • 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.


  • loading
  • [1]
    Z. Du, "A coordination and optimization method for cutting processes of multi-bridge waterjet systems, " M. S. thesis, School of Automation, Southeast University, China, 2011. http://d.wanfangdata.com.cn/Thesis/Y2022612
    J. Li, Q. Sun, and X. Dai, "A coordination and optimization method for multi-bridge waterjet cutting processes, " in Proc. 42nd International Conference on Computers & Industrial Engineering, Cape Town, South Africa, pp. 9575-9580, 2012. https://www.researchgate.net/publication/293094787_A_coordination_and_optimization_method_for_multi-bridge_waterjet_cutting_processes
    X. Meng, J. Li, M. C. Zhou, and X. Dai, "Improved population-based incremental learning algorithm for scheduling multi-bridge waterjet cutting processes, " in Proc. IEEE 11th International Conference on Networking, Sensing and Control (ICNSC), Miami, FL, USA, pp. 496-500, 2014. http://ieeexplore.ieee.org/document/6819676/
    Q. Sun, "A colored traveling salesman problem and its application, " M. S. thesis, School of Automation, Southeast University, China, 2013. http://d.wanfangdata.com.cn/Thesis/Y2438209
    J. Li, Q. Sun, M. C. Zhou, and X. Dai, "A new multiple traveling salesman problem and its genetic algorithm-based solution, " in Proc. 2013 IEEE International Conference on Systems, Man, and Cybernetics (SMC), Manchester, UK, pp. 627-632, 2013. http://dl.acm.org/citation.cfm?id=2572478
    J. Li, Q. Sun, M. C. Zhou, X. Yu, and X. Dai, "Colored traveling salesman problem and solution, " in Proc. 19th World Congress of the International Federation of Automatic Control, Cape Town, South Africa August 24-29, vol. 47, no. 3, pp. 9575-9580, 2014. http://www.sciencedirect.com/science/article/pii/S1474667016431289
    J. Li, M. C. Zhou, Q. Sun, X. Dai, and X. Yu, "Colored traveling salesman problem. IEEE Transactions on Cybernetics, " vol. 45, no. 11, pp. 2390-2401, 2015. http://ieeexplore.ieee.org/document/6975134/
    J. Li, X. Meng, M. C. Zhou, and X. Dai, "A two-stage approach to path planning and collision avoidance of multibridge machining systems, " IEEE Transactions on Systems, Man and Cybernetics: Systems, DOI: 10.1109/TSMC.2016.2531648.
    T. Bektas, "The multiple traveling salesman problem: an overview of formulations and solution procedures" Omega, vol. 34, no. 3, pp. 209-219, 2006. http://www.sciencedirect.com/science/article/pii/S0305048304001550
    D. L. Applegate, R. E. Bixby, V. Chvátal, and W. J. Cook, "The traveling salesman problem, " Princeton:Princeton University Press, 2006.
    N. Chakraborty, S. Akella, and J. T. Wen, "Coverage of a planar point set with multiple robots subject to geometric constraints, " IEEE Transactions on Automation Science and Engineering, vol. 7, no. 1, pp. 111-122, 2010. http://ieeexplore.ieee.org/document/4840418/
    E. K. Xidias, P. Th. Zacharia, and N. A. Aspragathos, "Time-optimal task scheduling for two robotic manipulators operating in a three-dimensional environment, " Proceedings of the Institution of Mechanical Engineers. Part Ⅰ: Journal of Systems and Control Engineering, vol. 224, no. 7, pp. 845-855, 2010. doi: 10.1243/09596518JSCE949
    A. G. Gonzalez-Rodriguez and A. Gonzalez-Rodriguez, "Collision-free motion planning and scheduling, " Robotics and Computer-Integrated Manufacturing, vol. 27, no. 3, pp. 657-665. http://www.sciencedirect.com/science/article/pii/S0736584510001766
    R. Kala, "Multi-robot path planning using co-evolutionary genetic programming, " Expert Systems with Applications vol. 39, no. 3, pp. 3817-3831, 2012. http://www.sciencedirect.com/science/article/pii/S0957417411014138
    H. Qu, K. Xing, and T. Alexander, "An improved genetic algorithm with co-evolutionary strategy for global path planning of multiple mobile robots, " Neurocomputing vol. 120, pp. 509-517, 2013. http://www.sciencedirect.com/science/article/pii/S0925231213005195
    H. J. Yoon, "Scheduling for deadlock avoidance operation in robotic manufacturing cells, " Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, vol. 224, no. 2, pp. 329-340, 2010. doi: 10.1243/09544054JEM1422
    T. S. Dahl, M. Matarić, and G. S. Sukhatme, "Multi-robot task allocation through vacancy chain scheduling, " Robotics and Autonomous Systems, vol. 57, no. 6-7, pp. 674-687, 2009. http://www.sciencedirect.com/science/article/pii/S0921889008002078
    G. A. Korsah, B. Kannan, B. Browning, A. Stentz, and M. B. Dias, "xBots: an approach to generating and executing optimal multi-robot plans with cross-schedule dependencies, " in Proc. IEEE International Conference on Robotics and Automation (ICRA 2012), St. Paul, MN, USA, pp. 115-122, 2012. http://ieeexplore.ieee.org/document/6225234/
    T. Zheng and J. Li, "Multi-robot task allocation and scheduling based on fish swarm algorithm, " in Proc. 8th World Congress on Intelligent Control and Automation (WCICA 2010), Jinan, China, pp. 6681-6685, 2010. http://ieeexplore.ieee.org/document/5554156/
    Y. Gan, X. Dai, and J. Li, "Cooperative path planning and constraints analysis for master-slave industrial robots, " International Journal of Advanced Robotic Systems, vol. 9, no. 88, pp. 1-13, 2012. 10.5772/51374
    G. Gutin, A. Yeo, and A. Zverovich, "Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP, " Discrete Applied Mathematics, vol. 117, no. 1-3, pp. 81-86, 2002. http://www.sciencedirect.com/science/article/pii/S0166218X01001950
    D. S. Johnson and L. A. McGeoch, "The traveling salesman problem: a case study in local optimization, " Local Search in Combinatorial Optimization, E. H. L. Aarts and J. K. Lenstra (eds. ), John Wiley and Sons, London, pp. 215-310, 1997. https://www.mendeley.com/research-papers/traveling-salesman-problem-case-study-local-optimization/


    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Figures(7)  / Tables(3)

    Article Metrics

    Article views (1187) PDF downloads(68) Cited by()


    DownLoad:  Full-Size Img  PowerPoint