BỘ KHOA HỌC VÀ CÔNG NGHỆ
HỆ THỐNG THÔNG TIN KHOA HỌC VÀ CÔNG NGHỆ

Lọc theo danh mục
  • Năm xuất bản
    Xem thêm
  • Lĩnh vực
liên kết website
Lượt truy cập
 Lượt truy cập :  23,197,148
  • Công bố khoa học và công nghệ Việt Nam

Toán học ứng dụng

Phan Thanh Toàn(1), Đặng Quốc Hữu, Nguyễn Thế Lộc

Thuật toán nhánh cận giải bài toán lập lịch luồng công việc

Branch and Bound Algorithm for Workflow Scheduling Problem

Tạp chí Khoa học (Đại học Sư phạm Hà Nội)

2018

3

108-116

2354-1075

Lập lịch luồng công việc, Điện toán đám mây, Phương pháp nhánh cận

Workflow scheduling, Cloud computing, Branch and bound algorithm

Điện toán đám mây là một môi trường dịch vụ dựa trên nền tảng công nghệ thông tin và truyền thông, mọi tài nguyên trên hệ thống đều được cung cấp cho người sử dụng dưới dạng dịch vụ, và người sử dụng chỉ phải chi trả các tài nguyên thực dùng. Với sự ra đời của công nghệ điện toán đám mây rất nhiều các ứng dụng trong lĩnh vực công nghệ thông tin đã có những thay đổi căn bản, chuyển từ dạng cung cấp sản phẩm đóng gói sử dụng riêng rẽ sang dạng cung cấp dịch vụ và được duy trì, vận hành bởi nhà cung cấp dịch vụ qua đó giảm đáng kể chi phí cho người dùng. Trong thực tiễn và nghiên cứu khoa học có nhiều bài toán được biểu diễn dưới dạng mô hình luồng công việc như lập lịch cho dây chuyền sản xuất, lập lịch điều phối tài nguyên trong hệ điều hành, lập lịch thời khóa biểu. Lập lịch là hoạt động nhằm gán các tác vụ vào thực hiện trên các tài nguyên tính toán và thảo mãn các ràng buộc về thứ tự các tác vụ trong luồng công việc cũng như các giới hạn về tài nguyên. Đa số các bài toán thuộc họ lập lịch đã được chứng minh thuộc lớp NP-Khó [1], do vậy việc tìm ra các thuật toán lập lịch nhằm cực tiểu hóa chi phí hoàn thành luồng công việc là một lĩnh vực khó và đã thu hút được sự quan tâm của nhiều nhà khoa học. Bài báo này đề xuất một thuật toán lập lịch luồng công việc mới nhằm cực tiểu hóa chi hoàn thành luồng công việc trong môi trường thực thi điện toán đám mây dựa trên phương pháp nhánh cận.

Cloud computing is a new trend of information and communication technology that enables resource distribution and sharing at a large scale. The Cloud consists of a collection of virtual machine that promises to provision on-demand computational and storage resources when needed. End-users can access these resources via the internet and have to pay only for their usage. Scheduling of scientific workflow applications on the Cloud is a challenging problem that has been the focus of many researchers for many years. In this work, we propose a novel algorithm for workflow scheduling that is derived from the Branch and Bound Algorithm.

TTKHCNQG, CVv 157

Xem toàn văn
  • [1] Phan Thanh Toàn, Nguyễn Thế Lộc, Nguyễn Doãn Cường, Đỗ Như Long (2015), Giải thuật tối thiểu hóa chi phí thực thi luồng công việc trong môi trường điện toán đám mây,Tạp chí khoa học trường đại học Sư Phạm Hà Nội, pp. 47-55.
  • [2] Q. XU, L.WANG, HE. Baomin, N.WANG (2011), Modified Opposition-Based Differential Evolution for Function Optimization,Journal of Computational Information Systems, pp. 1582-1591.
  • [3] S.Selvi, Dr. D.Manimegalai, Dr.A.Suruliandi (2011), Efficient Job Scheduling on Computational Grid with Differential Evolution Algorithm,International Journal of Computer Theory and Engineering, vol. 3, No. 2, April.
  • [4] Q. Cao, W. Gong and Z. Wei (2009), An Optimized Algorithm for Task Scheduling Based On Activity Based Costing in Cloud Computing,In Proceedings of Third International Conference on Bioinformatics and Biomedical Engineering, pp.1-3
  • [5] R. Rajkumar, T. Mala (2012), Achieving Service Level Agreement in Cloud Environment using Job Prioritization in Hierarchical Scheduling,Proceeding of International Conference on Information System Design and Intelligent Application, vol. 132, pp 547-554
  • [6] S. Pandey, L. Wu1, S. M. Guru, R. Buyya1 (2010), A Particle Swarm Optimization (PSO)- based Heuristic for Scheduling Workflow Applications in Cloud Computing Environments,Proc. of 24th IEEE International Conference on Advanced Information Networking and Applications (AINA), pp. 400-407.
  • [7] S. Singh, M.Kalra (2014), Task scheduling optimization of independent tasks in cloud computing using enhanced genetic algorithm,International Journal of Application or Innovation in Engineering & Management, vol.3, Issue 7.
  • [8] R. Rajkumar, T. Mala (2012), Achieving Service Level Agreement in Cloud Environment using Job Prioritization in Hierarchical Scheduling,Proceeding of International Conference on Information System Design and Intelligent Application, vol. 132, pp. 547-554.
  • [9] N.S.Grigoreva (2014), Branch and Bound Method for Scheduling Precedence Constrained Tasks on Parallel Identical Processors,Proc. of the World Congress on Engineering, Vol II
  • [10] J.D. Ullman (1975), NP-complete scheduling problems,Journal of Computer and System Sciences, pages 384-393, volume 10, issue 3.
  • [11] (), LIGO Project. LIGO - Laser Interferometer Gravitational Wave Observatory,http://www.ligo.caltech.edu.
  • [12] (), http://epigenome.usc.edu. [Online]. http://epigenome.usc.edu,
  • [13] P. Maechling et al. (2006), SCEC CyberShake Workflows, Automating Probabilistic Seismic Hazard Analysis Calculations,Springer.
  • [14] G. B. Berriman, et al. (2004), Montage: A Grid Enabled Engine for Delivering Custom Science-Grade Mosaics On Demand.,Proc. of the SPIE Conference.