[논문]Reachability Tree-Based Optimization Algorithm for Cyclic Scheduling of Timed Petri Nets

Kim, Chulhan; Yu, Tae-Sun; Lee, Tae-Eog

doi:10.1109/tase.2020.3009984

[해외논문] Reachability Tree-Based Optimization Algorithm for Cyclic Scheduling of Timed Petri Nets

IEEE transactions on automation science and engineering, v.18 no.3, 2021년, pp.1441 - 1452

Kim, Chulhan (SK Telecom, Seoul, South Korea) , Yu, Tae-Sun (Pukyong National University, Division of Systems Management and Engineering, Busan, South Korea) , Lee, Tae-Eog (Korea Advanced Institute of Science and Technology (KAIST), Daejon, South Korea)

Abstract ▼ AI-Helper

Timed Petri nets (TPNs) have been widely used for modeling discrete-event systems of diverse manufacturing and service industries. In this article, we introduce a reachability tree-based optimization algorithm to optimize cyclic schedules of TPNs. In particular, we focus on a special class of cyclic schedules that are referred to as one-cyclic schedules, i.e., the algorithm efficiently finds the optimal one-cyclic transition firing schedule of a TPN. The proposed scheduling method can be robustly applied and extended to a number of different scheduling models since the methodology is not bounded to a specific domain. To enhance the computational performance, we establish a set of transition ordering constraints that can reduce the tree size during the search procedure. We evaluate the computational efficiency of the suggested algorithm by examining robotized manufacturing systems where one-cyclic schedules are popularly being used. It is numerically shown that the proposed algorithm is computationally more efficient than the previously studied Petri net-based optimization methods. Note to Practitioners—Resource scheduling is one of the most important managerial issues in diverse industrial systems. An optimal scheduling method for a certain industrial system is often locally developed by utilizing domain-specific operational properties. Although such domain-dependent knowledge can contribute to enhancing the computational efficiency of an optimization method, such an approach has a weak point that the method might not be applicable to scheduling problems of different industrial fields. Our motivation is to develop an algorithm for optimizing steady-state schedules that can be robustly applied for various types of discrete-event systems. The algorithm is developed on the basis of the Petri net modeling framework as it is widely being used for describing cyclic behaviors of diverse manufacturing systems, service systems, and social systems. It is experimentally shown that the proposed algorithm is computationally efficient compared with the existing cyclic scheduling methods.

참고문헌 (50)

Yang, Fajun, Wu, NaiQi, Qiao, Yan, Zhou, MengChu, Li, ZhiWu. Scheduling of Single-Arm Cluster Tools for an Atomic Layer Deposition Process With Residency Time Constraints. IEEE transactions on systems, man, and cybernetics. Systems, vol.47, no.3, 502-516.

상세보기
Qiao, Yan, Wu, NaiQi, Yang, FaJun, Zhou, MengChu, Zhu, QingHua. Wafer Sojourn Time Fluctuation Analysis of Time-Constrained Dual-Arm Cluster Tools With Wafer Revisiting and Activity Time Variation. IEEE transactions on systems, man, and cybernetics. Systems, vol.48, no.4, 622-636.

상세보기
Levner, Eugene, Kats, Vladimir, Alcaide López de Pablo, David, Cheng, T.C.E.. Complexity of cyclic scheduling problems: A state-of-the-art survey. Computers & industrial engineering, vol.59, no.2, 352-361.

상세보기
Brauner, N.. Identical part production in cyclic robotic cells: Concepts, overview and open questions. Discrete applied mathematics, vol.156, no.13, 2480-2492.

상세보기
Zhu, QingHua, Zhou, MengChu, Qiao, Yan, Wu, NaiQi. Petri Net Modeling and Scheduling of a Close-Down Process for Time-Constrained Single-Arm Cluster Tools. IEEE transactions on systems, man, and cybernetics. Systems, vol.48, no.3, 389-400.

상세보기
Hyun-Jung Kim, Jun-Ho Lee, Tae-Eog Lee. Noncyclic Scheduling of Cluster Tools With a Branch and Bound Algorithm. IEEE transactions on automation science and engineering, vol.12, no.2, 690-700.

상세보기
Yang, Fajun, Wu, Naiqi, Gao, Kaizhou, Zhang, Chunjiang, Zhu, Yuting, Su, Rong, Qiao, Yan. Efficient Approach to Cyclic Scheduling of Single-Arm Cluster Tools With Chamber Cleaning Operations and Wafer Residency Time Constraint. IEEE transactions on semiconductor manufacturing : a publication of the IEEE Components, Hybrids, and Manufacturing Technology Society, the IEEE Electron Devices Society, the IEEE Reliability Society,, vol.31, no.2, 196-205.

상세보기
Proc IEEE Int Conf Autom Sci Eng Optimal scheduling of dual-armed cluster tools without swap restriction paek 2008 103
Drobouchevitch, Inna G., Sethi, Suresh P., Sriskandarajah, Chelliah. Scheduling dual gripper robotic cell: One-unit cycles. European journal of operational research, vol.171, no.2, 598-631.

상세보기
Che, Ada, Chu, Chengbin, Chu, Feng. Multicyclic hoist scheduling with constant processing times. IEEE transactions on robotics and automation : A publication of the IEEE Robotics and Automation Society, vol.18, no.1, 69-80.

상세보기
Lee, Doo Yong, DiCesare, F.. Scheduling flexible manufacturing systems using Petri nets and heuristic search. IEEE transactions on robotics and automation : A publication of the IEEE Robotics and Automation Society, vol.10, no.2, 123-132.

상세보기
Uzsoy, Reha, Lee, Chung-Yee, Martin-Vega, Louis A.. A REVIEW OF PRODUCTION PLANNING AND SCHEDULING MODELS IN THE SEMICONDUCTOR INDUSTRY PART I: SYSTEM CHARACTERISTICS, PERFORMANCE EVALUATION AND PRODUCTION PLANNING. IIE transactions, vol.24, no.4, 47-60.

상세보기
Chihyun Jung, Tae-Eog Lee. An Efficient Mixed Integer Programming Model Based on Timed Petri Nets for Diverse Complex Cluster Tool Scheduling Problems. IEEE transactions on semiconductor manufacturing : a publication of the IEEE Components, Hybrids, and Manufacturing Technology Society, the IEEE Electron Devices Society, the IEEE Reliability Society,, vol.25, no.2, 186-199.

상세보기
Zuberek, W.M.. Timed Petri nets in modeling and analysis of cluster tools. IEEE transactions on robotics and automation : A publication of the IEEE Robotics and Automation Society, vol.17, no.5, 562-575.

상세보기
10.1109/WSC.2008.4736310
Chihyun Jung, Hyun-Jung Kim, Tae-Eog Lee. A Branch and Bound Algorithm for Cyclic Scheduling of Timed Petri Nets. IEEE transactions on automation science and engineering, vol.12, no.1, 309-323.

상세보기
Li, Shao Yong, Li, Zhi Wu, Hu, He Suan. Siphon extraction for deadlock control in flexible manufacturing systems by using Petri nets. International journal of computer integrated manufacturing, vol.24, no.8, 710-725.

상세보기
Yu, Tae-Sun, Kim, Hyun-Jung, Lee, Tae-Eog. Scheduling Single-Armed Cluster Tools With Chamber Cleaning Operations. IEEE transactions on automation science and engineering, vol.15, no.2, 705-716.

상세보기
10.1080/17517575.2014.948936
Zhang, SiWei, Wu, NaiQi, Li, ZhiWu, Qu, Ting, Li, CongDong. Petri net-based approach to short-term scheduling of crude oil operations with less tank requirement. Information sciences, vol.417, 247-261.

상세보기
Korbaa, Ouajdi, Benasser, Ahmer, Yim, Pascal. Two FMS scheduling methods based on Petri nets: a global and a local approach. International journal of production research, vol.41, no.7, 1349-1371.

상세보기
10.1109/IECON.1995.483360
Yan, Pengyu, Chu, Chengbin, Yang, Naiding, Che, Ada. A branch and bound algorithm for optimal cyclic scheduling in a robotic cell with processing time windows. International journal of production research, vol.48, no.21, 6461-6480.

상세보기
10.1142/3376
Jeng, MuDer, Xie, Xiaolan. Modeling and analysis of semiconductor manufacturing systems with degraded behavior using Petri nets and siphons. IEEE transactions on robotics and automation : A publication of the IEEE Robotics and Automation Society, vol.17, no.5, 576-588.

상세보기
Ko, Sung-Gil, Yu, Tae-Sun, Lee, Tae-Eog. Scheduling Dual-Armed Cluster Tools for Concurrent Processing of Multiple Wafer Types With Identical Job Flows. IEEE transactions on automation science and engineering, vol.16, no.3, 1058-1070.

상세보기
10.1109/ICSMC.2001.972979
10.1109/ICSMC.2002.1176029
Choi, Jin Young, Reveliotis, S.A.. A generalized stochastic Petri net model for performance analysis and control of capacitated reentrant lines. IEEE transactions on robotics and automation : A publication of the IEEE Robotics and Automation Society, vol.19, no.3, 474-480.

상세보기
10.1109/ETFA.2003.1247721
Zuberek, W.M.. Cluster tools with chamber revisiting-modeling and analysis using timed Petri nets. IEEE transactions on semiconductor manufacturing : a publication of the IEEE Components, Hybrids, and Manufacturing Technology Society, the IEEE Electron Devices Society, the IEEE Reliability Society,, vol.17, no.3, 333-344.

상세보기
Int J Adv Manuf Technol Applications of Petri nets in production scheduling: A review tuncel 2006 10.1007/s00170-006-0640-1 34 762

상세보기
Liao, Da-Yin, Jeng, Mu-Der, Zhou, MengChu. Application of Petri Nets and Lagrangian Relaxation to Scheduling Automatic Material-Handling Vehicles in 300-mm Semiconductor Manufacturing. IEEE transactions on systems, man and cybernetics. a publication of the IEEE Systems, Man, and Cybernetics Society. Part C, Applications and reviews, vol.37, no.4, 504-516.

상세보기
Nai Qi Wu, MengChu Zhou. Modeling, Analysis and Control of Dual-Arm Cluster Tools With Residency Time Constraint and Activity Time Variation Based on Petri Nets. IEEE transactions on automation science and engineering, vol.9, no.2, 446-454.

상세보기
Qinghua Zhu, Naiqi Wu, Yan Qiao, Mengchu Zhou. Optimal Scheduling of Complex Multi-Cluster Tools Based on Timed Resource-Oriented Petri Nets. IEEE access : practical research, open solutions, vol.4, 2096-2109.

상세보기
NaiQi Wu, Feng Chu, Chengbin Chu, MengChu Zhou. Petri Net Modeling and Cycle-Time Analysis of Dual-Arm Cluster Tools With Wafer Revisiting. IEEE transactions on systems, man, and cybernetics. Systems, vol.43, no.1, 196-207.

상세보기
Murata, T.. Petri nets: Properties, analysis and applications. Proceedings of the IEEE, vol.77, no.4, 541-580.

상세보기
van der Aalst, W. M. P.. Petri net based scheduling. OR Spektrum : Organ der Deutschen Gesellschaft für Operations Research, vol.18, no.4, 219-229.

상세보기
Wang, Hunglin M., Wang, H.-P. Ben. Generation of optimal operating strategies for robotic cells: a Petri net approach. International journal of computer integrated manufacturing, vol.8, no.1, 32-42.

상세보기
Synchronization and Linearity An Algebra for Discrete Event Systems baccelli 2001
Lee, Tae-Eog, Park, Seong-Ho. An extended event graph with negative places and tokens for time window constraints. IEEE transactions on automation science and engineering, vol.2, no.4, 319-332.

상세보기
10.1109/ICSMC.1998.725471
Bai, Liping, Wu, Naiqi, Li, Zhiwu, Zhou, MengChu. Optimal One-Wafer Cyclic Scheduling and Buffer Space Configuration for Single-Arm Multicluster Tools With Linear Topology. IEEE transactions on systems, man, and cybernetics. Systems, vol.46, no.10, 1456-1467.

상세보기
Yang, Fajun, Wu, Naiqi, Qiao, Yan, Su, Rong. Polynomial approach to optimal one-wafer cyclic scheduling of treelike hybrid multi-cluster tools via Petri nets. IEEE/CAA journal of automatica sinica, vol.5, no.1, 270-280.

상세보기
Amari, S., Demongodin, I., Loiseau, J. J., Martinez, C.. Max-Plus Control Design for Temporal Constraints Meeting in Timed Event Graphs. IEEE transactions on automatic control, vol.57, no.2, 462-467.

상세보기
Levner, Eugene, Kats, Vladimir. A parametric critical path problem and an application for cyclic scheduling. Discrete applied mathematics, vol.87, no.1, 149-158.

상세보기
Wang, Jipeng, Pan, Chunrong, Hu, Hesuan, Li, Liang, Zhou, Yuan. A Cyclic Scheduling Approach to Single-Arm Cluster Tools With Multiple Wafer Types and Residency Time Constraints. IEEE transactions on automation science and engineering, vol.16, no.3, 1373-1386.

상세보기
Pan, Chunrong, Zhao, Kun, Lu, Yanjun, Zhang, Fei. Scheduling and optimization of mixed-processing with multi-variety wafers in dual-armed cluster tools. Journal of the Chinese Institute of Engineers = 中國工程學刊, vol.41, no.6, 463-472.

상세보기
QingHua Zhu, NaiQi Wu, Yan Qiao, MengChu Zhou. Petri Net-Based Optimal One-Wafer Scheduling of Single-Arm Multi-Cluster Tools in Semiconductor Manufacturing. IEEE transactions on semiconductor manufacturing : a publication of the IEEE Components, Hybrids, and Manufacturing Technology Society, the IEEE Electron Devices Society, the IEEE Reliability Society,, vol.26, no.4, 578-591.

상세보기
10.1007/978-1-4615-5537-7

LOADING...

활용도 분석정보

상세보기

다운로드

내보내기

활용도 Top5 논문

해당 논문의 주제분야에서 활용도가 높은 상위 5개 콘텐츠를 보여줍니다.
더보기 버튼을 클릭하시면 더 많은 관련자료를 살펴볼 수 있습니다.

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증