Polynomial Approach to Optimal One-wafer Cyclic Scheduling of Treelike Hybrid Multi-Cluster Tools via Petri Nets

Fajun Yang; Naiqi Wu; Yan Qiao; Rong Su

doi:10.1109/JAS.2017.7510772

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): 270-280

Fajun Yang, Naiqi Wu, Yan Qiao and Rong Su, "Polynomial Approach to Optimal One-wafer Cyclic Scheduling of Treelike Hybrid Multi-Cluster Tools via Petri Nets," IEEE/CAA J. Autom. Sinica, vol. 5, no. 1, pp. 270-280, Jan. 2018. doi: 10.1109/JAS.2017.7510772

Citation:

Fajun Yang, Naiqi Wu, Yan Qiao and Rong Su, "Polynomial Approach to Optimal One-wafer Cyclic Scheduling of Treelike Hybrid Multi-Cluster Tools via Petri Nets," IEEE/CAA J. Autom. Sinica, vol. 5, no. 1, pp. 270-280, Jan. 2018. doi: 10.1109/JAS.2017.7510772

Citation:

PDF( 1814 KB)

Polynomial Approach to Optimal One-wafer Cyclic Scheduling of Treelike Hybrid Multi-Cluster Tools via Petri Nets

doi: 10.1109/JAS.2017.7510772

Fajun Yang^{1, 2
,
,},
Naiqi Wu^3
,,
Yan Qiao^3
,,
Rong Su^4
,

1.
Department of Industrial Engineering, School of Electro-Mechanical Engineering, Guangdong University of Technology, Guangzhou 510006, China
2.
School of Electrical and Electronic Engineering at Nanyang Technological University, 639798, Singapore
3.
Institute of Systems Engineering, Macau University of Science and Technology, Taipa, Macau 999078, China
4.
school of Electro-Mechanical Engineering, Guangdong University of Technology, Guangzhou 510006, China

Funds:

Science and Technology Development Fund (FDCT) of Macau 106/2016/A3

the National Natural Science Foundation of China U1401240

More Information

Author Bio:
Fajun Yang received the B.S. degree in industrial engineering from Hunan University of Science and Technology, Xiangtan, China, in 2011, the Ph.D. degree in mechanical engineering from Guangdong University of Technology, Guangzhou, China, in 2016. From 2015-2016, he was a Visiting Student with New Jersey Institute of Technology, Newark, NJ, USA. He is currently a Research Fellow with Nanyang Technological University, Singapore. He has 10+ journal and conference papers. His research interests are Petri nets, production planning, discrete event systems, scheduling and control. He has served as a reviewer for a number of journals. (e-mail: fjyang@ntu.edu.sg)

Naiqi Wu (M'04-SM'05) received his B.S. Degree in electrical engineering from Anhui University of Technology, Huainan, China, in 1982, the M. S. and Ph.D. Degrees in systems engineering both from Xi'an Jiaotong University, Xi'an, China in 1985 and 1988, respectively. From 1988 to 1995, he was with Shenyang Institute of Automation, Chinese Academy of Sciences, Shenyang, China, and from 1995 to 1998, with Shantou University, Shantou, China. He moved to Guangdong University of Technology, Guangzhou, China in 1998. He joined Macau University of Science and Technology in 2013. He is currently a Professor at the Institute of Systems Engineering, Macau University of Science and Technology. His research interests include production planning and scheduling, manufacturing system modeling and control, discrete event systems, Petri net theory and applications, intelligent transportation systems, and energy systems. He is the author or coauthor of one book, five book chapters, and 130+ peer-reviewed journal papers. Dr. Wu was an Associate Editor of the IEEE Transactions on Systems, Man, & Cybernetics, Part C, IEEE Transactions on Automation Science and Engineering, IEEE Transactions on Systems, Man, & Cybernetics:Systems, and Editor in Chief of Industrial Engineering Journal. He is now a Guest Editor of IEEE/CAA Journal of Automatica Sinica and an Associate Editor of Information Sciences. (e-mail: nqwu@must.edu.mo)

Yan Qiao (M'16) received the B.S. and Ph. D. degrees in industrial engineering and mechanical engineering from the Guangdong University of Technology, Guangzhou, China, in 2009 and 2015, respectively.
From 2014 to 2015, he was a Visiting Student with the Department of Electrical and Computer Engineering, New Jersey Institute of Technology, Newark, NJ, USA. He is currently a Post-Doctoral Research Associate with the Institute of Systems Engineering, Macau University of Science and Technology. He has one book chapter and 20+ international journal papers (majority in the IEEE Transactions). His research interests include discrete event systems, production planning, Petri nets, scheduling and control.
Dr. Qiao was a recipient of the QSI Best Application Paper Award Finalist of 2011 IEEE International Conference on Automation Science and Engineering, the Best Student Paper Award of 2012 IEEE International Conference on Networking, Sensing and Control, and the Best Conference Paper Award Finalist of 2016 IEEE International Conference on Automation Science and Engineering. He has served as a reviewer for a number of journals. (e-mail: yqiao@must.edu.mo)

Rong Su (M'11-SM'14) received the B.E. degree in automatic control from the University of Science and Technology of China, Hefei, China, in 1997, and the M.A.Sc. and Ph.D. degrees both in electrical engineering from the University of Toronto, Toronto, ON, Canada, in 2000 and 2004, respectively. Since then he was affiliated with University of Waterloo and Technical University of Eindhoven before he joined Nanyang Technological University, Singapore, in 2010. His research interests include discrete event systems, supervisory control, modelbased fault diagnosis, multi-agent systems, optimization and scheduling with applications in green buildings, flexible manufacturing, power management, and intelligent transportation systems. In the aforementioned areas, he has more than 130 publications in journals, book chapters, and conference proceedings, and two patents. Dr. Su is an Associate Editor for Journal of Discrete Event Dynamic Systems:Theory and Applications, Journal of Control and Decision, and Transactions of the Institute of Measurement and Control, and the Chair of IEEE Control Systems Society Technical Committee on Smart Cities. (e-mail: RSu@ntu.edu.sg)
Corresponding author: Fujun Yang, e-mail:fjyang@ntu.edu.sg
Received Date: 2017-04-28
Accepted Date: 2017-07-06

Abstract

Abstract

A treelike hybrid multi-cluster tool is composed of both single-arm and dual-arm cluster tools with a treelike topology. Scheduling such a tool is challenging. For a hybrid treelike multi-cluster tool whose bottleneck individual tool is process-bound, this work aims at finding its optimal one-wafer cyclic schedule. It is modeled with Petri nets such that a onewafer cyclic schedule is parameterized as its robots' waiting time. Based on the model, this work proves the existence of its onewafer cyclic schedule that features with the ease of industrial implementation. Then, computationally efficient algorithms are proposed to find the minimal cycle time and optimal onewafer cyclic schedule. Multi-cluster tool examples are given to illustrate the proposed approach. The use of the found schedules enables industrial multi-cluster tools to operate with their highest productivity.
- Multi-cluster tool,
- Petri nets,
- scheduling,
- semiconductor manufacturing

FullText(HTML)

References(39)

References

[1]	N. Q. Wu and M. C. Zhou, "A closed-form solution for schedulability and optimal scheduling of dual-arm cluster tools with wafer residency time constraint based on steady schedule analysis, " IEEE Trans. Automat. Sci. Eng., vol. 7, no. 2, pp. 303-315, Apr. 2010. http://ieeexplore.ieee.org/document/5164901/
[2]	W. K. Chan, J. G. Yi, and S. W. Ding, "On the optimality of one-unit cycle scheduling of multi-cluster tools with single-blade robots, " in Proc. IEEE Int. Conf. Automation Science and Engineering, Scottsdale, AZ, USA, 2007, pp. 392-397. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4341844
[3]	N. Q. Wu, L. P. Bai, and M. C. Zhou, "An efficient scheduling method for crude oil operations in refinery with crude oil type mixing requirements, " IEEE Trans. Syst., Man, Cybern. Syst., vol. 46, no. 3, pp. 413-426, Mar. 2016.
[4]	N. Q. Wu, M. C. Zhou, L. P. Bai, and Z. W. Li, "Short-term scheduling of crude oil operations in refinery with high-fusion-point oil and two transportation pipelines, " Enterp. Inform. Syst., vol. 10, no. 6, pp. 581-610, Sep. 2016. http://dl.acm.org/citation.cfm?id=2938192.2938193
[5]	N. Q. Wu, M. C. Zhou, and Z. W. Li, "Short-term scheduling of crudeoil operations: Enhancement of crude-oil operations scheduling using a petri net-based control-theoretic approach, " IEEE Robot. Automat. Mag., vol. 22, no. 2, pp. 64-76, Jun. 2015. http://ieeexplore.ieee.org/xpl/abstractAuthors.jsp?arnumber=7108023
[6]	Y. Hou, N. Q. Wu, M. C. Zhou, and Z. W. Li, "Pareto-optimization for scheduling of crude oil operations in refinery via genetic algorithm, " IEEE Transactions on Systems, Man, Cybernetics: Systems, vol. 47, no. 3, pp. 517-530, Mar. 2017. http://ieeexplore.ieee.org/document/7366610/
[7]	S. W. Zhang, N. Q. Wu, Z. W. Li, T. Qu, and C. D. Li, "Petri net-based approach to short-term scheduling of crude oil operations with less tank requirement, " Information Sciences, vol. 417, pp. 247-261, Nov. 2017. http://www.infona.pl/resource/bwmeta1.element.elsevier-6770e744-9773-3a8c-9755-009dd7cd0e6e
[8]	N. Q. Wu, Z. W. Li, and T. Qu, "Energy efficiency optimization in scheduling crude oil operations of refinery based on linear programming, " Journal of Cleaner Production, vol. 166, 49-57, Nov. 2017. http://www.sciencedirect.com/science/article/pii/S0959652617316785
[9]	T. L. Perkinson, R. S. Gyurcsik, and P. K. McLarty, "Single-wafer cluster tool performance: An analysis of the effects of redundant chambers and revisitation sequences on throughput, " IEEE Trans. Semicond. Manuf., vol. 9, no. 3, pp. 384-400, Aug. 1996. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=536110
[10]	T. L. Perkinson, P. K. McLarty, R. S. Gyurcsik, and R. K. Cavin Ⅲ, "Single-wafer cluster tool performance: An analysis of throughput, " IEEE Trans. Semicond. Manuf., vol. 7, no. 3, pp. 369-373, Aug. 1994. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=311340
[11]	S. P. Sethi, C. Sriskandarajah, G. Sorger, J. Blazewicz, and W. Kubiak, "Sequencing of parts and robot moves in a robotic cell, " Int. J. Flex. Manuf. Syst., vol. 4, no. 3-4, pp. 331-358, Jun. 1992. doi: 10.1007/BF01324886
[12]	S. Venkatesh, R. Davenport, P. Foxhoven, and J. Nulman, "A steadystate throughput analysis of cluster tools: Dual-blade versus single-blade robots, " IEEE Trans. Semicond. Manuf., vol. 10, no. 4 pp. 418-424, Nov. 1997. http://ieeexplore.ieee.org/document/641483/
[13]	N. Q. Wu, F. Chu, C. B. Chu, and M. C. Zhou, "Petri net modeling and cycle-time analysis of dual-arm cluster tools with wafer revisiting, " IEEE Trans. Syst., Man, Cybern. Syst., vol. 43, no. 1, pp. 196-207, Jan. 2013. http://ieeexplore.ieee.org/document/6174478/
[14]	N. Q. Wu and M. C. Zhou, "Modeling, analysis and control of dual-arm cluster tools with residency time constraint and activity time variation based on Petri nets, " IEEE Trans. Automat. Sci. Eng., vol. 9, no. 2, pp. 446-454, Apr. 2012. http://ieeexplore.ieee.org/document/6138879/
[15]	N. Q. Wu and M. C. Zhou, "Schedulability analysis and optimal scheduling of dual-arm cluster tools with residency time constraint and activity time variation, " IEEE Trans. Automat. Sci. Eng., vol. 9, no. 1, pp. 203-209, Jan. 2012. http://ieeexplore.ieee.org/document/5957289/
[16]	N. Q. Wu, M. C. Zhou, F. Chu, and C. B. Chu, "A Petri-net-based scheduling strategy for dual-arm cluster tools with wafer revisiting, " IEEE Trans. Syst., Man, Cybern. Syst., vol. 43, no. 5, pp. 1182-1194, Sep. 2013. http://ieeexplore.ieee.org/document/6425515/
[17]	F. J. Yang, N. Q. Wu, Y. Qiao, M. C. Zhou, and Z. W. Li, "Scheduling of single-arm cluster tools for an atomic layer deposition process with residency time constraints, " IEEE Trans. Syst., Man, Cybern. Syst., vol. 47, no. 3, pp. 502-516, Mar. 2017. http://ieeexplore.ieee.org/document/7395391/
[18]	W. M. Zuberek, "Timed Petri nets in modeling and analysis of cluster tools, " IEEE Trans. Robot. Automat., vol. 17, no. 5, pp. 562-575, Oct. 2001. http://ieeexplore.ieee.org/xpls/icp.jsp?arnumber=964658
[19]	C. R. Pan, M. C. Zhou, Y. Qiao, and N. Q. Wu, "Scheduling cluster tools in semiconductor manufacturing: Recent advances and challenges, " IEEE Trans. Automat. Sci. Eng., to be published. doi: 10.1109/TASE.2016.2642997.
[20]	J. H. Kim, T. E. Lee, H. Y. Lee, and D. B. Park, "Scheduling analysis of time-constrained dual-armed cluster tools, " IEEE Trans. Semicond. Manuf., vol. 16, no. 3, pp. 521-534, Aug. 2003. http://ieeexplore.ieee.org/xpls/icp.jsp?arnumber=1219500
[21]	T. E. Lee, H. Y. Lee, and Y. H. Shin, "Workload balancing and scheduling of a single-armed cluster tool, " in Proc. 5th APIEMS Conf., Gold Coast, Australia, 2004, pp. 1-15. http://hdl.handle.net/10203/146698
[22]	M. J. Lopez and S. C. Wood, "Systems of multiple cluster tools:Configuration, reliability, and performance, " IEEE Trans. Semicond. Manuf., vol. 16, no. 2, pp. 170-178, May 2003. doi: 10.1109/TSM.2003.810936
[23]	D. Jevtic and S. Venkatesh, "Method and apparatus for scheduling wafer processing within a multiple chamber semiconductor wafer processing tool having a multiple blade robot, " U. S. Patent 6224638, May 1, 2001. http://www.freepatentsonline.com/6224638.html
[24]	S. W. Ding, J. G. Yi, and M. T. Zhang, "Multicluster tools scheduling: An integrated event graph and network model approach, " IEEE Trans. Semicond. Manuf., vol. 19, no. 3, pp. 339-351, Aug. 2006. http://ieeexplore.ieee.org/document/1668233/
[25]	J. G. Yi, S. W. Ding, D. Z. Song, and M. T. Zhang, "Steady-state throughput and scheduling analysis of multicluster tools: A decomposition approach, " IEEE Trans. Automat. Sci. Eng., vol. 5, no. 2, pp. 321-336, Apr. 2008. http://ieeexplore.ieee.org/document/4358085/
[26]	W. K. V. Chan, J. G. Yi, and S. W. Ding, "Optimal scheduling of multicluster tools with constant robot moving times, Part Ⅰ: Two-cluster analysis, " IEEE Trans. Automat. Sci. Eng., vol. 8, no. 1, pp. 5-16, Jan. 2011. http://ieeexplore.ieee.org/document/5447799/
[27]	W. K. V. Chan, S. W. Ding, J. G. Yi, and D. Z. Song, "Optimal scheduling of multicluster tools with constant robot moving times, Part Ⅱ: Tree-like topology configurations, " IEEE Trans. Automat. Sci. Eng., vol. 8, no. 1, pp. 17-28, Jan. 2011. http://ieeexplore.ieee.org/document/5454420/
[28]	S. Ware and R. Su, "An application of incremental scheduling to a cluster photolithography tool, " in IFAC World Congress 2017, Toulouse, France, to be published.
[29]	Q. H. Zhu, N. Q. Wu, Y. Qiao, and M. C. Zhou, "Petri net-based optimal one-wafer scheduling of single-arm multi-cluster tools in semiconductor manufacturing, " IEEE Trans. Semicond. Manuf., vol. 26, no. 4, pp. 578-591, Nov. 2013. http://ieeexplore.ieee.org/document/6579732/
[30]	Q. H. Zhu, N. Q. Wu, Y. Qiao, and M. C. Zhou, "Scheduling of single-arm multi-cluster tools with wafer residency time constraints in semiconductor manufacturing, " IEEE Trans. Semicond. Manuf., vol. 28, no. 1, pp. 117-125, Feb. 2015. http://ieeexplore.ieee.org/document/6971220/
[31]	F. J. Yang, N. Q. Wu, Y. Qiao, and M. C. Zhou, "Petri net-based optimal one-wafer cyclic scheduling of hybrid multi-cluster tools in wafer fabrication, " IEEE Trans. Semicond. Manuf., vol.27, no.2, pp. 192-203, May 2014. doi: 10.1109/TSM.2014.2312192
[32]	F. J. Yang, N. Q. Wu, Y. Qiao, and M. C. Zhou, "Petri net-based polynomially complex approach to optimal one-wafer cyclic scheduling of hybrid multi-cluster tools in semiconductor manufacturing, " IEEE Trans. Syst., Man, Cybern. Syst., vol. 44, no. 12, pp. 1598-1610, Dec. 2014. http://ieeexplore.ieee.org/document/6815731/
[33]	L. P. Bai, N. Q. Wu, Z. W. Li, and M. C. Zhou, "Optimal onewafer cyclic scheduling and buffer space configuration for single-arm multicluster tools with linear topology, " IEEE Trans. Syst., Man, Cybern. Syst., vol. 46, no. 10, pp. 1456-1467, Oct. 2016. http://ieeexplore.ieee.org/document/7372477/
[34]	F. J. Yang, N. Q. Wu, Y. Qiao, and M. C. Zhou, "Optimal onewafer cyclic scheduling of hybrid multirobot cluster tools with tree topology, " IEEE Trans. Syst., Man, Cybern. Syst., to be published, doi: 10.1109/TSMC.2016.2587697.
[35]	Y. F. Chen, Z. W. Li, K. Barkaoui, N. Q. Wu, and M. C. Zhou "Compact supervisory control of discrete event systems by Petri nets with data inhibitor arcs, " IEEE Trans. Syst., Man, Cybern. Syst., vol. 47, no. 2, pp. 364-379, Feb. 2017. http://ieeexplore.ieee.org/document/7426418/
[36]	H. F. Chen, N. Q. Wu, and M. C. Zhou, "A novel method for deadlock prevention of AMS by using resource-oriented Petri nets" Inform. Sci., vol. 363, pp. 178-189, Oct. 2016. http://www.sciencedirect.com/science/article/pii/S0020025515005915
[37]	N. Q. Wu, "Necessary and sufficient conditions for deadlock-free operation in flexible manufacturing systems using a colored petri net model, " IEEE Trans. Syst., Man, Cybern., C Appl. Rev., vol. 29, no. 2, pp. 192-204, May 1999. doi: 10.1109/5326.760564
[38]	N. Q. Wu and M. C. Zhou, System Modeling and Control with ResourceOriented Petri nets. New York, USA:CRC Press, 2009.
[39]	N. Q. Wu, C. B. Chu, F. Chu, and M. C. Zhou, "A petri net method for schedulability and scheduling problems in single-arm cluster tools with wafer residency time constraints, " IEEE Trans. Semicond. Manuf., vol. 21, no. 2, pp. 224-237, May 2008. doi: 10.1109/TSM.2008.2000425

Supplements(0)

Cited By

Proportional views

Proportional views

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

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

Figures(8) / Tables(1)

Get Citation

PDF

XML

Article Metrics

Article views (971) PDF downloads(96)

Polynomial Approach to Optimal One-wafer Cyclic Scheduling of Treelike Hybrid Multi-Cluster Tools via Petri Nets

doi: 10.1109/JAS.2017.7510772

Abstract

References

Proportional views

Catalog

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

Article Metrics

Export File

Citation

Format

Content