An improved Monte Carlo Tree Search approach to workflow scheduling
Workflow computing has become an essential part of many scientific and engineering fields, while workflow scheduling has long been a well-known NP-complete research problem. Major previous works can be classified into two categories: heuristic-based and guided random-search-based workflow scheduling...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Taylor & Francis Group
2022-12-01
|
| Series: | Connection Science |
| Subjects: | |
| Online Access: | http://dx.doi.org/10.1080/09540091.2022.2052265 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849307517744578560 |
|---|---|
| author | Hok-Leung Kung Shu-Jun Yang Kuo-Chan Huang |
| author_facet | Hok-Leung Kung Shu-Jun Yang Kuo-Chan Huang |
| author_sort | Hok-Leung Kung |
| collection | DOAJ |
| description | Workflow computing has become an essential part of many scientific and engineering fields, while workflow scheduling has long been a well-known NP-complete research problem. Major previous works can be classified into two categories: heuristic-based and guided random-search-based workflow scheduling methods. Monte Carlo Tree Search (MCTS) is a recently proposed search methodology with great success in AI research on game playing, such as Computer Go. However, researchers found that MCTS also has potential application in many other domains, including combinatorial optimization, task scheduling, planning, and so on. In this paper, we present a new workflow scheduling approach based on MCTS, which is still a rarely explored direction. Several new mechanisms are developed for the major steps in MCTS to improve workflow execution schedules further. Experimental results show that our approach outperforms previous methods significantly in terms of execution makespan. |
| format | Article |
| id | doaj-art-2af4f5d52b174db19214fda5865a0d82 |
| institution | Kabale University |
| issn | 0954-0091 1360-0494 |
| language | English |
| publishDate | 2022-12-01 |
| publisher | Taylor & Francis Group |
| record_format | Article |
| series | Connection Science |
| spelling | doaj-art-2af4f5d52b174db19214fda5865a0d822025-08-20T03:54:43ZengTaylor & Francis GroupConnection Science0954-00911360-04942022-12-013411221125110.1080/09540091.2022.20522652052265An improved Monte Carlo Tree Search approach to workflow schedulingHok-Leung Kung0Shu-Jun Yang1Kuo-Chan Huang2National Taichung University of EducationNational Taichung University of EducationNational Taichung University of EducationWorkflow computing has become an essential part of many scientific and engineering fields, while workflow scheduling has long been a well-known NP-complete research problem. Major previous works can be classified into two categories: heuristic-based and guided random-search-based workflow scheduling methods. Monte Carlo Tree Search (MCTS) is a recently proposed search methodology with great success in AI research on game playing, such as Computer Go. However, researchers found that MCTS also has potential application in many other domains, including combinatorial optimization, task scheduling, planning, and so on. In this paper, we present a new workflow scheduling approach based on MCTS, which is still a rarely explored direction. Several new mechanisms are developed for the major steps in MCTS to improve workflow execution schedules further. Experimental results show that our approach outperforms previous methods significantly in terms of execution makespan.http://dx.doi.org/10.1080/09540091.2022.2052265monte carlo tree searchworkflow schedulingparallel processing |
| spellingShingle | Hok-Leung Kung Shu-Jun Yang Kuo-Chan Huang An improved Monte Carlo Tree Search approach to workflow scheduling Connection Science monte carlo tree search workflow scheduling parallel processing |
| title | An improved Monte Carlo Tree Search approach to workflow scheduling |
| title_full | An improved Monte Carlo Tree Search approach to workflow scheduling |
| title_fullStr | An improved Monte Carlo Tree Search approach to workflow scheduling |
| title_full_unstemmed | An improved Monte Carlo Tree Search approach to workflow scheduling |
| title_short | An improved Monte Carlo Tree Search approach to workflow scheduling |
| title_sort | improved monte carlo tree search approach to workflow scheduling |
| topic | monte carlo tree search workflow scheduling parallel processing |
| url | http://dx.doi.org/10.1080/09540091.2022.2052265 |
| work_keys_str_mv | AT hokleungkung animprovedmontecarlotreesearchapproachtoworkflowscheduling AT shujunyang animprovedmontecarlotreesearchapproachtoworkflowscheduling AT kuochanhuang animprovedmontecarlotreesearchapproachtoworkflowscheduling AT hokleungkung improvedmontecarlotreesearchapproachtoworkflowscheduling AT shujunyang improvedmontecarlotreesearchapproachtoworkflowscheduling AT kuochanhuang improvedmontecarlotreesearchapproachtoworkflowscheduling |