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

Jun Li; Xianghu Meng; Xing Dai

doi:10.1109/JAS.2017.7510415

Volume 5 Issue 1

Jan. 2018

IEEE/CAA Journal of Automatica Sinica

JCR Impact Factor: 15.3, Top 1 (SCI Q1)

CiteScore: 23.5, Top 2% (Q1)
Google Scholar h5-index: 77， TOP 5

Turn off MathJax

Article Contents

Article Navigation > IEEE/CAA Journal of Automatica Sinica > 2018 > 5(1): 139-147

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

Citation:

PDF( 6479 KB)

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

doi: 10.1109/JAS.2017.7510415

Ministry of Education Key Laboratory of Measurement and Control, School of Computer Science and Engineering, Southeast University, Nanjing 210096, China

Funds:

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

Author Bio:
Jun Li (M'07-SM'13) received the M.S. degree in mechanical engineering from Jiangsu University, Zhenjiang, China, in 2003, and the Ph.D. degree in control theory and control engineering from Southeast University, Nanjing, China, in 2007.
From 2008 to 2010, he was a post-doctoral fellow with Southeast University, where he is currently an Associate Professor with the School of Automation. In 2014, he was a Visiting Scholar with the New Jersey Institute of Technology, Newark, NJ, USA.
He has been the Principal Investigator of ten national and provincial research projects. His innovative achievements over the past four years include proposing the colored traveling salesman problem, which exploits colors to distinguish the accessibility of cities toward salesmen, an image-guided touch teaching method for industrial manipulators in smart phone testing, and the lean reachability tree for general unbounded Petri nets. He has published over 30 journal and conference papers and holds five invention patents. His current research interests include robotics, machine learning, optimization and control of discrete production systems, and Petri nets.
Dr. Li was a recipient of the Best Ph.D. Dissertation Award of Southeast University, the Outstanding Young Teacher Foundation Award of Southeast University, the Phoenix Contract-Southeast University Teaching Award, and the Best Paper Award of the 12th IEEE International Conference on Networking, Sensing and Control (ICNSC'2015). He was invited to lecture in the IEEE Northern New Jersey Section in 2014 and National Central University, Taipei, in 2015. He served as a Program Committee Member of the 9th and 10th IEEE International Conference on Networking, Sensing and Control. He organized a special session at the ICNSC'2014, Miami, FL, USA, and co-sponsored an international seminar "Discrete Event System Control and Optimization" at Southeast University in 2016. He is a Peer Reviewer of 10+ international journals and NSFC proposals. He is a Senior Member of the China Computer Federation (CCF) and the Chinese Mechanical Engineering Society, and a member of ACM, CCF Technical Committee on Petri nets, the Chinese Association of Automation Technical Committee on Network Information Service, and the Jiangsu Province Computer Federation Technical Committee on Big Data (e-mail:j.li@seu.edu.cn).

Xianghu Meng received the B.S. degree from Shenyang Institute of Engineering, Shenyang, China in 2008, and M.S. degree from Kunming University of Science and Technology, Kunming, China in 2013. He is presently a Ph.D. candidate of Southeast University, Nanjing, China. His current research interests include evolutionary algorithms and production scheduling(e-mail: xdmengxianghu@163.com)

Xing Dai received the B.S. degree from Hunan University of Technology, Zhuzhou, China in 2014. He is currently a postgraduate in control theory and control engineering with the School of Automation, Southeast University, Nanjing, China. His current research interests include evolutionary algorithms and production scheduling(e-mail: 1508178155@qq.com)
Corresponding author: Jun Li, e-mail:j.li@seu.edu.cn
Received Date: 2016-02-19
Accepted Date: 2016-08-31

Abstract

Abstract

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.
- Collision resolution,
- greedy algorithm,
- modeling,
- multiple traveling salesman problem,
- scheduling

FullText(HTML)

References(22)

References

[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
[2]	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
[3]	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/
[4]	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
[5]	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
[6]	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
[7]	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/
[8]	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.
[9]	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
[10]	D. L. Applegate, R. E. Bixby, V. Chvátal, and W. J. Cook, "The traveling salesman problem, " Princeton:Princeton University Press, 2006.
[11]	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/
[12]	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
[13]	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
[14]	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
[15]	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
[16]	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
[17]	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
[18]	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/
[19]	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/
[20]	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
[21]	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
[22]	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/

Supplements(0)

Cited By

Proportional views

Proportional views

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

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

Figures(7) / Tables(3)

Get Citation

PDF

XML

Article Metrics

Article views (1335) PDF downloads(72)

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

doi: 10.1109/JAS.2017.7510415

Abstract

References

Proportional views

Catalog

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

Article Metrics

Export File

Citation

Format

Content