Thuật toán lập lịch luồng công việc trong môi trường điện toán đám mây
Tóm tắt Thuật toán lập lịch luồng công việc trong môi trường điện toán đám mây: ...ễn Doãn Cường 689 Thời gian truyền dữ liệu giữa tác vụ Ti và tác vụ con Tj là ( ) ( )( )ji ij TfTfB D , (4) - Bài báo này định nghĩa hàm mục tiêu là: Makespan → min trong đó Makespan là thời gian hoàn thành luồng công việc, được tính từ khi tác vụ gốc được khởi động cho tới thời điểm t... pháp tìm kiếm tiến hóa nói chung đôi khi bị mắc kẹt tại các lời giải cực trị địa phương mà không thể thoát ra để đi tới lời giải tốt hơn. Bài báo này đề xuất thủ tục Inverse như một biện pháp được áp dụng mỗi khi vòng lặp chương trình sa vào một cực trị và các cá thể bị hút vào gần lời giải c...thước luồng công việc phụ thuộc vào vùng ảnh chụp được từ bầu trời. Hình 4 minh họa một luồng công việc gồm 20 tác vụ trong ứng dụng Montage Những dữ liệu đó được tổng hợp lại và chia thành bốn nhóm (được trình bày trong Bảng 3) dựa theo số lượng máy chủ N và số lượng tác vụ M bao gồm: H...
- Khối lượng dữ liệu do tác vụ Ti chuyển tới tác vụ Tj, kí hiệu là Dij với đơn vị là Megabit, là giá trị cho trước (∀i,j). - Mỗi phương án xếp lịch thực thi luồng công việc tương đương với một hàm f() f : T → S Ti → f(Ti) Trong đó f(Ti) là máy chủ chịu trách nhiệm thực thi tác vụ Ti Từ các giả thiết trên ta suy ra: Thời gian tính toán của tác vụ Ti là: ( )( )i i TfP W (i=1,2, ... M) (3) Hình 1. Đồ thị biểu diễn một luồng công việc với 5 tác vụ 1 43 2 5 Phan Thanh Toàn, Nguyễn Thế Lộc, Nguyễn Doãn Cường 689 Thời gian truyền dữ liệu giữa tác vụ Ti và tác vụ con Tj là ( ) ( )( )ji ij TfTfB D , (4) - Bài báo này định nghĩa hàm mục tiêu là: Makespan → min trong đó Makespan là thời gian hoàn thành luồng công việc, được tính từ khi tác vụ gốc được khởi động cho tới thời điểm tác vụ cuối cùng được thực hiện xong. IV. THUẬT TOÁN ĐỀ XUẤT 4.1. Mã hóa cá thể Theo phương pháp PSO, tại bước lặp thứ k, cá thể thứ i trong đàn được xác định bởi vector vị trí xik (cho biết vị trí hiện tại) và vector dịch chuyển vik (cho biết hướng dịch chuyển hiện tại). Trong bài toán xếp lịch đang xét, hai vector đó đều có số chiều bằng số tác vụ trong luồng công việc, ký hiệu là M. Các thành phần của vector vị trí xik là số nguyên nhưng các thành phần của vector dịch chuyển vik lại là số thực do công thức (1) tính vector dịch chuyển có những tham số là số thực như rand1, rand2, c1,c2. Cả vector vị trí và vector dịch chuyển đều được biểu diễn bằng cấu trúc dữ liệu bảng băm. Ví dụ 1: giả sử luồng công việc gồm tập tác vụ T={T1, T2, T3, T4, T5}, đám mây có tập máy chủ S = {S1, S2, S3}. Khi đó cá thể xi được biểu diễn bằng vector vị trí [1 ; 2 ; 1 ; 3 ; 2] chính là phương án xếp lịch mà theo đó tác vụ T1, T3 được bố trí thực hiện bởi máy chủ S1, tác vụ T2, T5 được thực hiện trên S2 còn tác vụ T4 được thực hiện bởi S3 như dưới đây T1 T2 T3 T4 T5 S1 S2 S1 S3 S2 4.2. Phương thức cập nhật vị trí của cá thể Khi áp dụng công thức cập nhật vị trí của cá thể (2) vào bài toán lập lịch đang xét, chúng ta gặp một vấn đề. Như đã giải thích ở trên, các thành phần của vector dịch chuyển vik phải là số thực do công thức (1) tính vector dịch chuyển có những tham số là số thực như rand1, rand2, c1,c2. Nhưng vì tập máy chủ S là hữu hạn và đếm được nên các thành phần của vector vị trí xi phải là số nguyên để có thể ánh xạ tới một máy chủ nào đó nơi mà tác vụ tương ứng sẽ được thực hiện, chẳng hạn vector vị trí xi trong ví dụ 1 có các thành phần là xi[1] =1, xi[2] =2, xi[1] =1, xi[4] =3, xi[5] =2. Hậu quả là hai vế của phép gán (2) khác kiểu nhau, vế trái xik+1[t] thuộc kiểu số nguyên còn vế phải xik[t] + vik[t] thuộc kiểu số thực. Để giải quyết mâu thuẫn này, một số nghiên cứu trước đây như [9] [11] đã làm tròn giá trị số thực ở vế phải rồi gán cho biến vị trí xik+1[t] ở vế trái. Kết quả là nếu giá trị của vế phải là 3.2 thì phân phối tác vụ tới thực thi tại máy chủ có số thứ tự là 3, còn nếu vế phải là 3.8 thì tác vụ sẽ được phân cho máy chủ có số thứ tự là 4. Cách làm có vẻ tự nhiên này thực chất là gán một vị trí được tính toán cẩn thận theo chiến lược PSO cho máy chủ mà số thứ tự của nó tình cờ đúng bằng giá trị nguyên sau khi làm tròn. Cách làm như vậy đã phá hỏng quá trình tiến hóa từng bước của phương pháp PSO. Để giải quyết vấn đề trên, bài báo này đề xuất cách giải quyết như sau: giá trị thực của vế phải (xik[t] + vik[t]) sẽ được để nguyên không làm tròn, còn vế trái xik+1[t] sẽ được gán bởi định danh của máy chủ có tốc độ tính toán gần với giá trị của vế phải nhất so với các máy chủ còn lại. Làm như vậy tác vụ sẽ được gán cho máy chủ có năng lực phù hợp với giá trị được tính toán theo PSO. Ví dụ 2: giả thiết tập máy chủ S trong ví dụ 1 có tốc độ tính toán được liệt kê trong bảng 1 sau đây Bảng 1. Tốc độ tính toán của các máy chủ Máy chủ Si Tốc độ xử lý P(Si) (MI/s) S1 3.1 S2 5.2 S3 4.1 Giả sử ở bước thứ k+1 tổng xik + vik = [4.4 ; 2.1 ; 6.7 ; 5.6 ; 10.2] thì vector vị trí xik+1 sẽ được gán bằng [3; 1; 2; 2; 2] nghĩa là cá thể đó tương ứng với phương án xếp lịch sau đây: T1 T2 T3 T4 T5 S3 S1 S2 S2 S2 Thật vậy, thành phần thứ nhất của vector vị trí, xik+1[1] , sẽ nhận giá trị 3, nghĩa là tác vụ T1 sẽ được gán cho máy chủ S3 bởi vì : Nghĩa là trong 3 máy chủ thì máy S3 có tốc độ tính toán gần với giá trị 4.4 nhất so với 2 máy chủ còn lại, theo bảng 1, do đó tác vụ T1 được gán cho máy chủ S3 để thực hiện, tức là f(T1) = S3. Phép gán tương tự cũng được thực hiện với bốn tác vụ còn lại : T2, T3,T4,T5. 690 THUẬT TOÁN LẬP LỊCH LUỒNG CÔNG VIỆC TRONG MÔI TRƯỜNG ĐIỆN TOÁN ĐÁM MÂY Vấn đề tương tự cũng xảy ra với phép trừ hai vector vị trí trong công thức (1): (pbesti - xik ) và (gbest - xik). Một số công trình hiện có như [9] [11] chỉ đơn giản thực hiện phép trừ các thành phần số nguyên rồi gán cho máy chủ có số thứ tự tương ứng. Ví dụ nếu pbesti = [2,4,3,3,5] và xik = [1,3,2,1,2] thì pbesti - xik =[2-1,4-3,3-2,3-1,5-2] = [1,1,1,2,3]. Như đã giải thích ở trên, cách làm này thực chất là gán các tác vụ cho những máy chủ mà số thứ tự của nó tình cờ đúng bằng kết quả phép trừ. Cách làm mang tính ngẫu nhiên như vậy đã phá hỏng quá trình từng bước tiếp cận tới vị trí cực trị của phương pháp PSO. Bài báo này đề xuất một "phép trừ vector" áp dụng riêng cho công thức (1) như sau. Giả sử: pbesti = [xi1, xi2,xiM] với xik∈ S (∀k) và xj = [xj1, xj2,xjM] với xjk∈ S (∀k) Khi đó kết quả phép trừ pbesti - xj được tính như sau: pbesti - xj =[y1, y2,.yM] với các thành phần yk là các số thực được tính như sau Theo cách tính này, các máy chủ được xếp thứ tự theo tốc độ tính toán và băng thông của những đường truyền kết nối tới nó. Ví dụ 3 sau đây sẽ minh họa cụ thể hơn. Ví dụ 3: Ta tiếp tục sử dụng tập máy chủ trong ví dụ 2. Giả sử gbest = [2,1,2,1,1] ; xj = [3,2,1,2,1] ; Vậy gbest – xj = [y1, y2, y3,y4,y5] với y1 được tính như sau Cách tính tương tự được áp dụng cho các thành phần y2, y3 y5 còn lại. 4.3. Biện pháp thoát khỏi cực trị địa phương Phương pháp PSO nói riêng và các phương pháp tìm kiếm tiến hóa nói chung đôi khi bị mắc kẹt tại các lời giải cực trị địa phương mà không thể thoát ra để đi tới lời giải tốt hơn. Bài báo này đề xuất thủ tục Inverse như một biện pháp được áp dụng mỗi khi vòng lặp chương trình sa vào một cực trị và các cá thể bị hút vào gần lời giải cực trị đó mà không thể thoát ra. Khi đó thủ tục Inverse sẽ chuyển các cá thể tới một miền không gian mới nhiều khả năng chưa được lục soát (xem Hình 3) Function Inverse (vector vị trí xi ) Input: vector vị trí xi Output: vector vị trí xi sau khi đã biến đổi 1. Sắp xếp các máy chủ theo thứ tự tăng dần của tốc độ tính toán ta thu được dãy (S π(1), Sπ(2) ,, Sπ(N) ), trong đó P(S π(1)) ≤ P(Sπ(2)) ≤≤ P(Sπ(N)) với Sπ(i) ∈ S (i=1,2 N) 2. Thay thế các thành phần trong vector vị trí của cá thể theo nguyên tắc đảo ngược: S π(1) được thay bởi Sπ(N) , Sπ(2) được thay bởi Sπ(N-1), 3. return xi End Function Thủ tục Inverse hoạt động theo nguyên tắc đảo chiều nhằm di chuyển mỗi cá thể tới một vị trí mới nằm xa vị trí hiện tại. Giả sử hiện tại một tác vụ đang được gán cho máy chủ có tốc độ xử lý nhanh nhất thực hiện, vậy thì sau khi thực hiện thủ tục Inverse nó sẽ được gán cho máy chủ có tốc độ chậm nhất, nếu tác vụ đó đang được gán cho máy chủ có tốc độ nhanh thứ 2 thì thủ tục Inverse sẽ chuyển nó tới thực hiện tại máy chủ có tốc độ chậm thứ 2. Ví dụ 4: ta vẫn tiếp tục xét tập máy chủ S ở các ví dụ trước, sắp xếp chúng theo thứ tự tăng dần của tốc độ xử lý ta thu được dãy (S1, S3 , S2 ), ký hiệu dãy đó là (Sπ(1), Sπ(2) , Sπ(3)) như hình 2. Giả sử cá thể xi đang có vector vị trí là [3, 1, 2, 2, 1, 1], áp dụng thủ tục Inverse với xi ta thu được cá thể mới có giá trị là [3, 2, 1, 1, 2, 2]. Thật vậy, thành phần xi[1] = 3 tức là tác vụ T1 được gán cho máy chủ S3, mà S3 chính là Sπ(2) (xem hình 2) nên nó đứng ở giữa danh sách, do đó không bị thay đổi khi danh sách đảo ngược. Thành phần xi[2] = 1 tức là tác vụ T2 được gán cho máy chủ S1, mà S1 chính là Sπ(1) (xem hình 2) nên thủ tục Inverse sẽ biến nó thành Sπ(3) tức là S2, vì thế giá trị mới của thành phần xi[2] sau khi gọi thủ tục Inverse là 2. Hình 2. Thủ tục Inverse 3.1 4.1 5.2 Sπ(2) Sπ(1) Sπ(3) 3.1 5.2 4.1 S2 S1 S3 Sπ(1)↔ Sπ(3) S1 ↔ S2 Hình 3. Quần thể được di cư tới vùng tìm kiếm mới thông qua thủ tục Inverse với M=20, N=8 Phan Thanh Toàn, Nguyễn Thế Lộc, Nguyễn Doãn Cường 691 4.4. Thuật toán đề xuất PSOi Tổng hợp những cải tiến nói trên, thuật toán đề xuất với tên gọi PSOi (PSO Inverse) được mô tả như sau. Algorithm PSOi Input: tập T, tập S, mảng W[1×M], mảng P[1×N], mảng B[N×N], mảng D[M×M], hằng số K, độ lệch ε, số cá thể SCT Output: lời giải tốt nhất gbest 1. Khởi tạo vector vị trí và vector dịch chuyển của cá thể i một cách ngẫu nhiên 2. Khởi tạo bước lặp t← 0 ; 3. while (điều kiện lặp) do 4. for i=1 to SCT do 5. Tính vector vị trí xi theo công thức (5) 6. end for 7. for i=1 to SCT do 8. Cập nhật pbesti 9. end for 10. Cập nhật gbest 11. for i=1 to SCT do 12. Cập nhật vector dịch chuyển vi theo (1) 13. Tính xi theo (2) 14. end for 15. t++ ; 16. if (sau K thế hệ mà độ lệch giữa các gbest không vượt quá ε) then 17. for i=1 to SCT do 18. Inverse(xi) //Thực hiện thao tác Inverse trên cá thể thứ i 19 end for 20 end if 21. end while 22. return gbest Thuật toán hoạt động theo phương pháp PSO theo đó tại mỗi bước các cá thể cập nhật vị trí của mình hướng tới vị trí tốt nhất của cả quần thể (gbest) đồng thời có dựa trên kinh nghiệm cá nhân (pbesti). Nếu sau K thế hệ liên tiếp mà cả quần thể không cải thiện được một cách đáng kể giá trị gbest (mức chênh không vượt quá ε) thì chứng tỏ quần thể đang hội tụ tại một cực trị địa phương. Khi đó thủ tục Inverse được gọi để di cư cả quần thể tới một vùng không gian mới, tại đó quá trình tìm kiếm được tái khởi động. Điều kiện lặp ở đây là mức chênh của giá trị gbest so với K vòng lặp trước đó lớn hơn độ lệch ε (ε ấn định từ trước), nghĩa là thuật toán PSOi sẽ dừng nếu như sau K lần di cư (thông qua thủ tục Inverse) mà giá trị gbest tìm được vẫn không cải thiện được một cách đáng kể (mức chênh không vượt quá ε). Trong trường hợp thuật toán hội tụ nhanh nhất, nghĩa là sau K lần thực hiện Inverse thì chương trình hội tụ tới cực trị, điều kiện dừng lặp được thỏa mãn nên chương trình kết thúc sau K2 thế hệ. Ngược lại, trong trường hợp tồi nhất, chương trình luôn tìm được lời giải tốt hơn sau mỗi lần di cư (thông qua thủ tục Inverse) thì các vùng tìm kiếm sẽ lần lượt được khảo sát cho tới khi toàn bộ không gian lời giải được duyệt hết, thuật toán trở thành duyệt vét cạn. Để tránh tình huống này, chúng tôi cũng sử dụng giải pháp chung thường được áp dụng trong các giải thuật tiến hóa, đó là đặt một giá trị ngưỡng tối đa, khi quá trình tiến hóa của quần thể đạt tới số thế hệ vượt quá giá trị ngưỡng đã định thì quá trình tìm kiếm kết thúc. Trong phần thực nghiệm tiếp theo giá trị ngưỡng cho số thế hệ là 3000, giá trị K được đặt là 30 và độ lệch ε được ấn định là 0.21. V. THỰC NGHIỆM 5.1. Phân nhóm dữ liệu thực nghiệm Dữ liệu sử dụng trong các thực nghiệm bao gồm: • Dữ liệu thực tế thu được từ các công ty cung cấp dịch vụ Cloud trong nước [13] [14] và quốc tế [15] [16] • Dữ liệu mô phỏng được lấy từ nguồn cung cấp Cloud Sim [8] • Dữ liệu luồng công việc được lấy từ dự án Montage [17], đây là dự án nghiên cứu thiên văn được tổ chức và tài trợ bởi NASA/IPAC, dữ liệu của ứng dụng được thu thập từ các kính thiên văn, kích thước luồng công việc phụ thuộc vào vùng ảnh chụp được từ bầu trời. Hình 4 minh họa một luồng công việc gồm 20 tác vụ trong ứng dụng Montage Những dữ liệu đó được tổng hợp lại và chia thành bốn nhóm (được trình bày trong Bảng 3) dựa theo số lượng máy chủ N và số lượng tác vụ M bao gồm: Hình 4. Luồng công việc Montage với 20 tác vụ 692 THUẬT TOÁN LẬP LỊCH LUỒNG CÔNG VIỆC TRONG MÔI TRƯỜNG ĐIỆN TOÁN ĐÁM MÂY • Nhóm 1: M=5, N=3 • Nhóm 2: M=10, N=3 • Nhóm 3: M=20, N=8 • Nhóm 4: M=25, N=8 (luồng công việc từ ứng dụng Montage) Mỗi nhóm lại bao gồm ba thực nghiệm khác nhau về tỷ lệ số cạnh trên số đỉnh của đồ thị luồng công việc, ký hiệu là α Tham số α cho biết đồ thị G phân thành bao nhiêu cấp, mỗi cấp có nhiều hay ít tác vụ, nói cách khác α phản ánh độ trù mật của đồ thị G. Khi làm thực nghiệm với mỗi nhóm, số máy chủ và số tác vụ được giữ cố định còn tỷ lệ α lần lượt thay đổi như trong các hình 4, 5, 6. 5.2. Tham số cấu hình hệ thống Các tham số cấu hình của đám mây được thiết lập trong miền giá trị như sau: • Tốc độ tính toán P của các máy chủ: từ 1 đến 250 (million instructions/s) • Khối lượng dữ liệu D giữa các tác vụ: từ 1 đến 10000 (Mega bit) • Băng thông giữa các máy chủ B: từ 10 đến 100 (Mega bit/s) • Hệ số quán tính: ω = 0.729 • Hệ số gia tốc: c1 = c2 = 1.49445 • Hằng số: K = 30 • Số cá thể SCT: SCT=25 • Độ lệch ε: 0.21 • α: từ 0.2 tới 0.7 5.3. Quá trình tiến hành thực nghiệm Để kiểm chứng thuật toán đề xuất PSOi chúng tôi đã sử dụng công cụ mô phỏng Cloudsim [1] để tạo lập môi trường đám mây kết hợp với dữ liệu luồng công việc của ứng dụng Montage [17]. Các hàm của gói thư viện Jswarm [1] được sử dụng để thực hiện các phương thức Tối ưu bầy đàn. Đối tượng so sánh là thuật toán PSO [9], thuật toán Random [12] và thuật toán Round Robin [13]. Các chương trình mô phỏng được viết bằng ngôn ngữ Java và chạy trên máy tính cá nhân với bộ vi xử lý Intel Core i5 2.2 GHz, RAM 4GB, hệ điều hành Windows 7 Ultimate. Thực nghiệm được lặp lại 300 lần trên mỗi nhóm thực nghiệm. Để kiểm chứng hiệu quả của thủ tục Inverse trong quá trình tìm kiếm lời giải chúng tôi đã thực hiện thuật toán PSOi trên các bộ dữ liệu khác nhau và thống kê tỉ lệ thủ tục Inverse giúp thoát khỏi cực trị địa phương, kết quả được trình bày trong bảng 3. 5.4. Kết quả thực nghiệm Hình 5, 6, 7, 8 cho thấy sự chênh lệch về thời gian xử lý (makespan) của lời giải tốt nhất mà thuật toán đề xuất PSOi và các thuật toán đối chứng (PSO, Random và Round Robin) tìm được khi chạy trên 4 nhóm dữ liệu thực nghiệm khác nhau. Bảng 2. Kết quả thực nghiệm M N α PSOi PSO Random Round Robin 5 3 0.2 7.8 9.0 30.75 28.6 5 3 0.4 4.7 6.6 21.45 19.9 5 3 0.6 6.2 7.1 14.1 12.6 10 3 0.2 15.7 19.3 46.6 43.6 10 3 0.4 13.6 22.4 51.5 42.0 10 3 0.7 14.3 17.0 25.8 22.6 20 8 0.2 8.4 12.2 60.5 55.7 20 8 0.3 8.8 12.5 58.5 50.1 20 8 0.5 11.2 13.1 65.1 56.5 25 8 0.2 2.9 3.9 15.1 13.5 Hình 5. Lời giải tìm được bởi các thuật toán trong trường hợp M=5, N=3 Phan Thanh Toàn, Nguyễn Thế Lộc, Nguyễn Doãn Cường 693 Các thông số ở bảng 2 cho thấy thuật toán được kiểm chứng trên nhiều bộ dữ liệu khác nhau về quy mô của luồng công việc (số tác vụ M và số máy chủ N) và độ trù mật α của đồ thị liên kết G. Kết quả thực nghiệm cho thấy trong hầu hết các trường hợp thuật toán đề xuất PSOi đều cho lời giải tốt hơn các thuật toán PSO, Random và Round Robin. Riêng với nhóm thực nghiệm thứ nhất (số tác vụ bằng 5 và số máy chủ bằng 3) thì thuật toán PSOi cho lời giải gần xấp xỉ với lời giải tốt tuyệt đối tìm được bằng phương pháp duyệt vét cạn: 7.8 giây so với 7.7 giây. VI. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN Bài báo này đã trình bày một giải thuật tìm kiếm theo phương pháp Tối ưu bầy đàn để tìm lời giải gần đúng cho bài toán lập lịch thực thi luồng công việc trong môi trường điện toán đám mây. Những kết quả chính gồm có: - Đề xuất một phương thức mới để cập nhật vị trí của cá thể bằng cách ánh xạ một giá trị thực tới máy chủ có tốc độ tính toán và băng thông gần với giá trị đó nhất. - Đề xuất thủ tục Inverse để chương trình thoát ra khỏi cực trị địa phương bằng cách chuyển các cá thể tới một miền không gian tìm kiếm mới. - Đề xuất thuật toán PSOi sử dụng phương thức cập nhật vị trí cá thể và thủ tục Inverse để tìm kiếm lời giải cho bài toán lập lịch thực thi luồng công việc trong môi trường đám mây. Những kết quả thực nghiệm được tiến hành với nhiều bộ dữ liệu thực nghiệm khác nhau đã chứng tỏ chất lượng lời giải tìm được bởi thuật toán đề xuất tốt hơn so với các thuật toán đối chứng là thuật toán PSO gốc, thuật toán Random và thuật toán Round Robin. Về hướng công việc tiếp theo, ngoài hai yếu tố hiện nay là kinh nghiệm cá nhân (pbest) và kinh nghiệm từ cả quần thể (gbest) chúng tôi dự định đưa thêm vào yếu tố kinh nghiệm của các cá thể trong một lân cận xác định theo lược đồ Ring hoặc Star để cập nhật vị trí mới cho mỗi cá thể nhằm đạt được lời giải có chất lượng tốt hơn. Hình 6. Lời giải tìm được bởi các thuật toán trong trường hợp M=10, N=3 Hình 8. Lời giải tìm được bởi các thuật toán cho luồng công việc Montage với M=25, N=8 Bảng 3. Kết quả thử nghiệm thủ tục Inverse M N α Tỉ lệ cá thể mới sinh ra sau mỗi lần Inverse 5 3 0.2 12.9% 5 3 0.4 13.1% 10 3 0.2 13.4% 10 3 0.4 15.2% 10 3 0.7 13.8% 20 8 0.2 22.9% 20 8 0.3 20.6% 20 8 0.5 21.5% Hình 7. Lời giải tìm được bởi các thuật toán trong trường hợp M=20, N=8 694 THUẬT TOÁN LẬP LỊCH LUỒNG CÔNG VIỆC TRONG MÔI TRƯỜNG ĐIỆN TOÁN ĐÁM MÂY TÀI LIỆU THAM KHẢO [1]. Công cụ mô phỏng CloudSim [2]. J. D. Ullman, “NP-complete scheduling problems”, Journal of Computer and System Sciences, Volume 10, Issue 3, 1975 [3]. S. Parsa, R. E. Maleki “RASA: A New Task Scheduling Algorithm in Grid Environment”, International Journal of Digital Content Technology and its Applications, Vol. 3, No. 4, 2009 [4]. J. M. Cope, N. Trebon, H. M. Tufo, P. Beckman, “Robust data placement in urgent computing environments”, IEEE International Symposium on Parallel & Distributed Processing, IPDPS 2009 [5]. A. Agarwal, S. Jain, “Efficient Optimal Algorithm of Task Scheduling in Cloud Computing Environment”, International Journal of Computer Trends and Technology (IJCTT), vol. 9, 2014 [6]. M. Wieczorek, “Marek Scheduling of Scientific Workflows in the ASKALON Grid Environment”, ACM SIGMOD Record Journal, Vol. 34, Issue 3, 2005. [7]. A. Salman, “Particle swarm optimization for task assignment Problem”, Microprocessors and Microsystems, 2002. [8]. S. Pandey, A. Barker, K. K. Gupta, R. Buyya, “Minimizing Execution costs when using globally distributed cloud services”, 24th IEEE International Conference on Advanced Information Networking and Applications, 2010. [9]. J. Kennedy, RC. Eberhart, “Particle swarm optimization”, in Proc. IEEE Int’l. Conference on Neural Networks, vol. IV, 1995. [10]. T. Davidovic, M. Selmic, D. Teodorovic, D. Ramljak “Bee colony optimization for scheduling independent tasks to identical processors”, Journal of Heuristics, 2012. [11]. M. Mitzenmacher, E. Upfal, “Probability and Computing: Randomized Algorithms and Probabilistic Analysis”, Cambridge University Press, 2005. [12]. Don Fallis, “The Reliability of Randomized Algorithms”, British Journal for the Philosophy of Science, 2000. [13]. https://www.ngoisaoso.net/Cloud-Server.html [14]. [15]. [16]. [17]. THUẬT TOÁN LẬP LỊCH LUỒNG CÔNG VIỆC TRONG MÔI TRƯỜNG ĐIỆN TOÁN ĐÁM MÂY Phan Thanh Toan, Nguyen The Loc, Nguyen Doan Cuong ABSTRACT - The key factor which rules the cloud’s performance is the workflow scheduling, one of the well-known problems have proven to be NP-complete. Many algorithm in the literature have been targeting the workflow scheduling problem, however, handful efficient solutions have been proposed. This paper proposes a metaheuristic algorithm called PSOi which based on the Particle Swarm Optimization method. Our experiments which arranged by using the simulation tool CloudSim show that PSOi is superior to the general algorithms called Random and RoundRobin, moreover the deviation between the solution found by PSOi and the optimal solution is negligible. Keywords: workflow scheduling, particle swarm optimization, cloud computing.
File đính kèm:
- thuat_toan_lap_lich_luong_cong_viec_trong_moi_truong_dien_to.pdf