[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Online-learning task scheduling with GNN-RL scheduler in collaborative edge computing

  • Published:
Cluster Computing Aims and scope Submit manuscript

Abstract

With the development of collaborative edge computing (CEC), the manufacturing market is gradually moving toward large-scale, multi-scenario, and dynamic directions. The existing scheduling strategies based on machine learning or deep learning are only applicable to specific scenarios, which is difficult to meet the requirements of dynamic real-time scheduling in multiple scenarios. The proposed digital twin technology provides a new solution for real-time scheduling of multiple scenarios. In this paper, a digital twin-oriented multi-scene real-time scheduler (GNN-RL) is proposed. This scheduler converts task sequences into node trees and sets up two learning layers. The first layer is an online learning representation layer, which uses GNN to learn node features of embedded structures in real time to boost large instances without additional training. The second layer is the online learning policy layer, which introduces imitation learning mappings into optimal scheduling behavior policies adapted to multiple scenarios. Finally, our approach is validated in several scenarios in 3D digital twin factories, such as computationally intensive, delay-sensitive, and task-urgent scenarios. Since the scheduler proposed in this paper learns general features of the embedding graph rather than instance-specific features, it has good generality and scalability, with good generalization and scalability, outperforming other scheduling rules and schedulers on various benchmarks.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Afrin, M., Jin, J., Rahman, A., Tian, Y.-C., Kulkarni, A.: Multi-objective resource allocation for edge cloud based robotic workflow in smart factory. Fut. Gen. Comput. Syst. 97, 119–130 (2019)

    Article  Google Scholar 

  2. Wang, X., Han, Y., Leung, V.C., Niyato, D., Yan, X., Chen, X.: Convergence of edge computing and deep learning: a comprehensive survey. IEEE Commun. Surv. Tutor. 22(2), 869–904 (2020)

    Article  Google Scholar 

  3. Li, Y., Wang, X., Gan, X., Jin, H., Fu, L., Wang, X.: Learning-aided computation offloading for trusted collaborative mobile edge computing. IEEE Trans. Mob. Comput. 19(12), 2833–2849 (2019)

    Article  Google Scholar 

  4. Gao, H., Huang, W., Duan, Y.: The cloud-edge-based dynamic reconfiguration to service workflow for mobile ecommerce environments: a qos prediction perspective. ACM Trans. Internet Technol. 21(1), 1–23 (2021)

    Article  CAS  Google Scholar 

  5. He, C., Wang, R., Wu, D., Zhang, H., Tan, Z.: Qos-aware hybrid cloudlet placement over joint fiber and wireless backhaul access network. Opt. Switch. Netw. 45, 100678 (2022)

    Article  Google Scholar 

  6. Leng, J., Chen, Z., Sha, W., Ye, S., Liu, Q., Chen, X.: Cloud-edge orchestration-based bi-level autonomous process control for mass individualization of rapid printed circuit boards prototyping services. J. Manuf. Syst. 63, 143–161 (2022)

    Article  Google Scholar 

  7. Manne, A.S.: On the job-shop scheduling problem. Oper. Res. 8(2), 219–223 (1960)

    Article  MathSciNet  Google Scholar 

  8. Lomnicki, Z.A.: A “branch-and-bound’’ algorithm for the exact solution of the three-machine scheduling problem. J. Oper. Res. Soc. 16(1), 89–100 (1965)

    Article  Google Scholar 

  9. Krishna, K., Ganeshan, K., Ram, D.J.: Distributed simulated annealing algorithms for job shop scheduling. IEEE Trans. Syst. Man Cybern. 25(7), 1102–1109 (1995)

    Article  Google Scholar 

  10. Gupta, A.K., Sivakumar, A.I.: Job shop scheduling techniques in semiconductor manufacturing. Int. J. Adv. Manuf. Technol. 27(11), 1163–1169 (2006)

    Article  Google Scholar 

  11. Muteeh, A., Sardaraz, M., Tahir, M.: Mrlba: multi-resource load balancing algorithm for cloud computing using ant colony optimization. Clust. Comput. 24(4), 3135–3145 (2021)

    Article  Google Scholar 

  12. Kim, Y.-J.: A supervised-learning-based strategy for optimal demand response of an HVAC system in a multi-zone office building. IEEE Trans. Smart Grid 11(5), 4212–4226 (2020)

    Article  Google Scholar 

  13. Qi, Q., Zhang, L., Wang, J., Sun, H., Zhuang, Z., Liao, J., Yu, F.R.: Scalable parallel task scheduling for autonomous driving using multi-task deep reinforcement learning. IEEE Trans. Vehicul. Technol. 69(11), 13861–13874 (2020)

    Article  Google Scholar 

  14. Grondman, I., Busoniu, L., Lopes, G.A.D., Babuska, R.: A survey of actor-critic reinforcement learning: standard and natural policy gradients. IEEE Trans. Syst. Man Cybern. C 42(6), 1291–1307 (2012)

    Article  Google Scholar 

  15. Park, J., Chun, J., Kim, S.H., Kim, Y., Park, J.: Learning to schedule job-shop problems: representation and policy learning using graph neural network and reinforcement learning. Int. J. Prod. Res. 59(11), 3360–3377 (2021)

    Article  Google Scholar 

  16. Li, J., Gao, H., Lv, T., Lu, Y.: Deep reinforcement learning based computation offloading and resource allocation for MEC. In: 2018 IEEE Wireless Communications and Networking Conference (WCNC), pp. 1–6 (2018). IEEE

  17. Yang, T., Hu, Y., Gursoy, M.C., Schmeink, A., Mathar, R.: Deep reinforcement learning based resource allocation in low latency edge computing networks. In: 2018 15th International Symposium on Wireless Communication Systems (ISWCS), pp. 1–5 (2018). IEEE

  18. Wang, Y.-C., Usher, J.M.: Application of reinforcement learning for agent-based production scheduling. Eng. Appl. Artif. Intell. 18(1), 73–82 (2005)

    Article  CAS  Google Scholar 

  19. Yu, Z., Wang, K., Wan, Z., Xie, S., Lv, Z.: Popular deep learning algorithms for disease prediction: a review. Clust. Comput. 1, 1–21 (2022)

    Google Scholar 

  20. Bellavista, P., Giannelli, C., Mamei, M., Mendula, M., Picone, M.: Application-driven network-aware digital twin management in industrial edge environments. IEEE Trans. Ind. Inf. 17(11), 7791–7801 (2021)

    Article  Google Scholar 

  21. Tao, F., Zhang, H., Liu, A., Nee, A.Y.C.: Digital twin in industry: state-of-the-art. IEEE Trans. Ind. Inf. 15(4), 2405–2415 (2019)

    Article  Google Scholar 

  22. Khalil, E., Dai, H., Zhang, Y., Dilkina, B., Song, L.: Learning combinatorial optimization algorithms over graphs. Adv. Neural Inf. Process. Syst. 30, 1 (2017)

    Google Scholar 

  23. Kool, W., Van Hoof, H., Welling, M.: Attention, learn to solve routing problems! arXiv preprint arXiv:1803.08475 (2018)

  24. Mao, H., Schwarzkopf, M., Venkatakrishnan, S., Meng, Z., Alizadeh, M.: Learning scheduling algorithms for data processing clusters, pp. 270–288. ACM (2019)

  25. Gasse, M., Chételat, D., Ferroni, N., Charlin, L., Lodi, A.: Exact combinatorial optimization with graph convolutional neural networks. Adv. Neural Inf. Process. Syst. 32, 1 (2019)

    Google Scholar 

  26. Wang, Z., Gombolay, M.: Learning scheduling policies for multi-robot coordination with graph attention networks. IEEE Robot. Autom. Lett. 5(3), 4509–4516 (2020)

    Article  Google Scholar 

  27. Li, H., Huang, J., Wang, B., Fan, Y.: Weighted double deep q-network based reinforcement learning for bi-objective multi-workflow scheduling in the cloud. Clust. Comput. 25(2), 751–768 (2022)

    Article  Google Scholar 

  28. Lee, M., Yu, G., Li, G.Y.: Graph embedding-based wireless link scheduling with few training samples. IEEE Trans. Wirel. Commun. 20(4), 2282–2294 (2021)

    Article  Google Scholar 

  29. Schulman, J., Levine, S., Abbeel, P., Jordan, M., Moritz, P.: Trust region policy optimization. In: International Conference on Machine Learning, pp. 1889–1897 (2015). PMLR

  30. Schulman, J., Wolski, F., Dhariwal, P., Radford, A., Klimov, O.: Proximal policy optimization algorithms. ArXiv abs/1707.06347 (2017)

Download references

Acknowledgements

This work was supported in part by the National Natural Science Foundation of China under Grant Nos. 61672461 and 62073293.

Author information

Author notes

  1. Chengfeng Jian, Zhuoyang Pan, Lukun Bao and Meiyu Zhang have contributed equally to this work.

Authors and Affiliations

  1. Computer Science and Technology College, Zhejiang University of Technology, Hangzhou, 310023, China

    Chengfeng Jian, Zhuoyang Pan, Lukun Bao & Meiyu Zhang

Authors
  1. Chengfeng Jian
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Zhuoyang Pan
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Lukun Bao
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Meiyu Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Chengfeng Jian.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Jian, C., Pan, Z., Bao, L. et al. Online-learning task scheduling with GNN-RL scheduler in collaborative edge computing. Cluster Comput 27, 589–605 (2024). https://doi.org/10.1007/s10586-022-03957-w

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10586-022-03957-w

Keywords

Search

Navigation