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: 11.8, Top 4% (SCI Q1)
    CiteScore: 17.6, Top 3% (Q1)
    Google Scholar h5-index: 77, TOP 5
Turn off MathJax
Article Contents
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

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

doi: 10.1109/JAS.2017.7510772
Funds:

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

the National Natural Science Foundation of China U1401240

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

     

  • loading
  • [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

Catalog

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

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

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

    Figures(8)  / Tables(1)

    Article Metrics

    Article views (929) PDF downloads(91) Cited by()

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return